最小数原理与无穷递降法

一句话

最小数原理：正整数集的任何一个非空子集中，一定有一个最小的数。

换个说法就是无穷递降法：不存在无限的、严格递减的正整数列 $n_{1} > n_{2} > n_{3} > \dots$ 。于是，要证明某个东西不存在，可以这样：

假设它存在，并把它和一个正整数挂上钩（比如分母 $q$ ）；取这个正整数最小的那一个。
由它造出另一个，挂钩的正整数更小。
和“最小”矛盾——或者说，楼梯不可能一直往下走。

最小数原理和数学归纳法是一回事的两面：如果 $P (n)$ 不是对一切 $n$ 都成立，就取最小的反例 $n_{0}$ ； $P (1)$ 成立说明 $n_{0} > 1$ ， $P (n_{0} - 1)$ 成立却推不出 $P (n_{0})$ ，和递推矛盾。

例：√2 是无理数

第 1 / 4 步

假设有解
若 $2 = \frac{p}{q}$ （ $p, q$ 为正整数），则 $p^{2} = 2 q^{2}$ 。在所有这样的分数里，取分母 $q$ 最小的一个。

$p^{2} = 2 q^{2}, q 最小$
造一个新的
新的更小，而且仍是正的
矛盾

先猜后证

机器 $(p, q) \mapsto (2 q - p, p - q)$ 作用在 $(99, 70)$ 上，下一级是什么？

(41, 29)

(29, 41)

(58, 41)

(70, 29)

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

第 1 站 · 无理数：把 2 换成别的 d

同一台机器对任何不是完全平方数的 $d$ 都管用：取 $a = ⌊ d ⌋$ ，令

p^{'} = d q - a p, q^{'} = p - a q .

展开得 $p^{'2} - d q^{'2} = (a^{2} - d) (p^{2} - d q^{2})$ ；又 $a < d < a + 1$ 保证 $0 < q^{'} < q$ 。所以 $p^{2} = d q^{2}$ 没有正整数解， $d$ 是无理数。在英雄图里把 $d$ 调成 $3, 5, 7$ 试一试。

第 2 站 · 不定方程

方程 $x^{2} + y^{2} = 3 z^{2}$ 没有正整数解。 这次递降的量是 $z$ ，造更小解的工具是余数。

例：x² + y² = 3z²

第 1 / 4 步

取最小的解
假设有正整数解，取 $z$ 最小的一组 $(x, y, z)$ 。

$x^{2} + y^{2} = 3 z^{2}$
看模 3
代回去
更小的解

第 3 站 · 最小反例

不一定要“造更小的解”。有时只要盯住最小的那个对象，它的性质自己就说出了答案。

例：每个大于 1 的整数都有素因数

第 1 / 3 步

集合非空
$n > 1$ 的大于 $1$ 的因数组成一个集合，它至少含有 $n$ 本身，非空。

${d : d ∣ n, d > 1} ∋ n$
取最小的
它一定是素数

如果 d 是完全平方数

Break it

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

结论： $p^{2} = d q^{2}$ 没有正整数解

$d = 3$ ：从 $(26, 15)$ 出发（ $2 6^{2} - 3 \cdot 1 5^{2} = 1$ ），每一级都满足 $1 < p / q < 2$ ， $q$ 一路变小直到跌出正整数。

练一练

练习 1基础

从 $(41, 29)$ 出发，反复用 $(p, q) \mapsto (2 q - p, p - q)$ 。走几步后 $q$ 第一次变成 $0$ ？

练习 2基础

用无穷递降法证明 $3$ 是无理数。

练习 3提高

证明方程 $x^{3} + 2 y^{3} = 4 z^{3}$ 没有正整数解。

练习 4挑战

（IMO 1988）正整数 $a, b$ 使 $ab + 1$ 整除 $a^{2} + b^{2}$ 。可以证明商 $k = \frac{a ^{2} + b ^{2}}{ab + 1}$ 一定是完全平方数。先算 $a = 8, b = 30$ 时的 $k$ ，再试着用递降说明为什么。

一句话

例：√2 是无理数

第 1 站 · 无理数：把 2 换成别的 d

第 2 站 · 不定方程

例：x² + y² = 3z²

第 3 站 · 最小反例

例：每个大于 1 的整数都有素因数

如果 d 是完全平方数

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

练一练

错误博物馆 · 本站展品

在没有最小元的地方递降