歐拉函數

• $p$是素數，則有$?(p)=p?1$

  證明：顯然。

• $p$是素數，$n=p^k$，則$?(n)=p^k?p^{k?1}$

  證明：

  $[1,n]$內，$p$的約數有$p,2p,3p,4p\dots \dots (p^{k?1}?1)p$個，所以$?(n)=p^k?1?(p^{k?1}?1)=p^k?p^{k?1}$

• $p,q$是素數，$?(pq)=?(p)??(q)$

  證明：

  $pq?1$內是$p$的倍數的有$q?1$個，是$q$的倍數的有$p?1$個，$?(pq)=pq?1?(q?1)?(p?1)=pq?p?q?1=(p?1)(q?1)=?(p)?(q)$

  拓展$p,q$互質即可滿足條件。

• $a\%p==0,p是質數$，則$?(ap)=?(a)p$

  證明：

  一定有$a=k{p}^n$，$k,p$互質，

  $\therefore ?(a)=?(k)?(p^n)$

  $\therefore ?(k)=\frac{?(a)}{?(a^n)}$

  $\because ap=k{p}^{n+1}$

  $\therefore ?(ap)=?(k)?(p^{n+1})$

  $\therefore ?(ap)=?(a)\frac{?(p^{n+1})}{?(p^n)}$

  $\because ?(p^{n+1})=p^{n+1}?p^n,?(p^n)=p^n?p^{n?1}$

  $\therefore ?(ap)=?(a)\frac{?(p^{n+1})}{?(p^n)}=?(a)\frac{p^{n+1}?p^n}{p^n?p^{n?1}}$

  $\therefore ?(ap)=?(a)p$

• $n=p_1^{a_1}{p}_2^{a_2}\dots \dots p_n^{a_n}$則，$?(n)=n(1?\frac{1}{p_1})(1?\frac{1}{p_2})\dots \dots \frac{1}{p_n}$

  證明：

  $\because ?(n)=?(p_1^{a_1})?(p_2^{a_2})\dots \dots ?(p_n^{a_n})$

  $\therefore ?(n)=(p_1^{a_1}?p_1^{a_1?1})(p_2^{a_2}?p_2^{a_2?1})\dots \dots (p_n^{a_n}?p_n^{a_n?1})$

  每個括號里提出一個$p_i^{a_i}$得$?(n)=p_1^{a_1}{p}_2^{a_2}\dots \dots p_n^{a_n}(1?\frac{1}{p_1})(1?\frac{1}{p_2})\dots \dots \frac{1}{p_n}$

  即證得：$?(n)=n(1?\frac{1}{p_1})(1?\frac{1}{p_2})\dots \dots \frac{1}{p_n}$

• 關于歐拉函數得遞推求法

  顯然可以在歐拉素數篩的同時得到歐拉函數值

  $prime[j]\mid i$時，有$?(i?prime[j])=?(i)?prime[j]$

  其次就是兩個互質的情況了

  $?(i?prime[j])=?(i)?(prime[j]?1)$

  再最后就是$i$為質數的情況了，$?(i)=i?1$

• $n$的所有約數的歐拉函數之和等于$n$

  證明：

• 對于給定$n$，${\sum }_{i=1}^{n?1}i(gcd(i,n)==1)=\frac{n?n}{2}$

  證明：

  顯然$gcd(i,n)=1$，則有$gcd(n?i,n)=1$，所以互質數兩兩存在則有上面式子${\sum }_{i=1}^{n?1}i(gcd(i,n)==1)=\frac{n?n}{2}$成立。

• $d=gcd(a,b)$，$?(ab)=\frac{?(a)?(b)d}{?(d)}$

  證明：

總結

以上是生活随笔為你收集整理的欧拉函数的性质及其证明的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。