نویسنده : کیوان عباس زاده اسک شهری
تاریخ : $1395/04/03$
تابع فی اویلر
تابع $ \varphi : \mathbb{N} \longrightarrow \mathbb{N}$ که دارای ضابطه زیر است را تابع فی اویلر می نامند :
$$ \varphi (n)=| \lbrace m\in \mathbb{N}\ |\ m \leq n,\ gcd(m,n)=1\rbrace |$$
در واقع به ازای عدد طبیعی $n$ , $ \varphi (n)$ برابر تعداد اعداد طبیعی کوچکتر یا مساوی $n$ است که نسبت به $n$ اول هستند .
مثال : $ \varphi (8)=4$ زیرا اعداد طبیعی کوچکتر یا مساوی $8$ که نسبت به $8$ اول هستند عبارتند از $1,3,5,7$ .
قضیه ۱ : اگر $p$ عددی اول باشد آنگاه $ \varphi (p)=p-1$ .
اثبات : چون $p$ عددی اول است پس تمام اعداد طبیعی کوچکتر یا مساوی $p$ نسبت به $p$ اول هستند یعنی :
$$\lbrace m\in \mathbb{N}\ |\ m \leq p,\ gcd(m,p)=1\rbrace= \lbrace 1,2,...,p-1\rbrace $$
پس $ \varphi (p)=p-1$ .
قضیه 2 : اگر $p$ عددی اول باشد و $r$ عدد صحیح مثبت باشد آنگاه :$$ \varphi (p^r)=p^{r-1}(p-1)$$
اثبات : اعداد طبیعی کوچکتر یا مساوی $p^r$ که نسبت به آن اول نمی باشند مضارب عدد $p$ هستند که عبارتند از $p,2p,...,p^r$ یعنی :
$$\lbrace m\in \mathbb{N}\ |\ m \leq p^r,\ gcd(m,p^r) \neq 1\rbrace = \lbrace p,2p,...,p^r\rbrace $$
پس :
$$| \lbrace m\in \mathbb{N}\ |\ m \leq p^r,\ gcd(m,p^r) \neq 1\rbrace |=p^{r-1}$$
بنابراین داریم :
$$ \varphi (p^r)=| \lbrace m\in \mathbb{N}\ |\ m \leq p^r,\ gcd(m,p^r) = 1\rbrace |=p^r-p^{r-1}$$
$$ \Rightarrow \varphi (p^r)=p^{r-1}(p-1)$$
قضیه 3 : اگر $m,n $ دو عدد طبیعی باشند و $gcd(m,n)=1$ آنگاه :
$$ \varphi (mn)= \varphi (m) \varphi (n)$$
نتیجه : اگر $m_{1},m_{2},...,m_{k}$ اعداد طبیعی باشند که دو به دو نسبت به اول هستند یعنی برای هر $i \neq j$ داریم $gcd(m_{i},m_{j})=1$ آنگاه داریم :
$$ \varphi (m_{1}m_{2}...m_{k})= \varphi (m_{1}) \varphi (m_{2})... \varphi (m_{k})$$
قضیه 4 : اگر تجزیه عدد طبیعی $n$ به صورت $n=p_{1}^{ \alpha _{1}}p_{2}^{ \alpha _{2}}...p_{k}^{ \alpha _{k}}$ باشد که $p_{1},p_{2},...,p_{k}$ اعداد اول متمایز هستند و $ \alpha _{1}, \alpha _{2},..., \alpha _{k}$ اعداد صحیح مثبت هستند آنگاه :
$$ \varphi (n)=n(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})...(1-\frac{1}{p_{k}})$$
اثبات : به ازای هر $i \neq j$ داریم $gcd(p_{i}^{ \alpha _{i}},p_{j}^{ \alpha _{j}})=1$ پس طبق نتیجه بالا داریم :
$$\varphi (p_{1}^{ \alpha _{1}}p_{2}^{ \alpha _{2}}...p_{k}^{ \alpha _{k}})= \varphi (p_{1}^{ \alpha _{1}}) \varphi (p_{2}^{ \alpha _{2}})... \varphi (p_{k}^{ \alpha _{k}})$$
$$ \Rightarrow \varphi (n)= \varphi (p_{1}^{ \alpha _{1}}) \varphi (p_{2}^{ \alpha _{2}})... \varphi (p_{k}^{ \alpha _{k}})$$
حال طبق قضیه $2$ به ازای هر $ i=1,2,...,k $ داریم :
$$ \varphi (p_{i}^{ \alpha _{i}})=p_{i}^{ \alpha _{i}-1}(p_{i}-1)$$
پس :
$$ \varphi (n)=p_{1}^{ \alpha _{1}-1}(p_{1}-1)p_{2}^{ \alpha _{2}-1}(p_{2}-1)...p_{k}^{ \alpha _{k}-1}(p_{k}-1)$$
$$ \Rightarrow \varphi (n)=p_{1}^{ \alpha _{1}}(\frac{p_{1}-1}{p_{1}})p_{2}^{ \alpha _{2}}(\frac{p_{2}-1}{p_{2}})...p_{k}^{ \alpha _{k}}(\frac{p_{k}-1}{p_{k}})$$
$$ \Rightarrow \varphi (n)=n(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})...(1-\frac{1}{p_{k}})$$
مثال : $ \varphi (120)$ را حساب کنید .
حل : $120=2^3 \times 3 \times 5$ پس :
$$ \varphi (120)=120(1-\frac{1}{2})(1-\frac{1}{3})(1-\frac{1}{5})=32$$
پس در میان اعداد طبیعی کوچکتر یا مساوی $120$ ، $32$ عدد نسبت به $120$ اول هستند .
البته بدون استفاده از قضیه های بالا هم می توان فرمول تابع فی اویلر را بدست آورد . برای این کار کافی است از اصل شمول و عدم شمول استفاده کنیم . فرض کنید $n$ عدد طبیعی است و تجزیه آن به اعداد اول به صورت $n=p_{1}^{ \alpha _{1}}p_{2}^{ \alpha _{2}}...p_{k}^{ \alpha _{k}}$تعریف کنید :
$$S= \lbrace 1,2,...,n\rbrace $$
حال به ازای هر $i=1,...,k$ تعریف می کنیم :
$$A_{i}= \lbrace m\in S\ :\ p_{i}|m\rbrace $$
یعنی مجموعه $A_{i}$ مجموعه اعداد طبیعی کوچکتر یا مساوی $n$ است که مضرب $p_{i}$ هستند . حال واضح است که عدد طبیعی $m\in S$ نسبت به $n$ اول است هرگاه مضرب هیچ یک از اعداد اول $p_{1},p_{2},...,p_{k}$ نباشد . یعنی به ازای هر $i=1,...,k$ داشته باشیم $m\notin A_{i}$ . پس :
$$\lbrace m\in \mathbb{N}\ |\ m \leq n,\ gcd(m,n)=1\rbrace= \bigcap_{i=1}^k A_{i} ^c$$
( توجه : منظور از $A_{i}^c$ متمم مجموعه $A_{i}$ است ).
پس :
$$ \varphi (n)=|\lbrace m\in \mathbb{N}\ |\ m \leq n,\ gcd(m,n)=1\rbrace|= |\bigcap_{i=1}^k A_{i} ^c|$$
طبق اصل شمول و عدم شمول داریم :
$$\begin{align}|\bigcap_{i=1}^k A_{i} ^c|&=|S|- \sum_{i=1}^k |A_{i}|\\
&+\sum_{1 \leq i < j \leq k} |A_{i} \bigcap A_{j} |\\
&-\sum_{1 \leq i < j < s \leq k} |A_{i} \bigcap A_{j} \bigcap A_{s}|\\
&+...\\
&+(-1)^k|\bigcap_{i=1}^k A_{i} ^c|\\
\end{align} $$
حال هریک از زیگماهای بالا را محاسبه می کنیم اما قبل از آن نکته زیر را یادآوری می کنیم :
نکته : اگر $n,a$ عدد طبیعی باشند آنگاه تعداد اعداد طبیعی کوچکتر یا مساوی $n$ که مضرب $a$ هستند برابر است با $[\frac{n}{a}]$ .
پس به ازای هر $i=1,...,k$ داریم :
$$|A_{i}|=[\frac{n}{p_{i}}]=\frac{n}{p_{i}}$$
و به ازای هر $1 \leq i < j \leq k$ :
$$|A_{i}\bigcap A_{j}|=[\frac{n}{p_{i}p_{j}}]=\frac{n}{p_{i}p_{j}}$$
( زیرا عدد $m\in A_{i}\bigcap A_{j}$ اگر و تنها اگر $m$ هم مضرب $p_{i}$ و هم مضرب $p_{j} $ باشد اگر و تنها اگر $m$ مضرب $p_{i}p_{j}$ باشد . )
و به طور کلی برای هر $1 \leq t \leq k$ و $1 \leq i_{1} < i_{2} < ... < i_{t} \leq k$ :
$$|A_{i_{1}}\bigcap...\bigcap A_{i_{t}}|=[\frac{n}{p_{i_{1}}...p_{i_{t}}}]=\frac{n}{p_{i_{1}}...p_{i_{t}}}$$
پس با جاگذاری در بالا داریم : ( توجه : $|S|=n$ )
$$\begin{align}|\bigcap_{i=1}^k A_{i} ^c|&= n- \sum_{i=1}^k \frac{n}{p_{i}} \\
&+ \sum_{1 \leq i < j \leq k} \frac{n}{p_{i}p_{j}}\\
&-\sum_{1 \leq i < j < s \leq k} \frac{n}{p_{i}p_{j}p_{s}}\\
&+...\\
&+ (-1)^k\frac{n}{p_{1}p_{2}...p_{k}}\\
\end{align} $$
بعد از فاکتور گیری از $n$ واستفاده از اتحاد جمله مشترک خواهیم داشت :
$$\varphi (n)=n(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})...(1-\frac{1}{p_{k}})$$
مطمئنم تا اینجا از اثبات قبلی خوشحال هستید .
