初中数学竞赛 · 整除、同余与不定方程

费马小定理：降次的第一把刀

只要模数是素数，指数就可以按 p−1 取余。这一条把“大指数求余”从找规律变成了套公式。

九~九年级难度 ★★★★15 分钟

定理

设 $p$ 是素数， $a$ 是整数且 $p ∤ a$ ，则

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

等价形式：对任意整数 $a$ ， $a^{p} \equiv a (\mod p)$ 。第二种形式不要求 $p ∤ a$ ，因为 $p ∣ a$ 时两边都 $\equiv 0$ 。

它解决什么问题

指数太大算不动。有了它，指数就可以对 $p - 1$ 取余， $10^{100}$ 次方瞬间降到几十次方。

用剩余系。取 $1, 2, \dots, p - 1$ ，它们构成模 $p$ 的简化剩余系。全部乘 $a$ ，得到 $a, 2 a, \dots, (p - 1) a$ ，因为 $gcd (a, p) = 1$ ，这也是一组简化剩余系。

两个集合的乘积同余：

a \cdot 2 a \dots (p - 1) a \equiv 1 \cdot 2 \dots (p - 1) (\mod p)

即 $a^{p - 1} (p - 1)! \equiv (p - 1)! (\mod p)$ 。 $(p - 1)!$ 与 $p$ 互素，可以约掉，得 $a^{p - 1} \equiv 1$ 。

模数是素数，直接用；模数是合数，用欧拉定理（指数对 $φ (m)$ 取余）；模数含有多个素因子，拆成几个同余式分别算，再合并（中国剩余定理）。

求 $2^{100}$ 除以 $13$ 的余数。

解： $13$ 是素数， $gcd (2, 13) = 1$ ，故 $2^{12} \equiv 1 (\mod 13)$ 。

$100 = 12 \times 8 + 4$ ，所以 $2^{100} \equiv 2^{4} = 16 \equiv 3 (\mod 13)$ 。

求 $3^{100}$ 除以 $10$ 的余数。

解： $10$ 不是素数，用欧拉定理： $φ (10) = 4$ ， $3^{4} \equiv 1 (\mod 10)$ 。

$100 = 4 \times 25$ ，故 $3^{100} \equiv 1 (\mod 10)$ ，个位数字是 $1$ 。

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

解：由费马小定理的第二种形式， $n^{7} \equiv n (\mod 7)$ ，所以 $n^{7} - n \equiv 0 (\mod 7)$ 。

推广：对任意素数 $p$ ， $n^{p} - n$ 都能被 $p$ 整除。这条结论在竞赛里几乎年年出现。

求 $5$ 在模 $17$ 下的逆元。

解： $5^{16} \equiv 1 (\mod 17)$ ，故 $5^{- 1} \equiv 5^{15} (\mod 17)$ 。直接算太麻烦，改用扩展欧几里得或试乘：

$5 \times 7 = 35 \equiv 1 (\mod 17)$ ，所以逆元是 $7$ 。

证明 $341$ 是合数（尽管它满足 $2^{341} \equiv 2 (\mod 341)$ ）。

解： $341 = 11 \times 31$ ，直接看出是合数。

顺便说一句： $341$ 叫“伪素数”，它满足费马小定理的形式却不是素数。所以费马小定理只能用来否定素数（若不满足，一定不是素数），不能用来肯定。这一点在竞赛里经常设陷阱。

三个坑

模数不是素数还用 $p - 1$ ： $p - 1$ 只对素数模成立，合数要用 $φ (m)$ 。
指数取余后忘了还原： $a^{100} \equiv a^{100 mod (p - 1)}$ 只在 $a^{p - 1} \equiv 1$ 的前提下成立，指数为 $0$ 时应取 $a^{p - 1}$ 而不是 $a^{0}$ 。
用费马小定理证明素数：只能反用——不满足则不是素数；满足不代表是素数（ $341$ 是反例）。

练习（先做，再看答案）

看答案

1. $3^{6} \equiv 1 (\mod 7)$ ， $2026 = 6 \times 337 + 4$ ， $3^{2026} \equiv 3^{4} = 81 \equiv 4 (\mod 7)$ 。

2. $2^{4} \equiv 1 (\mod 5)$ ， $100 = 4 \times 25$ ，故余 $1$ 。

3. 由费马小定理 $n^{13} \equiv n (\mod 13)$ ，故差被 $13$ 整除。

4. $7 \times 11 = 77 = 19 \times 4 + 1$ ，逆元是 $11$ 。

5. $561 = 3 \times 11 \times 17$ ，是合数（它是最小的卡迈克尔数，对任意与它互素的 $a$ 都满足 $a^{560} \equiv 1$ ，所以费马小定理也拦不住它）。

一页速记

看完了？ 去整除、同余与不定方程做配套练习，或回到竞赛总览挑下一个专题。想动手刷题、看看这些方法在题目里怎么用，去奥数挑战。