• 相关文章 # 欧拉函数：

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

性质：

• 欧拉函数是积性函数。如果有 \(\gcd(a, b) = 1\)，那么 \(\varphi(a \times b) = \varphi(a) \times \varphi(b)\)。特别地，当 \(n\) 是奇数时 \(\varphi(2n) = \varphi(n)\)。

• \(n = \sum_{d \mid n}{\varphi(d)}\)。

• 若 \(n = p^k\)，其中 \(p\) 是质数，那么 \(\varphi(n) = p^k - p^{k - 1}\)。 （根据定义可知）

• 由唯一分解定理，设 \(n = \prod_{i=1}^{s}p_i^{k_i}\)，其中\(p_i\) 是质数，有 \(\varphi(n) = n \times \prod_{i = 1}^s{\dfrac{p_i - 1}{p_i}}\)。

实现：

只要求一个数的欧拉函数值:

#include <cmath>

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

如果是多个数的欧拉函数值: 详见：筛法求欧拉函数

有：

\[\begin{aligned} \varphi(n) & = \varphi(p_1) \times \varphi(n') \\\\ & = (p_1 - 1) \times \varphi(n') \end{aligned}\]

欧拉定理：

欧拉定理 0 \((Euler's theorem)\) 内容：若 \(\gcd(a, m) = 1\)，则 \(a^{\varphi(m)} \equiv 1 \pmod{m}\)。 >费马小定理可以看作当\(m\) 是质数 \(p\) 时欧拉定理的一个特殊情形。

扩展欧拉定理:

扩展欧拉定理内容：

\[a^b \equiv \begin{cases} A^{b \bmod \varphi (m)}, &\gcd (a, m) = 1, \\ A^b, &\gcd (a, m)\ne 1, b < \varphi (m), \\ A^{(b \bmod \varphi (m)) + \varphi (m)}, &\gcd (a, m)\ne 1, b \ge \varphi (m). \end{cases} \pmod m\]