EULER::【欧拉定理】木大木大木大!欧拉欧拉欧拉!

P.S.之前写的一篇关于欧拉定理的文章太辣鸡了,于是又重新写了这篇。

 


 

 

一、函数定义

在数论中,对于正整数N,少于或等于N ([1,N]),且与N互质的正整数(包括1)的个数,记作φ(n)。


 

 

二、函数性质

(1)对于一个质数 p,和一个正整数 k。φ(p^k) = p^k-p^(k-1) = (p-1)*p^(k-1)。

(2)m,n互质,φ(m*n) = φ(m)*φ(n)。欧拉函数是积性函数。

(3)对于任意整数 x,都有

EULER::【欧拉定理】木大木大木大!欧拉欧拉欧拉!

P.S.这个式子如果看不懂的话,可以在网上搜索连乘积符号

(4)对于某一奇数 n,φ(2*n) = φ(n)。

(5)对于任意两个互质的数 a,n(n>2),都有 a^φ(n) ≡ 1 (mod n)。此为 欧拉定理

(6)当n=p 且 a与素数p互质(即:gcd(a,p)=1)则上式有: a^(p-1) ≡ 1 (mod n)为 费马小定理


 

三、函数证明

(1)在性质(1)中,很明显,k = 1时,φ(p^k) = φ(p) = p-1。

已知少于 p^k 的正整数的个数为 p^k-1,

其中和 p^k 不互质的正整数有 { p×1,p×2,...,p×(p^(k-1)-1)},共计p^(k-1)-1个,

所以 φ(p^k) = p^k-p^(k-1) = (p-1)*p^(k-1)。

 

(2)关于性质(2)性质,我在网上看到了不少证明,讲的都很不通俗,我在这里就以更易懂的方式说明一下。

对于 m*n,它是 m 和 n 的最小公倍数

与它不互质的数有

{1*n,2*n,3*n.......m*n} 和 {1*m,2*m,3*m.....n*m} 共 m+n-1 个,

所以φ(m*n) = m*n-m-n+1 = (m-1)*(n-1) = φ(m)*φ(n)。

 

(3)对于性质(3)。

众所周知,任意一个整数n都可以表示为其质因子的乘积:

那我们就假设 n = (a[1]*k[1]) * (a[2]*k[2]) * ......* (a[e]*k[e])。

a[] 为 n 的某一质因数,e 为质因数个数,k[i] 为相应的质因数 a[i] 的对应个数。

n*(1-1/a[i])是不是就表示 n 中除去公因数为 a[i] 的数的个数?

那么 n * (1-1/a[1]) * (1-1/a[2]) * (1-1/a[3]) * ... * (1-1/a[e]) 就是 φ(n)呗。


 

四、欧拉定理证明

(缓一缓。。。。。(¯﹃¯)咱们继续)

EULER::【欧拉定理】木大木大木大!欧拉欧拉欧拉!

设 x1 , x2 , x3 ...... xφ(n) 是 1~n 中与 n 互质的数。1<=i<=φ(n)

m1=a*x1,m2=a*x2 ...... mφ(n)=a*xφ(n).

 

1)对于这其中任意两个不相同的数 ms 与 mr 都不模 n 同余,这里用反证法证明:

若 ms≡mr (mod n),咱们假设ms更大。那么ms-mr = a*(xs-xr)

a与n互质,xs-xr<n,因此 a*(xs-xr) 一定无法被 n 整除。

也就是说这 φ(n) 个数 %n 都不同余。

φ(n)个数有φ(n)种余数。a*xi 和 n 互质!

2)那么这些数的余数和 n 的关系又是什么?

这些数除n的余数都与n互质

假设其余数和 n 有公因数 r。

那么 a*xi=pn+qr,n=kr  --->  a*xi=(pk+q)*r.

a*xi 和 n 不互质了!

那么这(指 m 序列)些数%n,都在x1,x2,x3……xφ(n)中,因为这(指 x 序列)是1~n中与n互质的所有数,而余数又小于n。

 

由上得出:

m1*m2*m3……mφ(n) ≡ x1*x2*x3……xφ(n) (mod n)

a^[φ(n)]*(x1*x2*x3……xφ(n)) ≡ x1*x2*x3……xφ(n) (mod n)

设 k = x1*x2*x3……xφ(n)。

a^[φ(n)]*k ≡ k (mod n)

{a^[φ(n)]-1}*k ≡ 0 (mod n)

k 为与 n 互质的数相乘,因而 k 与 n 互质。

也就是只有 {a^[φ(n)]-1} 能被 n 整除时,{a^[φ(n)]-1}*k ≡ 0 (mod n) 才会成立

则:a^[φ(n)]-1 ≡ 0 (mod n)

a^[φ(n)] ≡ 1 (mod n)

得证。


 

 

五、费马小定理证明

a^(p-1) ≡ 1 (mod n)

a^φ(p) ≡ 1 (mod n)

得证。┐(´∇`)┌


 

 

六、应用

线性筛(欧拉筛),日后更新。。。

上一篇:The Euler function 线性筛法求欧拉函数


下一篇:New Citation 20 July 2019