欧拉函数的定义

欧拉函数（Euler’s totient function），即 φ(n)，表示的是小于等于 n 和 n 互质的数的个数。

比如说 φ(1)=1。

φ(8)=4，小于 8 且与 8 互素的数是 1,3,5,7。

当 n 是质数的时候，显然有 φ(n)=n−1。

欧拉函数的一些性质

• 欧拉函数是积性函数。

  积性是什么意思呢？如果有 gcd(a,b)=1，那么 φ(a×b)=φ(a)×φ(b)。

  特别地，当 n 是奇数时 φ(2n)=φ(n)。

• n=∑d∣nφ(d)。

  利用 莫比乌斯反演 相关知识可以得出。

  也可以这样考虑：如果 gcd(k,n)=d，那么 （）gcd(kd,nd)=1,（k<n）。

  如果我们设 f(x) 表示 gcd(k,n)=x 的数的个数，那么 n=∑i=1nf(i)。

  根据上面的证明，我们发现，f(x)=φ(nx)，从而 n=∑d∣nφ(nd)。注意到约数 d 和 nd 具有对称性，所以上式化为 n=∑d∣nφ(d)。

• 若 n=pk，其中 p 是质数，那么 φ(n)=pk−pk−1。
  （根据定义可知）

• 由唯一分解定理，设 n=∏i=1npiki，其中 pi 是质数，有 φ(n)=n×∏i=1spi−1pi。

  • 引理：设 p 为任意质数，那么 φ(pk)=pk−1×(p−1)。

    证明：显然对于从 1 到 pk 的所有数中，除了 pk−1 个 p 的倍数以外其它数都与 pk 互素，故 φ(pk)=pk−pk−1=pk−1×(p−1)，证毕。

    接下来我们证明 φ(n)=n×∏i=1spi−1pi。由唯一分解定理与 φ(x) 函数的积性

φ(n)=∏i=1sφ(piki)=∏i=1s(pi−1)×piki−1=∏i=1spiki×(1−1pi)=n∏i=1s(1−1pi)◻

如何求欧拉函数值

基于素因数分解求欧拉函数的算法

如果只要求一个数的欧拉函数值，那么直接根据定义质因数分解的同时求就好了。这个过程可以用 Pollard Rho 算法优化。

int euler_phi(int n) {
  int m = int(sqrt(n + 0.5));
  int ans = n;
  for (int i = 2; i <= m; i++)
    if (n % i == 0) {
      ans = ans / i * (i - 1);
      while (n % i == 0) n /= i;
    }
  if (n > 1) ans = ans / n * (n - 1);
  return ans;
}

注：如果将上面的程序改成如下形式，会提升一点效率：

int euler_phi(int n) {
  int ans = n;
  for (int i = 2; i * i <= n; i++)
    if (n % i == 0) {
      ans = ans / i * (i - 1);
      while (n % i == 0) n /= i;
    }
  if (n > 1) ans = ans / n * (n - 1);
  return ans;
}

利用埃氏筛法，实现欧拉函数值的预处理

可以求多个数的欧拉函数。

利用埃氏筛法，每次发现素因子时就把它的倍数的欧拉函数乘上 (p-1)/p ，这样就可以一次性求出 1~n 的欧拉函数值的表了。实现如下:

1  int euler[MAX_N];
2  void euler_phi2(){
3	for (int i = 0; i < MAX_N; i++) euler[i] = i;
4	for (int i = 2; i < MAX_N; i++) {
5		if (euler[i] == i) {
6			for (int j = i; j < MAX_N; j += i) 
7				euler[j] = euler[j] / i * (i - 1);
8		}
9	}
10 }

容斥原理求欧拉函数

若将 N 分解为不同素数的乘积，即：

N=p1r1p2r2…pkrk

设 1 到 N 的 N 个数中为 pi 倍数的集合为 Ai,|Ai|=|Npi|(i=1,2,…,k) 。

对于 pi≠pj,Ai∩Aj 既是 pi 的倍数也是 pj, 的倍数，即可得

|Ai∩Aj|=∣Npipj⌋(1≤i,j≤k,i≠j)

人在去除 |Ai| 和 |Aj| 的时候， pi 和 pj 的倍数被去除去了两次，需要再把 |Ai∩Aj| 加回来。

φ(N)=|A1―∩A2―∩⋯∩Ak―|=N−(Np1+Np2+⋯+Npk)+(Np1p2+Np2p3+⋯+Np1pk)…±(Np1p2…pk)=N(1−1p1)(1−1p2)…(1−1pk)

与欧拉函数紧密相关的一个定理就是欧拉定理。其描述如下：

若 gcd(a,m)=1，则 aφ(m)≡1(modm)。

扩展欧拉定理

当然也有扩展欧拉定理

ab≡{abmodφ(p),,gcd(a,,p)=1ab,gcd(a,,p)≠1,,b<φ(p)abmodφ(p)+φ(p),gcd(a,,p)≠1,,b≥φ(p)(modp)