费马小定理与欧拉定理

贡献者： int256

预备知识　线性同余，同余与剩余类，欧拉函数（数论），数论求和记号

　　若 $p$ 是素数，且 $p ⧸ ∣ a$ ，则

\begin{matrix} (1) & a^{p - 1} \equiv 1 (\mod p) . \end{matrix}

　　费马小定理只是费马-欧拉定理的一个特例，我们只要证明了费马-欧拉定理就自动证明了费马小定理。其中，费马-欧拉定理是指：

　　若 $(a, m) = 1$ ，则

\begin{matrix} (2) & a^{φ (m)} \equiv 1 (\mod m), \end{matrix}

其中

φ (m)

是

m

的欧拉函数。

　　证明：考虑 $h$ 取遍 $m$ 的一个缩系，则由于 $(a, m) = 1$ ，利用定理 2 ， $a h$ 也将取遍 $m$ 的一个缩系。这就使得

\begin{matrix} (3) & \prod_{h^{*} (m)} a h \equiv \prod_{h^{*} (m)} h (\mod m), \end{matrix}

此处记号使用数论求和的记号，

h^{*} (m)

代表

h

枚举

m

的一个缩系。这式子也就指出

\begin{matrix} (4) & a^{φ (m)} \prod_{h^{*} (m)} h \equiv \prod_{h^{*} (m)} h (\mod m), \end{matrix}

而由于

h

取

m

的缩系，故每个

h

都与

m

互质，这必将导致他们的乘积也与

m

互质，从而使得有

\begin{matrix} (5) & a^{φ (m)} \equiv 1 (\mod m) . \end{matrix}

证毕！