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}
