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

算术基本定理：每个数只有一种拆法

大于 1 的整数拆成素数乘积的方式唯一（不计顺序）。这条看似平常的结论，是约数个数、完全平方数、整除判断所有公式的来源。

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

定理本身

任何大于 $1$ 的整数 $n$ 都能唯一地写成

n = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{k}^{a_{k}}

其中 $p_{i}$ 是互不相同的素数， $a_{i}$ 是正整数。“唯一”是指：除了排列顺序，这种写法只有一种。

$360 = 2^{3} \cdot 3^{2} \cdot 5$ ，就这么一种。你不可能找出另一组素数幂乘起来也是 $360$ 。

它为什么重要

一旦把数写成素数幂，所有关于整除的问题都变成了比较指数：

d ∣ n ⟺ d 的每个素因子指数都不超过 n 的对应指数

约数个数

若 $n = p_{1}^{a_{1}} \dots p_{k}^{a_{k}}$ ，则 $n$ 的正约数个数是

(a_{1} + 1) (a_{2} + 1) \dots (a_{k} + 1)

理由：一个约数的每个素因子指数可以取 $0$ 到 $a_{i}$ ，共 $a_{i} + 1$ 种选择，各因子独立，乘起来就是总数。

$360 = 2^{3} \cdot 3^{2} \cdot 5^{1}$ ，约数个数 $(3 + 1) (2 + 1) (1 + 1) = 24$ 。

约数之和

σ (n) = (1 + p_{1} + \dots + p_{1}^{a_{1}}) (1 + p_{2} + \dots + p_{2}^{a_{2}}) \dots

每个括号是等比数列，展开后正好穷尽所有约数，且每个约数只出现一次。

指数视角下的两个结论

完全平方数： $n$ 是完全平方数 ⇔ 分解式中每个指数都是偶数。

完全立方数：每个指数都是 $3$ 的倍数。

这两个判据在竞赛里用得极多，因为它们把“平方”这个乘法概念转化成了“指数的奇偶”。

例题

例1 约数个数

求 $1260$ 的正约数个数。

解： $1260 = 2^{2} \cdot 3^{2} \cdot 5 \cdot 7$ ，约数个数 $(2 + 1) (2 + 1) (1 + 1) (1 + 1) = 36$ 。

例2 反向求数

一个正整数有 $12$ 个约数，且是 $2$ 的幂，求这个数。

解：设 $n = 2^{a}$ ，约数个数 $a + 1 = 12$ ，故 $a = 11$ ， $n = 2^{11} = 2048$ 。

如果题目不说“是 2 的幂”，答案就不唯一： $2^{11}$ 、 $2^{5} \cdot 3$ 、 $2^{3} \cdot 3^{2}$ 、 $2^{2} \cdot 3 \cdot 5$ 都有 $12$ 个约数。约束条件决定了答案是否唯一。

例3 完全平方判定

判断 $2^{10} \cdot 3^{7} \cdot 5^{4}$ 是不是完全平方数。

解：指数 $10, 7, 4$ 中 $7$ 是奇数，所以不是完全平方数。

要让它变成完全平方数，最小乘数是 $3$ （把 $3$ 的指数补成 $8$ ），最小除数是 $3$ （把指数降到 $6$ ）。

例4 整除的指数判据

证明：若 $a^{2} ∣ b^{2}$ ，则 $a ∣ b$ 。

解：设 $a = p_{1}^{α_{1}} \dots p_{k}^{α_{k}}$ ， $b = p_{1}^{β_{1}} \dots p_{k}^{β_{k}}$ （指数可以为 $0$ ）。

$a^{2} ∣ b^{2}$ 意味着对每个 $i$ 都有 $2 α_{i} \leq 2 β_{i}$ ，即 $α_{i} \leq β_{i}$ ，这正是 $a ∣ b$ 的条件。

例5 约数之和

求 $72$ 的所有正约数之和。

解： $72 = 2^{3} \cdot 3^{2}$ 。 $σ (72) = (1 + 2 + 4 + 8) (1 + 3 + 9) = 15 \times 13 = 195$

验算： $72$ 的约数是 $1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72$ ，加起来 $195$ 。

三个坑

分解不彻底： $360$ 写成 $2^{3} \cdot 45$ 就没法用公式， $45$ 还要继续拆。
约数个数漏了 1 和本身：公式 $(a + 1)$ 里已经包含指数取 $0$ 和取 $a_{i}$ 的情况，不用另外加。
把“有 12 个约数”当成唯一条件：不加限制时答案有无穷多个，要看清题目约束。

练习（先做，再看答案）

求 $1800$ 的正约数个数。
求 $1800$ 的所有正约数之和。
求最小的正整数 $n$ ，使 $n$ 有 $6$ 个约数。
若 $n$ 是完全平方数，证明 $n$ 的约数个数是奇数。
求最小的正整数 $k$ ，使 $2^{3} \cdot 3^{2} \cdot 5 \cdot k$ 是完全平方数。

看答案

1. $1800 = 2^{3} \cdot 3^{2} \cdot 5^{2}$ ，约数个数 $4 \times 3 \times 3 = 36$ 。

2. $(1 + 2 + 4 + 8) (1 + 3 + 9) (1 + 5 + 25) = 15 \times 13 \times 31 = 6045$ 。

3. $6 = 6 \times 1 = 3 \times 2$ ，对应 $p^{5}$ 或 $p^{2} q$ 。最小的是 $2^{2} \cdot 3 = 12$ （ $p^{5}$ 中 $2^{5} = 32$ 更大）。

4. 设 $n = p_{1}^{2 a_{1}} \dots p_{k}^{2 a_{k}}$ ，约数个数 $\prod (2 a_{i} + 1)$ ，每个因子都是奇数，乘积为奇数。

5. 指数 $3, 2, 1$ 中 $3$ 和 $1$ 是奇数，需补 $2 \times 3 \times 5 = 30$ 的因子使它们变偶； $k = 2 \cdot 3 \cdot 5 = 30$ 时指数变为 $4, 3, 2$ ， $3$ 仍是奇数，再乘 $3$ 得 $k = 90$ ，指数 $4, 4, 2$ ，全偶。故 $k = 90$ 。

一页速记

每个大于 1 的整数只有一种素数分解（不计顺序）
约数个数 $= \prod (a_{i} + 1)$ ；约数之和 $= \prod (1 + p + \dots + p^{a})$
完全平方 ⇔ 所有指数为偶；完全立方 ⇔ 所有指数是 3 的倍数
$d ∣ n$ ⇔ 指数逐项不超过
分解必须彻底，否则公式全错

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