欧拉函数公式及其证明.doc

欧拉函数 ：欧拉函数是数论中很重要的一个函数，欧拉函数是指：对于一个正整数 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，代入欧拉定理即可证明。*补充：欧拉函数公式( 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 是偶数。/直接求解欧拉函数int euler(int n) /返回euler(n) int res=n,a=n; for(int i=2;i*i1) res=res/a*(a-1); return res;/筛选法打欧拉函数表 #define Max 1000001int eulerMax;void Init() euler1=1; for(int i=2;iMax;i+) euleri=i; fo