Proven for Euler Theorem#

这个证明应该很常见了，我还是写一下，也很简单，对于整数 a 和 m，$(a, m) = 1$，m 的简化剩余系 $R(m) = \{r_1, r_2, ..., r_{\phi(m)}\}$

$(ar_1)(ar_2)\cdots(ar_{\phi(m)}) \equiv a^{\phi(m)}(r_1r_2\cdots r_{\phi(m)})\ (\textrm{mod}\ m)$

而因为 $(a, m) = 1$, 显然有

1. $ar_i \not\equiv 0 \ (\textrm{mod} \ m)$
2. $ar_i \not\equiv ar_j \ (\textrm{mod} \ m), i \ne j$

因此 $b_i = (ar_i\ \textrm{mod} \ m)$ 同样构成了 m 的简化剩余系。

所以 $\prod_{i = 1}^{i = \phi(m)} b_i \equiv \prod_{i = 1}^{i = \phi(m)} r_i \ (\textrm{mod} \ m)$

所以 $\prod_{i = 1}^{i = \phi(m)} r_i \equiv a^{\phi(m)}\prod_{i = 1}^{i = \phi(m)} r_i \ (\textrm{mod} \ m)$

那么 $(a^{\phi(m)} - 1)\prod_{i = 1}^{i = \phi(m)} r_i \equiv 0 \ (\textrm{mod} \ m)$

由 $(r_i, m) = 1$，显然 $a^{\phi(m)} - 1 \equiv 0 \ (\textrm{mod} \ m)$

证毕。

Fermat’s Little Theorem#

欧拉定理的特殊情况。

弱化 1(p, m)#

不妨设 $p = p_1$, 令 $m' = m \ / \ p_1^{k_1}, k = k_1$，显然 $(p^{k}, m') = 1$。

易见，$p^{2\phi(m)} - p^{\phi(m)} \equiv 0 \ (\textrm{mod} \ m')$。

且, $p^{2\phi(m)} - p^{\phi(m)} \equiv 0 \ (\textrm{mod} \ p^k)$，因为 $\phi(m) \ge p^{k - 1}(p - 1) \ge k$ 永远成立。

由中国剩余定理，$(p^{2\phi(m)} - p^{\phi(m)}) \ (\textrm{mod} \ p^k\cdot m')$解存在且唯一，而这里显然是 0.

所以，$p^{2\phi(m)} \equiv p^{\phi(m)} \ (\textrm{mod} \ m)$

弱化 2(a, m)#

假设 $(a, m) \ne 1$，并且质数 p，有 $p | (a,m)$，同上不妨设$p = p_1, k = k_1$, 定义$a = pa_1, m = p^km_1$，我们有

$a^{2\phi(m)} - a^{\phi(m)} = p^{2\phi(m)}a_1^{2\phi(m)} - p^{\phi(m)}a_1^{\phi(m)}$

$= p^{2\phi(m)}a_1^{2\phi(m)} - p^{\phi(m)}a_1^{2\phi(m)} + p^{\phi(m)}a_1^{2\phi(m)} - p^{\phi(m)}a_1^{\phi(m)}$

因此 $a^{2\phi(m)} - a^{\phi(m)} = (p^{2\phi(m)} - p^{\phi(m)})a_1^{2\phi(m)} + p^{\phi(m)}(a_1^{2\phi(m)} -a_1^{\phi(m)})$

$\equiv p^{\phi(m)}(a_1^{2\phi(m)} -a_1^{\phi(m)}) \ (\textrm{mod} \ m)$

即要证明 $p^{\phi(m)}(a_1^{2\phi(m)} -a_1^{\phi(m)}) \equiv 0\ (\textrm{mod} \ m)$，显然即 $a_1^{2\phi(m)} -a_1^{\phi(m)} \equiv 0\ (\textrm{mod} \ m_1)$

如果 $(a_1, m_1) = 1$，即得证，否则 $a_1 < a$，我们总能找到质数 $q | (a_1, m_1)$，然后递降，而 $a_1$ 一定是整数，所以 $a_1 \ge 1$，即存在递降下限 1，而 $(1, m_t) = 1$ 恒成立。

故得证。

最终结论#

由弱化结论 2，很容易得知 $a^{k\phi(m)} \equiv a^{\phi(m)} \ (\textrm{mod} \ m), k \in N^+$，以及 $a^{k\phi(m) + b} \equiv a^{\phi(m) + b} \ (\textrm{mod} \ m), k \in N^+, b \in N, b \le m$，得证。