反证法

没有直接的代数方法能证明一个数不是整数之比,因为那意味着要检验无穷多个分数;反证法通过假设这样一个最简分数存在,并从这单一假设中挖出一个不可能的奇偶性事实,巧妙地绕开了这一点。

为反证,假设 $\sqrt{2}$ 是有理数。那么可以写成 $\sqrt{2} = \frac{p}{q}$,其中 $p,q$ 为整数且 $q \neq 0$,通过约去公因子可设 $\gcd(p,q)=1$(分数已为最简形式)。

两边平方得 $2 = \frac{p^2}{q^2}$,故 $p^2 = 2q^2$。这意味着 $p^2$ 是偶数。由于奇数的平方是奇数,$p$ 本身必须是偶数;设 $p = 2k$,其中 $k$ 为某个整数。

代回原式,$(2k)^2 = 2q^2$,即 $4k^2 = 2q^2$,化简为 $q^2 = 2k^2$。这意味着 $q^2$ 是偶数,由同样的推理 $q$ 也必须是偶数。

但现在 $p$ 与 $q$ 都是偶数,故 $2$ 同时整除它们,这与假设 $\gcd(p,q)=1$ 矛盾。这一矛盾表明最初的假设——$\sqrt{2}$ 可以写成 $\frac{p}{q}$——必定为假。因此 $\sqrt{2}$ 是无理数。

不可能直接列出无穷多个素数来验证这一断言,因此反证法转而假设存在一个有限的完整列表,并恰好从这个列表出发构造出一个数,揭露该列表其实并不完整。

为反证,假设素数只有有限个,设 $p_1, p_2, \dots, p_n$ 是它们的完整列表。

考虑数 $N = p_1 p_2 \cdots p_n + 1$。由于 $N > 1$,它必有至少一个素因子,记为 $p$(大于 $1$ 的每个整数都有素因子)。

由假设,$p_1, \dots, p_n$ 是所有素数的列表,故对某个 $i$,$p$ 必等于 $p_i$。特别地,$p$ 整除乘积 $p_1 p_2 \cdots p_n$。

但 $p$ 也整除 $N = p_1 p_2 \cdots p_n + 1$。若 $p$ 同时整除 $p_1 p_2 \cdots p_n$ 与 $N$,则 $p$ 整除它们的差:$p \mid \big(N - p_1 p_2 \cdots p_n\big) = 1$。

没有任何素数能整除 $1$,因为每个素数都大于 $1$。这是矛盾。因此最初的假设——素数只有有限个——必定为假,所以素数有无穷多个。