歐拉函數 ：
歐拉函數是數論中很重要的一個函數，歐拉函數是指：對于一個正整數 n ，小于 n 且和 n 互質的正整數（包括 1）的個數，記作 φ(n) 。?

完全余數集合：
定義小于 n 且和 n 互質的數構成的集合為 Zn ，稱呼這個集合為 n 的完全余數集合。 顯然 |Zn| ＝φ(n) 。

有關性質：
對于素數 p ，φ(p) = p -1 。
對于兩個不同素數 p， q ，它們的乘積 n = p * q 滿足 φ(n) = (p -1) * (q -1)? 。
這是因為 Zn = {1, 2, 3,? ... , n - 1} - {p, 2p, ... , (q - 1) * p} - {q, 2q, ... , (p - 1) * q} ， 則 φ(n) = (n - 1) - (q - 1) - (p - 1) = (p -1) * (q -1)? ＝φ(p) *?φ(q)?。

歐拉定理 ：
對于互質的正整數 a 和 n ，有?aφ(n)? ≡ 1 mod n? 。

證明：
( 1 ) 令?Zn = {x1, x2, ..., xφ(n)}?，?S?= {a * x1?mod n, a * x2?mod n, ... , a * xφ(n)?mod n}?，
??????? 則 Zn = S 。
??????? ① 因為 a 與 n 互質，?xi?(1 ≤ i ≤ φ(n))?與 n 互質， 所以 a *?xi? 與 n 互質，所以 a *?xi? mod n ∈ Zn 。
??????? ② 若 i ≠ j ， 那么?xi?≠?xj，且由 a, n互質可得?a * xi?mod n ≠?a * xj?mod n （消去律）。

( 2 )?????aφ(n)?*?x1?*?x2?*... *?xφ(n)?mod n?
??????≡?(a * x1) * (a * x2) * ... * (a * xφ(n))?mod n
??????≡?(a * x1?mod n) * (a * x2?mod n) * ... * (a * xφ(n)?mod n)?mod n
??????≡??x1?*?x2?* ... *?xφ(n)?mod n
????? 對比等式的左右兩端，因為?xi? (1 ≤ i ≤ φ(n)) 與 n 互質，所以?aφ(n)??≡? 1 mod n （消去律）。
注：
消去律：如果 gcd(c,p) = 1 ，則 ac ≡ bc mod p ? a ≡ b mod p 。

費馬定理 ：
若正整數 a 與素數 p 互質，則有?ap - 1?≡ 1 mod p?。
證明這個定理非常簡單，由于 φ(p) = p -1，代入歐拉定理即可證明。

參考來源：
http://zhidao.baidu.com/question/15882452.html?si=2

》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》

補充：歐拉函數公式

( 1 ) pk?的歐拉函數

對于給定的一個素數 p ， φ(p) = p -1。則對于正整數 n = pk?，

φ(n) = pk - pk -1證明：小于 pk 的正整數個數為 pk - 1個，其中和 pk 不互質的正整數有{p * 1,p * 2,...,p * (pk - 1-1)} 共計 pk - 1 - 1 個所以 φ(n) = pk - 1 - (pk - 1 - 1) = pk - pk - 1 。

( 2 ) p * q 的歐拉函數

假設 p, q是兩個互質的正整數，則 p * q 的歐拉函數為

φ(p * q) = φ(p) * φ(q) ， gcd(p, q) = 1 。

證明：令 n = p * q ， gcd(p,q) = 1根據中國余數定理，有Zn 和 Zp × Zq 之間存在一一映射 （我的想法是： a ∈ Zp ， b ∈ Zq ? b * p + a * q ∈ Zn 。）所以 n 的完全余數集合的元素個數等于集合 Zp × Zq 的元素個數。而后者的元素個數為 φ(p) * φ(q) ，所以有φ(p * q) = φ(p) * φ(q) 。

( 3 ) 任意正整數的歐拉函數

任意一個整數 n 都可以表示為其素因子的乘積為：

In = ∏ piki (I 為 n 的素因子的個數) i=1

根據前面兩個結論，很容易得出它的歐拉函數為：

I IΦ(n) = ∏ piki -1(pi -1) = n ∏ (1 - 1 / pi)i=1 i=1

對于任意 n > 2，2 | Φ(n) ,因為必存在??pi?-1?是偶數。

程序代碼可參見：http://blog.csdn.net/Rappy/archive/2007/08/16/1747489.aspx

?

轉自https://blog.csdn.net/hillgong/article/details/4214327

?

總結

以上是生活随笔為你收集整理的ACM - 欧拉函数（内容）的全部內容，希望文章能夠幫你解決所遇到的問題。

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