费马小定理及其应用 · 看得见的小蓝本

观察

$m = 7$ ， $a = 3$ ：一步步走， $1 \to 3 \to 2 \to 6 \to 4 \to 5 \to 1$ ， $6$ 步回到 $1$ 。换 $a = 2$ ：几步？ $a = 6$ 呢？
把 $a = 1, \dots, 6$ 的步数都记下来。它们和 $6$ 是什么关系？
步数总是 $6$ 的因数，所以走满 $6$ 步时，一定正好踩在 $1$ 上。看下面那排“费马检验”。
把 $m$ 换成 $11$ 、 $13$ ：费马检验那一排是不是清一色的 $1$ ？
把 $m$ 换成 $9$ 、 $12$ ：有的 $a$ 根本回不到 $1$ 。那一排出现了什么？

费马小定理 设 $p$ 是素数， $a$ 是不被 $p$ 整除的整数，则
$a^{p - 1} \equiv 1 (mod p)$
两边再乘一个 $a$ ： $a^{p} \equiv a (mod p)$ ，这个式子对所有整数 $a$ 都成立。

先猜后证

模 $11$ 。从 $1$ 出发不断乘 $a$ （ $a$ 不是 $11$ 的倍数），第一次回到 $1$ 所用的步数不可能是：

2

5

10

4

先选定答案，才能看到结论。

为什么

证明只用到上一站的那张图：乘以 $a$ 是一次重新排队。

把“重新排队”的两边乘起来

第 1 / 6 步

排队
模 $7$ ，乘以 $3$ 。 $0$ 留在原地； $1, 2, \dots, 6$ 被送到 $3, 6, 2, 5, 1, 4$ ——还是这六个数，只是换了顺序。

$\equiv {3 \cdot 1, 3 \cdot 2, \dots, 3 \cdot 6} {1, 2, \dots, 6} (mod 7)$
两边各自连乘
把 3 提出来
约去 6!
到幂的图上验一下
用来降指数

如果去掉一个条件

Break it

反例实验室：去掉一个条件

结论：每个不被 $p$ 整除的 $a$ 都满足 $a^{p - 1} \equiv 1 (mod p)$

$p = 13$ 。费马检验的 $12$ 个格子全部是 $1$ 。点不同的格子换 $a$ ，再“走完”：步数各不相同，但都是 $12$ 的因数。

练一练

练习 1基础

求 $5^{14}$ 被 $13$ 除的余数。

练习 2基础

求 $2^{2025}$ 被 $11$ 除的余数。

练习 3提高

证明：对任意整数 $n$ ， $n^{7} - n$ 能被 $42$ 整除。

练习 4挑战

素数 $p$ 满足 $p ∣ (2^{p} + 1)$ 。求 $p$ 。

错误博物馆 · 本站展品

离站之前，看看别人在这里踩过的坑。去博物馆看全部展品 →

展品

模不是素数，照样套费马小定理

由费马小定理，

2^{14} \equiv 1 (mod 15)

。

错在哪里？先想一想，再打开

病因　 $15 = 3 \times 5$ 不是素数，定理不管它。实际上 $2^{4} = 16 \equiv 1 (mod 15)$ ，所以 $2^{14} = (2^{4})^{3} \times 2^{2} \equiv 4$ 。

先确认模是素数。合数模要么直接找周期（这里是

4

），要么拆成素数模分别处理。

「用定理前先验条件：p 是素数吗」

展品

底数是 p 的倍数

1 4^{6} \equiv 1 (mod 7)

。

错在哪里？先想一想，再打开

病因　 $7 ∣ 14$ ，所以 $1 4^{6} \equiv 0 (mod 7)$ 。定理要求 $p ∤ a$ ：从 $1$ 出发乘一个 $0$ ，掉进 $0$ 就再也出不来了。

不想检查这个条件时，用另一种写法：

a^{p} \equiv a (mod p)

，它对所有整数

a

成立。

「a 不能是 p 的倍数」

展品

把定理反过来用

2^{340} \equiv 1 (mod 341)

，所以

341

是素数。

错在哪里？先想一想，再打开

病因　 $341 = 11 \times 31$ 。碰巧 $2^{10} = 1024 = 3 \times 341 + 1 \equiv 1$ ，于是 $2^{340} \equiv 1$ 。定理说“素数 ⇒ 余 1”，没说“余 1 ⇒ 素数”。

余数不是

1

，可以断定是合数；余数是

1

，什么也不能断定。换个底数：

3^{340} \neq \equiv 1 (mod 341)

。

「定理只管一个方向」