5.4.4 费马定理、欧拉定理和威尔逊定理

1. 欧拉函数

对于每个正整数 $m$ ,我们可以确定当 $0\le x\le m$ 时与 $m$ 互素的整数 $x$ 的个数. 对应的函数 $\phi$ 称为欧拉函数. 函数 $\phi \left(m\right)$ 的值是与 $m$ 互素的剩余类的个数 (参见第 505 页 5.4.3, 4.).

例如, $\phi \left(1\right)=1,\phi \left(2\right)=1,\phi \left(3\right)=2,\phi \left(4\right)=2,\phi \left(5\right)=4,\phi \left(6\right)=2,\phi \left(7\right)=$ $6,\phi \left(8\right)=4$ ,等等. 一般地,对于每个素数 $p$ 有 $\phi \left(p\right)=p-1$ ,并且对于每个素数幂 $p^{\alpha }$ 有 $\phi \left(p^{\alpha }\right)=p^{\alpha }-p^{\alpha -1}$ . 如果 $m$ 是一个任意正整数,那么 $\phi \left(m\right)$ 可以用下列方式

确定:

$$\begin{array}{}\text{(5.261a)}& \phi \left(m\right)=m\prod _{p\mid m}\left(1-\frac{1}{p}\right),\end{array}$$

其中乘积应用于 $m$ 的所有素因子.

$$\phi \left(360\right)=\phi \left(2^3\cdot 3^2\cdot 5\right)=360\cdot \left(1-\frac{1}{2}\right)\cdot \left(1-\frac{1}{3}\right)\cdot \left(1-\frac{1}{5}\right)=96.$$

此外还有

$$\begin{array}{}\text{(5.261b)}& \sum _{d\mid m}\phi \left(d\right)=m\end{array}$$

如果 $gcd\left(m,n\right)=1$ ,那么我们有 $\phi \left(mn\right)=\phi \left(m\right)\phi \left(n\right)$ .$\phi \left(360\right)=\phi \left(2^3\cdot 3^2\cdot 5\right)=4\cdot 6\cdot 4=96.$

2. 费马-欧拉定理

费马-欧拉定理是初等数论中最重要的定理之一. 如果 $a$ 和 $m$ 是互素正整数, 那么

$$\begin{array}{}\text{(5.262)}& a^{\phi \left(m\right)}\equiv 1\left(m\right).\end{array}$$

确定 $9^{9^9}$ 的十进制表示中最后三位数字. 这意味着确定 $x$ 使得 $x\equiv 9^{9^9}\left(1000\right)$ , 并且 $0\le x\le 999$ . 现在有 $\phi \left(1000\right)=400$ ,并且依据费马定理, $9^{400}\equiv 1\left(1000\right)$ . 此外还有 $9^9={(80+1)}^4\cdot 9\equiv \left(\left(\begin{array}{l}4\\ 0\end{array}\right){80}^0\cdot 1^4+\left(\begin{array}{l}4\\ 1\end{array}\right){80}^1\cdot 1^3\right)\cdot 9=\left(1+4\cdot 80\right)\cdot 9\equiv$ $-79\cdot 9\equiv 89\left(400\right)$ . 由此推出 $9^{9^9}\equiv 9^{89}={(10-1)}^{89}\equiv \left(\begin{array}{c}89\\ 0\end{array}\right){10}^0\cdot {(-1)}^{89}+\left(\begin{array}{c}89\\ 1\end{array}\right){10}^1$ .${(-1)}^{88}+\left(\begin{array}{c}89\\ 2\end{array}\right){10}^2\cdot {(-1)}^{87}=-1+89\cdot 10-3916\cdot 100\equiv -1-110+400=289\left(1000\right).$因此 $9^{9^9}$ 的十进制表示以数字 289 结尾.

注 当 $m=p$ 时上述定理 (即 $\phi \left(p\right)=p-1$ ) 是费马证明的; 一般形式是欧拉证明的. 这个定理形成译码格式的基础 (见 5.4.6). 它含有正整数的素数性质的一个必要性判据: 如果 $p$ 是素数,那么对于每个 $p\nmid a$ 的整数 $a$ 有 $a^{p-1}\equiv 1\left(p\right)$ .

3. 威尔逊定理

还有其他的素数判别法, 称作威尔逊定理:

每个素数 $p$ 满足 $\left(p-1\right)!\equiv -1\left(p\right)$ .

逆命题也正确; 因而有:

数 $p$ 是素数,当且仅当 $\left(p-1\right)!\equiv -1\left(p\right)$ .