欧拉定理的内容证明及欧拉函数的推导"/>

欧拉定理的内容证明及欧拉函数的推导

欧拉定理的内容证明及欧拉函数的推导

内容

aφ(n)≡1(modn) $$a^φ(n)≡1 (mod n)$$
其中φ(n)是欧拉函数，下面是关于φ(n)的求法

φ(n)的求法

φ(n)就是求[1,n]的区间与n互质的数的个数。
我们可以先用容斥的思想考虑这个问题：
1.n可以分解成若干个质因子相乘的形式，形如

n=p1a1+p2a2+p3a3+…+pkak $$n=p1^a1+p2^a2+p3^a3+…+pk^ak$$
2.显然 φ(n)=φ(p1a1)∗φ(p2a2)∗…∗φ(pkak) $$φ(n)= φ(p1^a1)* φ(p2^a2)*…*φ(pk^ak)$$
3.很明显存在φ(pi)=pi-1，那么φ(pi^ai)就等于pi^ai减去[1，pi^ai]区间中pi的倍数，那么
φ(piai)=piai−piai/pi=piai−pi(ai−1)=piai(1−1/pi) $$φ(pi^{ai}) =pi^{ai}-pi^{ai}/pi =pi^{ai}-pi^({ai}-1) =pi^{ai}(1-1/pi)$$
各项相乘可得 φ(n)=n∗(1−1/p1)∗(1−1/p2)∗…∗(1−1/pk) $$φ(n)=n*(1-1/p1)*(1-1/p2)*…*(1-1/pk)$$
即对n进行大合数分解，所以效率为O(n^0.5)。

证明

先假定集合Z包含[1,n]的区间与n互质的数{x1,x2,x3…xφ(n)}
集合

S={a*x1%n,a*x2%n,a*x3%n…a*xφ(n)%n} $$S={a*x1%n,a*x2%n,a*x3%n…a*xφ(n)%n}$$
可得Z=S，下面给出证明：
因为(a,n)=1,(xi,n)=1,所以(a*xi,n)=1，通过辗转相除法(a*xi,n)=(n,a*xi%n)=1,写成(a*xi%n,n)=1。
在S集合中，若i≠j,则xi≠xj (mod n),a*xi≠a*xj (mod n),这个可以通过公式ca≡cb (mod m) (其中(c,n)=1) a≡b (mod m)反证得出。
既然(a*xi%n,n)=(xi,n)=1,并且长度相等，那么必有Z=S。
我们可以得出一个等式:
aφ(n)x1x2x3…xφ(n))(modn) $$a^φ(n)x1x2x3…xφ(n)) (mod n)$$
=x1ax2ax3a…xφ(n)a(modn)//乘法分配律=ax1 $$=x1ax2ax3a…xφ(n)a (mod n) //乘法分配律 =ax1%n*a*x2%n*a*x3%n...a*xφ(n)%n //分步mod$$
=x1x2x3…xφ(n)//因为Z=S $$=x1x2x3…xφ(n) //因为Z=S$$
得证aφ(n)≡1(modn) $$得证a^φ(n)≡1 (mod n)$$

拓展

费马小定理
当a是不能被质数p整除的正整数，则有

a(p−1)≡1(modp) $$a^{(p-1)}≡1 (mod p)$$
因为对于一个质数p，φ(p)=p-1,所以可以用欧拉定理得出，所以欧拉定理是费马小定理的一个拓展。