欧拉定理

欧拉函数：

欧拉函数 $(E u l e r^{'} s t o t i e n t f u n c t i o n)$ 内容：即 $φ (n)$ ，表示的是小于等于 $n$ 和 $n$ 互质的数的个数。

性质：

欧拉函数是积性函数。如果有 $gcd (a, b) = 1$ ，那么 $φ (a \times b) = φ (a) \times φ (b)$ 。特别地，当 $n$ 是奇数时 $φ (2 n) = φ (n)$ 。
$n = \sum_{d ∣ n} φ (d)$ 。
若 $n = p^{k}$ ，其中 $p$ 是质数，那么 $φ (n) = p^{k} - p^{k - 1}$ 。（根据定义可知）
由唯一分解定理，设 $n = \prod_{i = 1}^{s} p_{i}^{k_{i}}$ ，其中 $p_{i}$ 是质数，有
$φ (n) = n \times \prod_{i = 1}^{s} \frac{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} φ (n) & = φ (p_{1}) \times φ (n^{'}) \\ = (p_{1} - 1) \times φ (n^{'}) \end{aligned}

欧拉定理：

欧拉定理 0 $(E u l e r^{'} s t h e o r e m)$ 内容：若 $gcd (a, m) = 1$ ，则 $a^{φ (m)} \equiv 1 (\mod m)$ 。

费马小定理可以看作当 $m$ 是质数 $p$ 时欧拉定理的一个特殊情形。

扩展欧拉定理:

扩展欧拉定理内容：

a^{b} \equiv {\begin{cases} A^{b mod φ (m)}, & gcd (a, m) = 1, \\ A^{b}, & gcd (a, m) \neq 1, b < φ (m), \\ A^{(b mod φ (m)) + φ (m)}, & gcd (a, m) \neq 1, b \geq φ (m) . \end{cases} (\mod m)