欧拉函数 + 费马小定理

数学

定义

欧拉函数（φ函数）：在数论，对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。

性质

1. φ (1) = 1
2. φ (p) = p - 1
3. 若n是质数p的k次幂，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)。
   

   证明：除了p的倍数外，其他数都跟n互质。
   小于p^k且是p的倍数的分别为p*(1..p^(k-1)-1)，共有p^(k-1)-1个。
   小于p^k的数共有p^k-1个。
   所以φ(n)=p^k-1-(p^(k-1)-1)=p^k-p^(k-1)=(p-1)p^(k-1)。

4. 欧拉函数是积性函数——若m,n互质，φ(mn)=φ(m)φ(n)。

   由此可推出φ(x)[x为任意正整数]：
   φ(n) = φ(p1)...φ(p1)...φ(p2)...φ(pi)
   = φ(p1^k1)...φ(pi^ki)
   = (p1-1)p1^(k1-1)...(pi-1)pi^(ki-1)

5. 特殊性质：当n为奇数时，φ(2n)=φ(n)。因为 φ(2)=1

6. 公式转换：φ(n)=n*(1-1/p1)(1-1/p2)........*(1-1/pi)

7. 与欧拉定理、费马小定理的关系
   　　对任何两个互质的正整数a, m(m>=2)有

   　 > a^φ(m)≡1(mod m)（即欧拉定理）
   　
   　　当m是质数p时，此式则为：
   　　
   　 > a^(p-1)≡1(mod p)（即费马小定理）

   若多次求小于N且与N互质的数，可以先将质数筛选出来，再将N分解，这样就能快速地求出答案。
   下面给出求1..N的φ函数的code：

    for (i = 1; i <= N; i ++) phi[i] = i;
    for (i = 2; i <= N; i ++) {
        if (prime[i]) { //之前先筛选出质数
            for (j = i; j <= N; j += i) 
                phi[j] = phi[j] / i * (i - 1); //此处注意先/i再*（i-1)，否则范围较大时会溢出
        }
    }

以上部分参考自：  [维基百科][1]

费马小定理

1736年，欧拉证明了费马小定理：

> 假若 p 为质数，a 为任意正整数，那么 a^p - a 可被 p 整除。

然后欧拉予以一般化：

> 假若 a 与 n 互质，那么 a^φ(n) - 1 可被 n 整除。亦即，a^φ(n) ≡ 1 (mod n)。
> 其中 φ(n) 即为欧拉总计函数。如果 n 为质数，那么 φ(n) = n - 1，因此，有高斯的版本：
> 假若 p 为质数，a 与 p 互质（a 不是 p 的倍数），那么 a^{p-1} \equiv 1 \pmod p。

参考： blog