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

素数与合数

素数是乘法的“原子”。判断一个数是不是素数、以及素数有哪些必须的性质，是数论题的起点。

七~九年级难度 ★★★14 分钟

定义里的两个坑

大于 $1$ 的整数，如果只有 $1$ 和它本身两个正因数，叫素数（也叫质数）；否则叫合数。

两个坑：

$1$ 既不是素数也不是合数。它只有一个正因数，不满足“两个因数”。
$2$ 是唯一的偶素数。所有其他素数都是奇数。

为什么素数重要

任何大于 $1$ 的整数都能唯一地分解成素数的乘积（算术基本定理）。所以素数相当于整数里的“原子”，研究整数的乘法结构，本质上就是研究素数。

怎么判断一个数是不是素数

试除法：用不超过 $\sqrt{n}$ 的所有素数去试除。如果都不整除， $n$ 就是素数。

为什么只需要试到 $\sqrt{n}$ ：如果 $n = a b$ 且 $a \leq b$ ，那么 $a \leq \sqrt{n}$ 。也就是说，只要 $n$ 是合数，它一定有一个不超过 $\sqrt{n}$ 的因数。

判断 $97$ 是不是素数： $\sqrt{97} \approx 9.8$ ，只需试 $2, 3, 5, 7$ 。 $97$ 不被这四个数整除，所以是素数。

判断 $91$ ： $\sqrt{91} \approx 9.5$ ，试 $2, 3, 5, 7$ ， $91 = 7 \times 13$ ，是合数。

素数有无穷多个

欧几里得的证明，反证法：

假设素数只有有限个，记为 $p_{1}, p_{2}, \dots, p_{n}$ 。构造

N = p_{1} p_{2} \dots p_{n} + 1

$N$ 大于 $1$ ，所以它要么本身是素数，要么有素因数。但 $N$ 除以任何一个 $p_{i}$ 都余 $1$ ，所以 $p_{i}$ 都不整除 $N$ 。这说明存在一个新的素数，与“只有 $n$ 个”矛盾。

这个证明的结构

用已知的有限个素数造一个新数，让它们都除不尽。这个套路在后面很多题里会重复出现。

素数最关键的一条性质

若 $p$ 是素数，且 $p ∣ a b$ ，则 $p ∣ a$ 或 $p ∣ b$ 。

这条性质合数没有。比如 $6 ∣ 2 \times 3$ ，但 $6 ∤ 2$ 且 $6 ∤ 3$ 。

它的用处：从乘积里“提取”因子。例如 $p ∣ n^{2}$ 能推出 $p ∣ n$ 。

例题

例1 判定

判断 $143$ 与 $167$ 是不是素数。

解： $\sqrt{143} \approx 12$ ，试 $2, 3, 5, 7, 11$ 。 $143 = 11 \times 13$ ，是合数。

$\sqrt{167} \approx 12.9$ ，试 $2, 3, 5, 7, 11$ ： $167$ 是奇数、各位和 $14$ 不被 $3$ 整除、末位不是 $0 / 5$ 、 $167 = 7 \times 23 + 6$ 、 $167 = 11 \times 15 + 2$ ，都不整除，所以 $167$ 是素数。

例2 用素数性质

已知 $p$ 是素数， $p ∣ n^{2}$ ，证明 $p ∣ n$ 。

解： $n^{2} = n \cdot n$ ，由 $p ∣ a b$ ⇒ $p ∣ a$ 或 $p ∣ b$ ，取 $a = b = n$ ，得 $p ∣ n$ 。

推广： $p ∣ n^{k}$ ⇒ $p ∣ n$ ，对任意正整数 $k$ 成立。

例3 三个都是素数

求所有的素数 $p$ ，使 $p$ 、 $p + 2$ 、 $p + 4$ 都是素数。

解： $p = 3$ 时 $3, 5, 7$ 都是素数，符合。

$p > 3$ 时， $p$ 不被 $3$ 整除，故 $p \equiv 1$ 或 $2 (\mod 3)$ 。

若 $p \equiv 1 (\mod 3)$ ，则 $p + 2 \equiv 0 (\mod 3)$ ，且 $p + 2 > 3$ ，是合数；

若 $p \equiv 2 (\mod 3)$ ，则 $p + 4 \equiv 0 (\mod 3)$ ，且 $p + 4 > 3$ ，是合数。

两种情况都矛盾，所以只有 $p = 3$ 。

这类题的标准动作：三个数间隔固定，就找一个模数让它们恰好覆盖所有余数。这里间隔是 $2$ 和 $4$ ，模 $3$ 正好。

例4 构造合数

证明：对任意大于 $1$ 的整数 $n$ ， $n^{4} + 4$ 是合数。

解：补项分解： $n^{4} + 4 = n^{4} + 4 n^{2} + 4 - 4 n^{2} = (n^{2} + 2)^{2} - (2 n)^{2} = (n^{2} + 2 n + 2) (n^{2} - 2 n + 2)$

$n > 1$ 时， $n^{2} - 2 n + 2 = (n - 1)^{2} + 1 \geq 2$ ， $n^{2} + 2 n + 2 > 2$ ，两个因式都大于 $1$ 且都小于原式，所以 $n^{4} + 4$ 是合数。

为什么必须限定 $n > 1$ ： $n = 1$ 时 $1 + 4 = 5$ 是素数，结论不成立。边界值一定要单独看。

例5 素数在数列里

求所有素数 $p$ ，使 $2 p + 1$ 是完全平方数。

解：设 $2 p + 1 = m^{2}$ ，则 $2 p = (m - 1) (m + 1)$ 。 $m$ 必为奇数（否则 $m^{2}$ 为偶数， $2 p$ 为偶数， $m^{2} - 1 = 2 p$ 需要 $m$ 奇）。

$m$ 为奇数时 $m - 1$ 与 $m + 1$ 是相邻偶数，都含因子 $2$ ，且 $gcd (m - 1, m + 1) = 2$ 。

$2 p$ 只有因子 $1, 2, p, 2 p$ 。由于 $m - 1 \geq 2$ （ $m \geq 3$ ），且 $m - 1 < m + 1$ ，只能 $m - 1 = 2$ ， $m + 1 = 2 p$ ，得 $m = 3$ ， $p = 4$ （不是素数），矛盾。

检查 $m = 1$ ： $2 p + 1 = 1$ ⇒ $p = 0$ ，不行。

所以不存在这样的素数 $p$ 。

三个坑

把 1 当素数：这是最常见的错误，直接导致整题作废。
试除只试到 $n / 2$ ：试到 $\sqrt{n}$ 就够，多试浪费时间。
忘记检查边界： $n = 1$ 、 $p = 2$ 这类小值经常是反例。

练习（先做，再看答案）

判断 $221$ 是不是素数。
证明：若 $p$ 是大于 $3$ 的素数，则 $p^{2} - 1$ 能被 $24$ 整除。
求所有的素数 $p$ ，使 $p + 4$ 也是素数，且 $p < 10$ 。
证明： $n^{2} + n + 1$ 不可能是完全平方数（ $n$ 为正整数）。
已知 $p, q$ 都是素数，且 $p + q = 100$ ，求 $p, q$ 。

看答案

1. $\sqrt{221} \approx 14.9$ ，试 $2, 3, 5, 7, 11, 13$ ： $221 = 13 \times 17$ ，是合数。

2. $p^{2} - 1 = (p - 1) (p + 1)$ 。 $p$ 是大于 $3$ 的素数，故 $p$ 为奇数， $p - 1, p + 1$ 是相邻偶数，其中一个被 $4$ 整除，故乘积被 $8$ 整除；又 $p$ 不被 $3$ 整除， $p - 1, p, p + 1$ 中必有 $3$ 的倍数，而 $p$ 不是，所以 $p - 1$ 或 $p + 1$ 被 $3$ 整除。 $8$ 与 $3$ 互素，故被 $24$ 整除。

3. $p = 3$ 时 $7$ 是素数； $p = 7$ 时 $11$ 是素数。 $p = 2$ 时 $6$ 不是素数， $p = 5$ 时 $9$ 不是素数。答案 $p = 3, 7$ 。

4. $n^{2} < n^{2} + n + 1 < (n + 1)^{2}$ ，夹在两个相邻平方数之间，不可能是平方数。

5. 若 $p = 2$ ，则 $q = 98$ 不是素数，故 $p, q$ 都是奇素数。穷举 $p \leq q$ ： $3 + 97$ 、 $5 + 95$ （不行）、 $7 + 93$ （不行）、 $11 + 89$ 、 $17 + 83$ 、 $29 + 71$ 、 $41 + 59$ 、 $47 + 53$ ，共六组。

一页速记

$1$ 不是素数； $2$ 是唯一偶素数
判定：试除到 $\sqrt{n}$ 的所有素数
素数无穷：构造 $p_{1} p_{2} \dots p_{n} + 1$ 反证
$p ∣ a b$ ⇒ $p ∣ a$ 或 $p ∣ b$ （合数没有这条性质）
大于 $3$ 的素数都能写成 $6 k \pm 1$
边界值（ $n = 1$ 、 $p = 2, 3$ ）必须单独验

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