源地址：
http://www.cppblog.com/zoyi-zhang/articles/43456.html 欧拉函数 ：欧拉函数是数论中很重要的一个函数，欧拉函数是指：对于一个正整数 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 = {x
1, x
2, ..., x
φ(n)}
， S = {a * x
1 mod n, a * x
2 mod n, ... , a * x
φ(n) mod n}
， 则 Zn = S 。 ① 因为 a 与 n 互质， x
i (1 ≤ i ≤ φ(n)) 与 n 互质， 所以 a * x
i 与 n 互质，所以 a * x
i mod n ∈ Zn 。 ② 若 i ≠ j ， 那么 x
i ≠ x
j，且由 a, n互质可得 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
对比等式的左右两端，因为 x
i (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，代入欧拉定理即可证明。*****************************************************************************
补充：欧拉函数公式
( 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 都可以表示为其素因子的乘积为：
I
n = ∏ 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 是偶数。
posted on 2012-04-11 07:11
luis 阅读(956)
评论(0) 编辑 收藏 引用 所属分类:
组合数学