欧拉函数

1. 欧拉函数定义

欧拉函数 ${\phi(n)}$ 表示的是小于等于 $n$ 且和 $n$ 互质的正整数的个数。（易知 ${\phi(1) = 1}$）

2. 欧拉函数公式

对于任意整数 $n$，若其质因数分解结果为 ${n = p_1^{k_1}p_2^{k_1} \cdots p_n^{k_n}}$，则欧拉函数公式为

$$\begin{array}{c} \phi(n) = n(1-{1 \over p_1})(1- {1 \over p_2}) \cdots (1-{1 \over p_n}) \end{array}$$

3. 欧拉函数性质

（1）欧拉函数为积性函数。（对于数论函数 ${f(n)}$ 不恒等于 0，当 ${(m,n) = 1}$ 时，满足 ${f(mn) = f(m)f(n)}$ ，则称 ${f(n)}$ 为积性函数）

$$\begin{array}{c} \phi(mn) = \phi(m)\phi(n), \, (m,n) = 1 \end{array}$$

（2）若 ${(m,n) = d}$，则

$$\begin{array}{c} \phi(mn) = d{\phi(m)\phi(n) \over \phi(d)} \end{array}$$

（3）若 $m$、$n$ 满足 ${m|n}$，则

$$\begin{array}{c} \phi(mn) = m \cdot \phi(n) \end{array}$$

（4）若 $m$、$n$满足 ${m|n}$，则

$$\begin{array}{c} \phi(m)|\phi(n) \end{array}$$

（5）对于质数 $p$，其欧拉函数公式为

$$\begin{array}{c} \phi(p) = p-1 \end{array}$$

（6）对于质数 $p$，${p^k}$的欧拉函数公式为

$$\begin{array}{c} \phi(p^k) = (p-1)p^{k-1} \end{array}$$

（7）小于等于 $n$ 且整除 $n$ 的所有正整数的欧拉函数值之和等于 $n$，即

$$\begin{array}{c} n = \sum_{d|n}\phi(d) \end{array}$$

（8）欧拉定理：若 ${(a,m) = 1}$，则 ${a^{\phi(m)} \equiv 1 \, \pmod{m}}$ 。

（9）扩展欧拉定理

$$\begin{array}{c} a^x \equiv a^{x \bmod \phi(m)} \pmod{m}, (a,m) = 1 \\ a^x \equiv a^x \pmod{m}, (a,m) \neq 1 \wedge x \lt \phi(m) \\ a^x \equiv a^{(x \bmod \phi(m)) + \phi(m)} \pmod{m}, (a,m) \neq 1 \wedge x \geq \phi(m) \end{array}$$