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，都有
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)呗。
四、欧拉定理证明
（缓一缓。。。。。(¯﹃¯)咱们继续）
设 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)
得证。┐(´∇｀)┌
六、应用
线性筛（欧拉筛），日后更新。。。