欧拉函数和欧拉定理

ycw123 · 2021-08-15 17:00:56 · 个人记录

欧拉函数和欧拉定理

欧拉函数的定义

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

比如说 \varphi(1)=1。

当 n 是质数的时候，显然有 \varphi(n)=n-1。

欧拉函数的一些性质&结论

欧拉函数是积性函数

不知道积性函数？点这里。

证明：如果 $gcd(k,n)=d$，那么 $gcd\left(\displaystyle\frac{k}{d},\frac{n}{d} \right)=1,(k<n)
如果我们设 f(x) 表示 gcd(k,n)=x 的数的个数，那么 n=\displaystyle\sum_{i=1}^n f(i)。

根据上面的证明，我们发现 f(x)=\varphi\left(\displaystyle\frac{n}{x}\right)，

从而 n=\displaystyle\sum_{i=1}^n \varphi\left(\displaystyle\frac{n}{x}\right)。

注意到约数 d 和 \displaystyle\frac{n}{d} 具有对称性，所以上式化为 n=\displaystyle\sum_{d|n}\varphi(d)。
若 n = p^k，其中 p 是质数，那么 \varphi(n)=p^k-p^{k-1}=p^{k-1} \times (p-1)。

证明：显然对于从 1 到 p^k 的所有数中，除了 p^{k-1} 个 p 的倍数以外其它数都与 p^k 互素，故 \varphi(n)=p^k-p^{k-1}=p^{k-1} \times (p-1)，证毕。
由唯一分解定理，设 n=\displaystyle\prod_{i=1}^s p_i^{k_i}，其中 p_i 是质数，有 \varphi(n)=n \times \displaystyle\prod_{i=1}^s(1-\frac{1}{p})。

证明：
- 引理：设 p 为任意质数，那么 \varphi(n)=p^{k-1} \times (p-1)。
\varphi(n) = \displaystyle\prod_{i=1}^{s} \varphi(p_i^{k_i}) = \prod_{i=1}^s(p_i-1)p_i^{k_i-1} = \prod_{i=1}^sp_i^{k_i} \times (1-\frac{1}{p_i}) = n\displaystyle\prod_{i=1}^s(1-\frac{1}{p_i})

如何求欧拉函数值

如果只要求一个数的欧拉函数值，那么直接根据定义质因数分解的同时求就好了。

int 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;
}

如果是多个数的欧拉函数值，可以利用线性筛法来求得。

void pre() {
  memset(isprime, 1, sizeof(isprime));
  int cnt = 0;
  isprime[1] = 0;
  phi[1] = 1;
  for (int i = 2; i <= 5000000; i++) {
    if (isprime[i]) {
      prime[++cnt] = i;
      phi[i] = i - 1;
    }
    for (int j = 1; j <= cnt && i * prime[j] <= 5000000; j++) {
      isprime[i * prime[j]] = 0;
      if (i % prime[j])
        phi[i * prime[j]] = phi[i] * phi[prime[j]];
      else {
        phi[i * prime[j]] = phi[i] * prime[j];
        break;
      }
    }
  }
}

欧拉定理

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

若 gcd(a,m)=1，则 a^{\varphi(m)} \equiv 1 \pmod m。

证明：

证明转载自M_lear

记小于 n 且与 n 互质的正整数集合为

R=\{x_1,x_2, \cdots ,x_{\varphi(n)}\}

令

S=\{ax_1 \% n,ax_2 \% n, \cdots ,ax_{\varphi(n)} \% n\}

\forall i \in [1,\varphi(n)]

\because gcd(a,n)=1,gcd(x_i,n)=1

\therefore gcd(ax_i,n)=1

由最大公约数的性质可得 gcd(ax_i \% n,n)=1

所以 S 中的所有元素都与 n 互质，且都小于 n。又 S 中无重复元素

假设 i \not = j,ax_i \% n= ax_j \% n

即 ax_i \equiv ax_j，又 gcd(a,n) = 1

$\therefore S=R

\therefore \displaystyle\prod_{i=1}^{\varphi(n)} ax_i \equiv \prod_{i=1}^{\varphi(n)} x_i \pmod{n}

\therefore a^{\varphi(n)}\displaystyle\prod_{i=1}^{\varphi(n)} x_i \equiv \prod_{i=1}^{\varphi(n)} x_i \pmod{n}

\because gcd\left(\displaystyle\prod_{i=1}^{\varphi(n)} x_i,n\right)=1

\therefore a^{\varphi(n)} \equiv 1 \pmod{n}