源地址:
http://www.shnenglu.com/zoyi-zhang/articles/43456.html 歐拉函數(shù) :歐拉函數(shù)是數(shù)論中很重要的一個(gè)函數(shù),歐拉函數(shù)是指:對(duì)于一個(gè)正整數(shù) n ,小于 n 且和 n 互質(zhì)的正整數(shù)(包括 1)的個(gè)數(shù),記作 φ(n) 。 完全余數(shù)集合:定義小于 n 且和 n 互質(zhì)的數(shù)構(gòu)成的集合為 Zn ,稱呼這個(gè)集合為 n 的完全余數(shù)集合。 顯然 |Zn| =φ(n) 。有關(guān)性質(zhì):對(duì)于素?cái)?shù) p ,φ(p) = p -1 。對(duì)于兩個(gè)不同素?cái)?shù) p, q ,它們的乘積 n = p * q 滿足 φ(n) = (p -1) * (q -1) 。這是因?yàn)?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) 。歐拉定理 :對(duì)于互質(zhì)的正整數(shù) a 和 n ,有 aφ(n) ≡ 1 mod n 。證明:
( 1 ) 令 Zn = {x
1, x
2, ..., x
φ(n)}
, S = {a * x
1 mod n, a * x
2 mod n, ... , a * x
φ(n) mod n}
, 則 Zn = S 。 ① 因?yàn)?a 與 n 互質(zhì), x
i (1 ≤ i ≤ φ(n)) 與 n 互質(zhì), 所以 a * x
i 與 n 互質(zhì),所以 a * x
i mod n ∈ Zn 。 ② 若 i ≠ j , 那么 x
i ≠ x
j,且由 a, n互質(zhì)可得 a * x
i mod n ≠ a * x
j mod n (消去律)。( 2 ) a
φ(n) * x
1 * x
2 *... * x
φ(n) mod n
≡ (a * x
1) * (a * x
2) * ... * (a * x
φ(n)) mod n
≡ (a * x
1 mod n) * (a * x
2 mod n) * ... * (a * x
φ(n) mod n) mod n
≡ x
1 * x
2 * ... * x
φ(n) mod n
對(duì)比等式的左右兩端,因?yàn)?nbsp;x
i (1 ≤ i ≤ φ(n)) 與 n 互質(zhì),所以 a
φ(n) ≡ 1 mod n (消去律)。
注:
消去律:如果 gcd(c,p) = 1 ,則 ac ≡ bc mod p ⇒ a ≡ b mod p 。
費(fèi)馬定理 :若正整數(shù) a 與素?cái)?shù) p 互質(zhì),則有
ap - 1 ≡ 1 mod p 。
證明這個(gè)定理非常簡(jiǎn)單,由于 φ(p) = p -1,代入歐拉定理即可證明。*****************************************************************************
補(bǔ)充:歐拉函數(shù)公式
( 1 ) pk 的歐拉函數(shù)
對(duì)于給定的一個(gè)素?cái)?shù) p , φ(p) = p -1。則對(duì)于正整數(shù) n = pk ,
φ(n) = pk - pk -1
證明:
小于 pk 的正整數(shù)個(gè)數(shù)為 pk - 1個(gè),其中
和 pk 不互質(zhì)的正整數(shù)有{p * 1,p * 2,...,p * (pk - 1-1)} 共計(jì) pk - 1 - 1 個(gè)
所以 φ(n) = pk - 1 - (pk - 1 - 1) = pk - pk - 1 。
( 2 ) p * q 的歐拉函數(shù)
假設(shè) p, q是兩個(gè)互質(zhì)的正整數(shù),則 p * q 的歐拉函數(shù)為
φ(p * q) = φ(p) * φ(q) , gcd(p, q) = 1 。
證明:
令 n = p * q , gcd(p,q) = 1
根據(jù)中國(guó)余數(shù)定理,有
Zn 和 Zp × Zq 之間存在一一映射
(我的想法是: a ∈ Zp , b ∈ Zq ⇔ b * p + a * q ∈ Zn 。)
所以 n 的完全余數(shù)集合的元素個(gè)數(shù)等于集合 Zp × Zq 的元素個(gè)數(shù)。
而后者的元素個(gè)數(shù)為 φ(p) * φ(q) ,所以有
φ(p * q) = φ(p) * φ(q) 。
( 3 ) 任意正整數(shù)的歐拉函數(shù)
任意一個(gè)整數(shù) n 都可以表示為其素因子的乘積為:
I
n = ∏ piki (I 為 n 的素因子的個(gè)數(shù))
i=1
根據(jù)前面兩個(gè)結(jié)論,很容易得出它的歐拉函數(shù)為:
I I
Φ(n) = ∏ piki -1(pi -1) = n ∏ (1 - 1 / pi)
i=1 i=1
對(duì)于任意 n > 2,2 | Φ(n) ,因?yàn)楸卮嬖?nbsp; pi -1 是偶數(shù)。
posted on 2012-04-11 07:11
luis 閱讀(973)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
組合數(shù)學(xué)