证明整除性

用数学归纳法证明整除性问题在数论中很常见。关键是利用整除的性质和模运算。

基本知识

证明策略

证明 $a | f(n)$ 的步骤：

1. 基础步骤：验证 $a | f(n_0)$
2. 归纳假设：假设 $a | f(k)$，即 $f(k) = ma$（$m$ 为整数）
3. 归纳步骤：将 $f(k+1)$ 表示成包含 $f(k)$ 的形式，利用归纳假设

应用示例

示例1：基本整除性

命题：证明 $n^3 - n$ 能被 6 整除。

证明：

基础步骤：$n = 1$ 时，$1^3 - 1 = 0 = 6 \times 0$，能被 6 整除。

归纳假设：假设 $k^3 - k$ 能被 6 整除，即 $k^3 - k = 6m$（$m$ 为整数）

归纳步骤：

$$\begin{aligned} (k+1)^3 - (k+1) &= k^3 + 3k^2 + 3k + 1 - k - 1 \\ &= k^3 - k + 3k^2 + 3k \\ &= (k^3 - k) + 3k(k + 1) \\ &= 6m + 3k(k+1) \quad \text{（归纳假设）} \end{aligned}$$

因为 $k$ 和 $k+1$ 是连续整数，其中必有一个是偶数，所以 $k(k+1)$ 是偶数，设 $k(k+1) = 2p$：

$(k+1)^3 - (k+1) = 6m + 3 \times 2p = 6m + 6p = 6(m+p)$

因此能被 6 整除。

结论：由数学归纳法，$n^3 - n$ 能被 6 整除对所有 $n \geq 1$ 成立。

示例2：幂次差的整除性

命题：证明 $7^n - 1$ 能被 6 整除。

证明：

基础步骤：$n = 1$ 时，$7^1 - 1 = 6$，能被 6 整除。

归纳假设：假设 $7^k - 1$ 能被 6 整除，即 $7^k - 1 = 6m$

归纳步骤：

$$\begin{aligned} 7^{k+1} - 1 &= 7 \cdot 7^k - 1 \\ &= 7(7^k - 1) + 7 - 1 \\ &= 7 \times 6m + 6 \quad \text{（归纳假设）} \\ &= 6(7m + 1) \end{aligned}$$

因此能被 6 整除。

结论：由数学归纳法，$7^n - 1$ 能被 6 整除对所有 $n \geq 1$ 成立。

示例3：斐波那契数列的整除性

命题：斐波那契数列 $F_1 = 1, F_2 = 1, F_{n+2} = F_{n+1} + F_n$。证明 $F_{3n}$ 能被 2 整除。

证明：

先计算前几项：$F_1=1, F_2=1, F_3=2, F_4=3, F_5=5, F_6=8, F_7=13, F_8=21, F_9=34$

基础步骤：$n = 1$ 时，$F_3 = 2$，能被 2 整除。

归纳假设：假设 $F_{3k}$ 能被 2 整除。

归纳步骤：需要证明 $F_{3(k+1)} = F_{3k+3}$ 能被 2 整除。

利用斐波那契数列的性质：$F_{n+3} = F_{n+2} + F_{n+1} = (F_{n+1} + F_n) + F_{n+1} = 2F_{n+1} + F_n$

因此： $F_{3k+3} = 2F_{3k+1} + F_{3k}$

由归纳假设，$F_{3k}$ 能被 2 整除，而 $2F_{3k+1}$ 显然能被 2 整除，所以 $F_{3k+3}$ 能被 2 整除。

结论：由数学归纳法，$F_{3n}$ 能被 2 整除对所有 $n \geq 1$ 成立。

练习题

练习 1

证明：$5^n - 1$ 能被 4 整除。

参考答案

基础步骤：$n = 1$ 时，$5^1 - 1 = 4$，能被 4 整除。

归纳假设：假设 $5^k - 1$ 能被 4 整除，即 $5^k - 1 = 4m$

归纳步骤：

$$\begin{aligned} 5^{k+1} - 1 &= 5 \cdot 5^k - 1 \\ &= 5(5^k - 1) + 5 - 1 \\ &= 5 \times 4m + 4 \\ &= 4(5m + 1) \end{aligned}$$

结论：由数学归纳法，$5^n - 1$ 能被 4 整除。

练习 2

证明：$n^5 - n$ 能被 5 整除。

参考答案

基础步骤：$n = 1$ 时，$1^5 - 1 = 0$，能被 5 整除。

归纳假设：假设 $k^5 - k$ 能被 5 整除。

归纳步骤：

$$\begin{aligned} (k+1)^5 - (k+1) &= k^5 + 5k^4 + 10k^3 + 10k^2 + 5k + 1 - k - 1 \\ &= k^5 - k + 5k^4 + 10k^3 + 10k^2 + 5k \\ &= (k^5 - k) + 5(k^4 + 2k^3 + 2k^2 + k) \end{aligned}$$

由归纳假设，$k^5 - k$ 能被 5 整除，而 $5(k^4 + 2k^3 + 2k^2 + k)$ 显然能被 5 整除。

结论：由数学归纳法，$n^5 - n$ 能被 5 整除。

---

总结

中英对照

中文术语	英文术语	音标	说明
整除	divisibility	/dɪˌvɪzəˈbɪləti/	一个数能被另一个数整除
模运算	modular arithmetic	/ˈmɒdjʊlə əˈrɪθmətɪk/	关于余数的运算
斐波那契数列	Fibonacci sequence	/ˌfɪbəˈnɑːtʃi ˈsiːkwəns/	$F_{n+2} = F_{n+1} + F_n$

上一章节 证明不等式