Note
這篇文章涉及幾個歐拉函數的性質
暫時沒有證明，大概寒假的時候會補一下證明
完結撒花！我居然在寒假第一天就把這證明補完了...
如果下方的證明有哪裡有問題的話，請在下方評論區指出，以提醒作者修改。
定義
\(\phi(n)\)表示在1~n中與n互質的數
計算式及計算方法
\[\begin{aligned}
&若n根據算術基本定理分解為n=p_1^{c_1}p_2^{c_2}...p_m^{c_m}\\
&則\phi(n)=n\prod_{i=1}^{m}\left(1-\frac{1}{p}\right)\\
&也可以變式為\phi(n)=n\prod_{i=1}^m\left(\frac{p-1}{p}\right)\\
&本質是一樣的
\end{aligned}
\]
\(upd\)：\(O(\frac{\sqrt{n}}{\log n})\)計算一個數的歐拉函數
分解質因數，由性質4可以順便算出每個\(\varphi(p^k)\)，然後因為\(\varphi\)是個積性函數，是以直接把每個值相乘即得到該數的\(\varphi\)。
直接分解質因數是\(O(\sqrt{n})\)的，但是隻要預處理出根号内的質數就可以\(O(\frac{\sqrt{n}}{\log n})\)計算一個數的歐拉函數了。
性質1
\[\begin{aligned}
&\phi是積性函數，但不是完全積性函數\\
&當n,m互質時，滿足:\\
&\phi(nm)=\phi(n)*\phi(m)\\
&那麼顯然，當n根據算術基本定理分解為n=p_1^{c_1}p_2^{c_2}...p_m^{c_m}時\\
&\phi(n)=\prod_{i=1}^m{\phi(p_i^{c_i})}
\end{aligned}
\]
證明：
\[\begin{aligned}
&若n與m互質，則n與m沒有相同的質因子\\
&設n的質因子個數為cnt_n,m的質因子個數為cnt_m，則\\
&\phi(n)*\phi(m)\\
&=n*\prod_{i=1}^{cnt_n}(1-p_i)*m*\prod_{i=1}^{cnt_m}(1-p_i)\\
&=n*m*\prod_{i=1}^{cnt_n+cnt_m}(1-p_i)\\
&=\phi(nm)
\end{aligned}
\]
證畢。
性質2
對于質數\(p\)，它的歐拉函數值\(\phi(p)=p-1\)
證明：
因為\(p\)為質數，是以比它小的數都和它互質，即在1~p***有p-1個數和它互質。
證畢。
性質3
\[當n為奇數時,\phi(2*n)=\phi(n)
\]
證明：
\[\begin{aligned}
&當n為奇數時，n與2互質\\
&由歐拉函數是積性函數可知，n與2互質時，\phi(2n)=\phi(2)*\phi(n)\\
&又因為\phi(2)=1\\
&是以\phi(2n)=\phi(n)
\end{aligned}
\]
證畢。
性質4
\[當n=p^k時，\phi(n)=p^k-p^{k-1}
\]
證明：
\[因為n=p^k，是以n隻有p一個質因數，則由歐拉函數的計算式可得\\
\phi(n)=p^k*(1-\frac{1}{p})=p^k-p^{k-1}
\]
性質5
\[\begin{aligned}
&n中與n互質的數的和為\phi(n)/2*n(n>1)\\
&\phi(n)(n>2)為偶數
\end{aligned}
\]
證明：
需要知道的一個基本事實是\(gcd(n,x)=gcd(n,n-x)(n>x)\)
關于這個，可以了解一下更相減損術
因為\(gcd(n,x)=gcd(n,n-x)(n>x)\)，是以與n互質的數都是成對出現的
每一對的和都為\(n\)。是以他們的和為\(\phi(n)/2*n\)。
至于\(\phi(n)(n>2)\)為偶數。因為與n互質的數都是成對出現的，是以顯然與n互質的數為偶數，即\(\phi(n)\)為偶數。
證畢。
性質6
\[\begin{aligned}
&若p|n且p^2|n，則\phi(n)=\phi(\frac{n}{p})*p\\
&若p|n且p^2\not|\space\space n,則\phi(n)=\phi(\frac{n}{p})*(p-1)
\end{aligned}
\]
證明：
對于第一點
\[\begin{aligned}
&若p|n且p^2|n，則證明n和\frac{n}{p}有相同的質因子，隻是p這一項的指數不同\\
&那麼我們可以将其按照歐拉函數的計算式展開，并相除，可得：\\
&\frac{n\prod_{i=1}^m(1-\frac{1}{p_i})}{\frac{n}{p}\prod_{i=1}^{m}(1-\frac{1}{p_i})}=\frac{n}{\frac{n}{p}}=p\\
\end{aligned}
\]
對于第二點
\[\begin{aligned}
&若p|n且p^2\not|\space\space n，則說明p與\frac{n}{p}互質（因為p為素數）\\
&那麼根據歐拉函數為積性函數的這個性質即可證得\phi(n)=\phi(\frac{n}{p})*\phi(p)=\phi(\frac{n}{p})*(p-1)
\end{aligned}
\]
證畢。
這個性質廣泛用于遞推求歐拉函數
性質7
\[\sum_{d|n}\phi(d)=n
\]
證明：
\[設f(n)=\sum_{d|n}\phi(d)\\
\]
則f(n)為一個積性函數（當n，m互質時）
證明：
（設n,m互質）
\[\begin{aligned}
&f(n)*f(m)\\
&=\sum_{i|n}\phi(i)*\sum_{j|m}\phi(m)\\
&=\sum_{i|n}\sum_{j|m}\phi(i)*\phi(j)\\
&=\sum_{i|n}\sum_{j|m}\phi(i*j)\\
&=\sum_{d|nm}\phi(d)\\
&=f(nm)
\end{aligned}\\
\begin{aligned}
&可以發現的是\sum_{i|n}\sum_{j|m}\phi(i*j)涵蓋了所有nm的因數的歐拉函數，即為f(n)*f(m)\\
&是以f是一個積性函數
\end{aligned}
\]
那麼則有
\[\begin{aligned}
&若n根據算數基本定理可以分解為p_1^{c_1}p_2^{c_2}...p_k^{c_k}\\
&則由f是一個積性函數可知，f(n)=f(p_1^{c_1})*f(p_2^{c_2})*...*f(p_k^{c_k})\\
&是以f(p^c)=\phi(1)+\phi(p)+\phi(p^2)+...+\phi(p^k)=1+(p-1)+(p^2-p)+...+(p^k-p^{k-1})=p^k\\
&則f(n)=f(p_1^{c_1})*f(p_2^{c_2})*...*f(p_k^{c_k})=p_1^{c_1}*p_2^{c_2}*...*p_k^{c_k}=n\\
&即\sum_{d|n}\phi(d)=n
\end{aligned}
\]
證畢。
性質8
\[\phi(n)=\sum_{d|n}\frac{\mu(d)}{d}
\]
證明
我們将性質7用狄利克雷卷積形式表示出來
\[\begin{aligned}
&\phi*1=id\\
&兩邊卷上\mu\\
&\phi*1*\mu=id*\mu\\
&\phi*(1*\mu)=id*\mu\\
&\phi*e=id*\mu
\end{aligned}
\]
最後一個式子寫出來就是
\[\phi(n)=\sum_{d|n}\frac{\mu(d)}{d}
\]
證畢。