第 2 章：费马小定理与指数缩减

2.1 定理说了什么

若 $p$ 是质数，且 $p$ 不整除整数 $a$ ，则

$\boxed{a^{p-1}\equiv1\pmod p.}$

质数 $p$ 的非零剩余类都与 $p$ 互质，因此第1章的消去律可以使用。这个条件会在证明最后一步发挥作用。

还有一种包含所有整数 $a$ 的形式： $a^p\equiv a\pmod p$ 。若 $p\nmid a$ ，把第一式乘 $a$ 即可；若 $p\mid a$ ，两边模 $p$ 都为0。反过来，只有在 $p\nmid a$ 时，才能从后一式约去 $a$ ，得到前一式。

2.2 为什么乘法会把非零余数重新排列

考虑非零剩余类 $1,2,\ldots,p-1$ ，把它们分别乘 $a$ 。要证明乘后的余数仍然是这一整组数，只需排除两种情况。

第一，不会出现0。若 $ai\equiv0\pmod p$ ，因为 $a$ 与 $p$ 互质，可以消去 $a$ ，得到 $i\equiv0$ ，与 $1\le i\le p-1$ 矛盾。

第二，不会有两个不同位置产生相同余数。若 $ai\equiv aj\pmod p$ ，消去 $a$ 得到 $i\equiv j$ 。而 $i,j$ 都在 $1$ 至 $p-1$ 之间，同余只能意味着 $i=j$ 。

因此，乘后的 $p-1$ 个余数非零且互不相同；总共只有 $p-1$ 种非零余数，它们必然把原来的整组数全部占满。这里“重新排列”指的就是这件事，并没有增加或丢失余数。

把这组同余相乘，就有

$(a\cdot1)(a\cdot2)\cdots(a\cdot(p-1)) \equiv1\cdot2\cdots(p-1)\pmod p.$

左边含有 $p-1$ 个 $a$ ，所以可写为 $a^{p-1}(p-1)!$ 。两边的 $(p-1)!$ 都与 $p$ 互质，可以消去。剩下的正是 $a^{p-1}\equiv1$ 。

证明的顺序是：互质允许消去 → 乘法没有重复和零 → 整组余数只是重排 → 相乘并消去共同乘积。一般的欧拉定理还会使用同一思路。

2.3 为什么能缩减指数

若 $a^{p-1}\equiv1$ ，把非负整数指数 $m$ 写成

$m=q(p-1)+r,\qquad0\le r<p-1,$

就得到

$a^m=(a^{p-1})^qa^r\equiv a^r\pmod p.$

这一步不是直接对指数套用同余运算法则；依据是每一整段 $p-1$ 次幂都贡献一个1。例如算 $3^{100}\bmod7$ ，由于 $100=16\cdot6+4$ ，只需算 $3^4\equiv4\pmod7$ 。例子中的“对6取余”和“对7取余”承担不同任务：6用于分解指数，7用于计算幂的值。

2.4 应用和使用边界

定理还可以证明整除： $a^p\equiv a\pmod p$ 等价于 $p\mid(a^p-a)$ 。也可以给出逆元：当 $p\nmid a$ 时， $a\cdot a^{p-2}\equiv1$ ，所以 $a^{p-2}$ 是 $a$ 的逆元。

但通过一次类似的幂同余检验，不能反过来保证模数是质数。例如 $341=11\cdot31$ ，却有 $2^{340}\equiv1\pmod{341}$ ，因为 $2^{10}=1024\equiv1\pmod{341}$ 。费马小定理给的是“质数必满足”的性质，并未证明“满足这个性质的数必为质数”。

第 2 章：费马小定理与指数缩减 ​

2.1 定理说了什么 ​

2.2 为什么乘法会把非零余数重新排列 ​

2.3 为什么能缩减指数 ​

2.4 应用和使用边界 ​

第 2 章：费马小定理与指数缩减

2.1 定理说了什么

2.2 为什么乘法会把非零余数重新排列

2.3 为什么能缩减指数

2.4 应用和使用边界