关于数论中欧拉函数和欧拉定理的简短证明 收藏
一.欧拉函数的证明 1) p^k的欧拉函数 对于给定的一个素数p,我们知道φ(p) = p-1。 假设一个整数n是p的k次幂,也就是 n = p^k,k∈N+ 容易证明 φ(n) = p^k - p^(k-1) 证明: 已知少于小于p^k的正整数个数为p^k-1个,其中 和p^k不互质的正整数有{p×1,p×2,...,p×(p^(k-1)-1)}共计p^(k-1)-1个 所以φ(n) = p^k -1 - (p^(k-1)-1) = p^k - p^(k-1) 2) pq的欧拉函数 假设p,q是两个互质的正整数,则pq的欧拉函数为 φ(pq) = φ(p)φ(q),gcd(p,q)=1 证明: ∵M= pq, gcd(p,q) =1 ∴根据中国余数定理,有 Zm和Zp×Zq之间存在一一映射 所以M的完全余数集中元素的个数等于集合Zp×Zq元素的个数 而后者的元素个数为φ(p)φ(q),所以有 φ(pq) = φ(p)φ(q) 3) 任意正整数的欧拉函数 φ(n)=n∏(1-1/p),其中p为能够被n整除的质数 二.欧拉定理的证明
对于互质的整数a和n,有a^φ(n) ≡ 1 (mod n) 证明: 首先证明下面这个命题: 对于集合Zn={x_1,x_2,...,x_φ(n)},考虑集合 S = {ax_1 mod n,ax_2mod n,...,ax_φ(n)mod n} 则S = Zn 1) 由于a,n互质,x_i也与n互质,则ax_i也一定于n互质,因此 任意x_i,ax_i mod n 必然是Zn的一个元素 2) 对于Zn中两个元素x_i和x_j,如果x_i ≠ x_j 则ax_i mod n ≠ ax_j mod n,这个由a、n互质和消去律可以得出。 所以,很明显,S=Zn 既然这样,那么 (ax_1 × ax_2×...×ax_φ(n))mod n = (ax_1 mod n × ax_2 mod n × ... × ax_φ(n) mod n)mod n = (x_1 × x_2 × ... × x_φ(n))mod n 考虑上面等式左边和右边 左边等于(a^φ(n) × (x_1 × x_2 × ... × x_φ(n))mod n) mod n 右边等于x_1 × x_2 × ... × x_φ(n))mod n 而x_1 × x_2 × ... × x_φ(n))mod n和n互质 根据消去律,可以从等式两边约去,就得到: a^φ(n) ≡ 1 (mod n) 本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/dlyme/archive/2009/04/20/4094446.aspx |
|
来自: bbtingyuge > 《我的图书馆》