INFO

若无特殊说明，本章涉及的变量皆为正整数。

定义

$n$ 的欧拉函数为 $[1,\phantom{0}$$\phantom{0}n]$ 中与 $n$ 互质的数的个数，记为 $\phi (n)$。特别地，$\phi (1)=\phantom{0}$$\phantom{0}1$。

性质

质数的欧拉函数

$p$ 为质数，则 $\phi (p)=\phantom{0}$$\phantom{0}p-\phantom{0}$$\phantom{0}1$。

证

$p$ 与 $[1,\phantom{0}$$\phantom{0}p-\phantom{0}$$\phantom{0}1]$ 中的每个数互质。

$p^k$ 的欧拉函数

$p$ 为质数，$n=\phantom{0}$$\phantom{0}{p}^k$，则 $\phi (n)=\phantom{0}$$\phantom{0}{p}^k-\phantom{0}$$\phantom{0}{p}^{k-1}$。

证

在 $[1,\phantom{0}$$\phantom{0}n]$ 中，只有 $p$ 的倍数不与 $n=\phantom{0}$$\phantom{0}{p}^k$ 互质。

$\because [1,\phantom{0}$$\phantom{0}n]$ 中 $p$ 的倍数有 ${\displaystyle \frac{n}{p}}=\phantom{0}$$\phantom{0}{\displaystyle \frac{p^k}{p}}=\phantom{0}$$\phantom{0}{p}^{k-1}$ 个，

$\therefore \phi (n)=\phantom{0}$$\phantom{0}n-\phantom{0}$$\phantom{0}{p}^{k-1}=\phantom{0}$$\phantom{0}{p}^k-\phantom{0}$$\phantom{0}{p}^{k-1}$。

通项公式

$n$ 有 $m$ 个质因子 $p_1\cdots p_m$，则 ${\displaystyle \phi (n)=\phantom{0}}$$\phantom{0}n\prod _{i=1}^m(1-\frac{1}{p_i})$。

证

若 $n$ 有质因子 $p$，则 $p$ 的倍数不与 $n$ 互质。

$[1,\phantom{0}$$\phantom{0}n]$ 中 $p$ 的倍数有 $\frac{n}{p}$ 个，则剩下的 $n-\phantom{0}$$\phantom{0}\frac{n}{p}=\phantom{0}$$\phantom{0}n\cdot (1-\phantom{0}$$\phantom{0}\frac{1}{p})$ 个数不是 $p$ 的倍数。也就是说，这 $n$ 个数中，非 $p$ 的倍数占比为 $1-\phantom{0}$$\phantom{0}\frac{1}{p}$。

根据定义，$[1,\phantom{0}$$\phantom{0}n]$ 中有 $\phi (n)$ 个数不是 $p_1\cdots p_m$ 的倍数（即与 $n$ 互质）。由乘法原理得：

$$\phi (n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots (1-\frac{1}{p_m})=n\prod _{i=1}^m(1-\frac{1}{p_i})$$

积性函数

$n,\phantom{0}$$\phantom{0}m$ 互质，则 $\phi (nm)=\phantom{0}$$\phantom{0}\phi (n)\cdot \phi (m)$。

证

设 $n$ 有 $x$ 个质因子 $p_1\cdots p_x$，

设 $m$ 有 $y$ 个质因子 $q_1\cdots q_y$，

$\because n,\phantom{0}$$\phantom{0}m$ 互质，$\therefore n,\phantom{0}$$\phantom{0}m$ 的质因子互不相同。

$\therefore nm$ 有 $x+\phantom{0}$$\phantom{0}y$ 个质因子 $p_1\cdots p_x,\phantom{0}$$\phantom{0}{q}_1\cdots q_y$。

由 $\phi$ 函数的通项公式可得：

$$\begin{array}{rl}\phi (n)\cdot \phi (m)& =n\prod _{i=1}^x(1-\frac{1}{p_i})\cdot m\prod _{i=1}^y(1-\frac{1}{q_i})\\ & =nm\prod _{i=1}^x(1-\frac{1}{p_i})\prod _{i=1}^y(1-\frac{1}{q_i})\\ & =\phi (nm)\end{array}$$

定理

欧拉定理

若 $a,\phantom{0}$$\phantom{0}n$ 互质，则 $a^{\phi (n)}\equiv 1(\mathrm{mod}n)$。

证

设 $C=\phantom{0}$$\phantom{0}\{C_1,C_2,\cdots ,C_{\phi (n)}\}$ 为模 $n$ 的 简化剩余系。

设 $aC=\phantom{0}$$\phantom{0}\{a{C}_1,a{C}_2,\cdots ,a{C}_{\phi (n)}\}$，即 $C$ 中的每个元素乘 $a$。

引理 1

由 剩余系 的定义得：

$$\mathrm{\forall }i\ne j,C_i\not\equiv C_j(\mathrm{mod}n)$$

$\because a,\phantom{0}$$\phantom{0}n$ 互质，由同余的 同乘性 可知：

$$\mathrm{\forall }i\ne j,a{C}_i\not\equiv a{C}_j(\mathrm{mod}n)$$

$\therefore aC$ 为模 $n$ 的剩余系。

引理 2

$\because a,\phantom{0}$$\phantom{0}n$ 互质，根据 欧几里得算法 有：

$$\gcd (a,n)=\gcd (n,amodn)=1$$

$\therefore amodn$ 也与 $n$ 互质。

根据 简化剩余系 的定义可知：

$$amodn\in C$$

$\because$ 简化剩余系满足 乘法封闭 性质，所以：

$$\{\begin{array}{l}amodn\in C\\ C_i\in C\end{array}\iff (amodn)\cdot C_{i}modn\in C\iff a{C}_{i}modn\in C$$

$\therefore a{C}_{i}modn$ 与 $n$ 互质，即 $aC$ 中的任意元素模 $n$ 后与 $n$ 互质。

结合引理 $1$、引理 $2$ 可知 $aC$ 也为 $n$ 的简化剩余系。

显然，$C$ 的所有元素之积和 $aC$ 的所有元素之积模 $n$ 同余，即：

$$\prod _{i=1}^{\phi (n)}{C}_i\equiv \prod _{i=1}^{\phi (n)}a{C}_i(\mathrm{mod}n)$$$$\prod _{i=1}^{\phi (n)}{C}_i\equiv a^{\phi (n)}\cdot \prod _{i=1}^{\phi (n)}{C}_i(\mathrm{mod}n)$$$$(a^{\phi (n)}-1)\prod _{i=1}^{\phi (n)}{C}_i\equiv 0(\mathrm{mod}n)$$

$\because C$ 中的所有元素模 $n$ 后与 $n$ 互质，所以：

$$\prod _{i=1}^{\phi (n)}{C}_i\not\equiv 0(\mathrm{mod}n)$$

$\therefore a^{\phi (n)}-\phantom{0}$$\phantom{0}1\equiv 0(\mathrm{mod}n)$，即 $a^{\phi (n)}\equiv 1(\mathrm{mod}n)$。

费马小定理

若 $p$ 为质数，则 $a^{p-1}\equiv a(\mathrm{mod}p)$。

证

当 $p\mid a$ 时，费马小定理显然成立，故只需讨论 $p\nmid a$ 的情况。

当 $p\nmid a$ 时，$\because p$ 是质数 $\therefore a,\phantom{0}$$\phantom{0}p$ 没有公因数（即 $a,\phantom{0}$$\phantom{0}p$ 互质）。根据 欧拉定理 有：

$$a^{\phi (p)}\equiv 1(\mathrm{mod}p)$$

$\because p$ 为质数，由 性质 可知 $\phi (p)=\phantom{0}$$\phantom{0}p-\phantom{0}$$\phantom{0}1$。代入上式：

$$a^{p-1}\equiv 1(\mathrm{mod}p)$$

即证。

扩展欧拉定理

若 $a,\phantom{0}$$\phantom{0}n$ 互质，则对于任意 $b$，有 $a^b\equiv a^{bmod\phi (n)}(\mathrm{mod}n)$。

证

设 $bmod\phi (n)=\phantom{0}$$\phantom{0}q$，则 $b$ 可以表示为 $k\cdot \phi (n)+\phantom{0}$$\phantom{0}q$. 代入 $a^b$ 得：

$$a^b=a^{k\cdot \phi (n)+q}=(a^{\phi (n)}{)}^k\cdot a^q$$

根据 欧拉定理，当 $a,\phantom{0}$$\phantom{0}n$ 互质时，有：

$$a^{\phi (n)}\equiv 1(\mathrm{mod}n)$$

由同余的 同幂性、同乘性 可知：

$$(a^{\phi (n)}{)}^k\equiv 1^k=1(\mathrm{mod}n)$$$$(a^{\phi (n)}{)}^k\cdot a^q\equiv a^q(\mathrm{mod}n)$$$$a^b\equiv a^q(\mathrm{mod}n)$$

即 $a^b\equiv a^{bmod\phi (n)}(\mathrm{mod}n)$。

模板

欧拉函数

int varphi(int n) {
    int ans = n;
    for (int i = 2; i <= sqrt(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;
}

线性欧拉算法

求 $1\cdots n$ 的欧拉函数。

对质数的 线性筛法 加以改造。

• 若 $i$ 为质数，则 $\phi (i)=\phantom{0}$$\phantom{0}i-\phantom{0}$$\phantom{0}1$；
• 利用 $i$ 和 $prim{e}_j$ 生成合数时，利用 积性函数 性质：

$$\phi (i\cdot prim{e}_j)=\phi (i)\cdot \phi (prim{e}_j)$$

时间复杂度为 $O(n)$。

const int N = 1e6;
int phi[N];
vector<int> prime;

void varphi(int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; i ++) {
        if (!phi[i])
            phi[i] = i - 1, prime.push_back(i);
        for (int j = 0; j < prime.size(); j ++) {
            if (i * prime[j] > n) break;
            phi[i * prime[j]] = phi[i] * phi[prime[j]]; // 积性函数
            if (i % prime[j] == 0) break;
        }
    }
}