欧拉函数:对于一个正整数n,小于n且和n互质的正整数(包括1)的个数,记作φ(n) 。 通式:φ(x)=x*(1-1/p1)(1-1/p2)(1-1/p3)*(1-1/p4)......(1-1/pn),其中p1, p2......pn为x的所有质因数。φ(1)=1(唯一和1互质的数就是1本身)。 欧拉定理:对于互质的正整数a和n,有aφ(n) ≡ 1 mod n。 性质: 1.对于质数p,φ(p) = p – 1。注意φ(1)=1. 2.欧拉函数是积性函数——若m,n互质,φ(mn)=φ(m)φ(n)。 3.若n是质数p的k次幂,φ(n)=pk-p(k-1)=(p-1)p^(k-1),因为除了p的倍数外,其