反证法+整数的性质

定理: 若$a$和$b$为正整数, 则$a^{1/b}$要么是无理数, 要么是整数.

提示

若$a^{1/b}=x/y$, 其中$y\not\mid x$, 则$a=\left(a^{1/b}\right)^{b}=x^{b}/y^{b}$不是整数, (因为$y^{b}\not\mid x^{b}$), 这与$a$是整数矛盾.

反证法+唯一因子分解

假设$\sqrt{2}$可以写成不可约分数$\frac{p}{q}$, 其中$p,q$都是正整数. 则$2q^{2}=p^{2}$. 由于$p^{2}$和$q^{2}$的因子$2$都是偶数个, 所以$2q^{2}$有奇数个因子$2$, 由于唯一因子分解的唯一性, $p^{2}$只有偶数个因子$2$, 它不可能等于$p^{2}$.

反证法+余数

如果$\sqrt{2}$是有理数, 则有分数表示$a/b$, 取$b$是$\sqrt{2}$的分数表示中分母最小的. 则

考虑$a^{2}$的末位数字, 它只可能是$0,1,4,5,6,9$中的一个. 而$2b^{2}$的末位数字只有$0,2,8$三种情况. 如果$a^{2}$与$2b^{2}$相等, 则它们有相同的末位数, 这个末位数只能是$0$. 所以$a$的末位数字只能是$0$, 而$b$的末位数字只能是$0$或$5$, 无论哪种情况, $a$和$b$都能被$5$整除, 从而$\frac{a/5}{b/5}$也是$\sqrt{2}$的分数表示. 因为$b/5<b$, 这与$b$是$\sqrt{2}$的分数表示中分母最小的选择矛盾.

这种方法在证明$2^{1/3}$的无理性时变得简洁.

设$2^{1/3}$是既约分数$a/b$, 则$2a^{3}=b^{3}$, 考虑模7同余, 由于整数的立方模7同余的结果只有$0,1$或$6$, 因此$a,b$模7必然均为$0$, 这与$a/b$是既约分数矛盾.

反证法+Bezout公式

$\sqrt{2}$是无理数的证明是下面定理的推论.

定理: 对于$n\in\NN$. 如果$r=\sqrt{n}$是有理数, 则$r$是整数.

提示

设$r=a/b$为有理数, 其中$\mathrm{gcd}(a,b)=1$, 则有Bezout公式, 存在整数$c,d\in\ZZ$, 使得

因此,

所以$r$是整数.

这一证法可以推广到三次根的有理判别法, 如下

定理: 若$r^{3}=m\in\ZZ$, 如果$r\in\QQ$, 则$r\in\ZZ$.

提示

设$r=a/b\in\QQ$, $\mathrm{gcd}(a,b)=1$, 则由Bezout公式, 存在$c,d\in\ZZ$, 使得$ad-bc=1$. 从而

所以对于$r$的多项式方程, 这里从原来的$r^{3}-m=0$的次数$3$降到了上式中$1\cdot r^{2}+acr-bdm=0$的次数$2$, 按照下面的推广, 这个指数可以继续递降下去直到$r\in\ZZ$.

定理: 若$r=a/b\in\QQ$是$\ZZ[x]$中的首一多项式的根, $a/b$为既约分数, 则$r\in\ZZ$.

提示

设这个首一多项式的次数大于$1$, 并设

于是同前面使用Bezout公式时一样,

化简并注意到$br^{n}=ar^{n-1}$, 有

$r$所满足的方程从原来的指数$n+1$降为了指数为$n$的首一多项式, 如此继续下去, 指数$n$必然在有限步后降为$n=0$, 从而$r=e\in\ZZ$.

反证法+Bezout公式 - 2

定理: 若$p,q,n$为正整数, 且$\mathrm{gcd}(p,q)=1$, 且$p^{2}=nq^{2}$, 则$q=1$, 从而$n=p^{2}$.

提示

由于$\mathrm{gcd}(p,q)=1$, 所以存在整数$s,t$, 使得$ps+qt=1$. 两边同时取立方, 得到

又由$p^{2}=nq^{2}$, 所以

因此$q\mid1$.

连分数法

设$v=1+\sqrt{2}$, 则有

容易验证$v=2+\frac{1}{v}$. 所以如果不断的将右边分母中的$v$替换成$2+\frac{1}{v}$, 就有以下连分式

因为任何无穷连分数都是无理数, 所以$1+\sqrt{2}$是无理数.

无穷递降原理(自然数的良序性)

这个证明和连分数构造类似, 可以用来避免使用连分数的知识.

定理: 对于自然数$n$, 如果$r=\sqrt{n}$是有理数, 则它是整数.

提示

设$r=\frac{A}{B}$, $B$是$r$的有理表示中分母最小的正整数.

由于$\sqrt{n}=\frac{n}{\sqrt{n}}$, 将$\sqrt{n}=r=\frac{A}{B}$代入, 得到

对上式左右两边取小数部分, 得到形如

的等式.

如果$b\ne0$, 所以$\frac{A}{B}=\frac{a}{b}$, 此式两边都可以看成$r$的有理数表示, 而$b<B$.
这与$B$的最小性矛盾.

所以只能有$b=0$, 这也就意味着$\frac{A}{B}$的小数部分$\frac{b}{B}$为$0$, 即$\frac{A}{B}$是整数.

wiki百科有一个按照分母的无穷递降法.

定理: 如果$\sqrt{k}$不是整数, 则它是无理数.

提示

证明. 用反证法, 对于$k>0$, 假设$\sqrt{k}$不是整数, 则有有理表示$\frac{a}{b}$, 其中$a,b$都是自然数, 设$q$是不超过$\sqrt{k}$的最大整数. 则

其中, 在分子分母同时乘以的$\left(\sqrt{k}-q\right)$是一个介于$0$和$1$之间的有理数. 而上面的$a’,b’$分别小于$a,b$, 且它们的比值都是$\sqrt{k}$. 由于自然数的良序性, 从$a,b$之比递减到$a’,b’$之比可以继续进行下去, 而这种无穷递降是不可能的. 所以$\sqrt{k}$不能是自然数之比.

如果考虑的是$2$的立方根的无理性证明, 按照Fermat的无穷递降原理则会有一种调皮的证法:

假设$2^{1/3}=\frac{n}{m}$, 则$2m^{3}=n^{3}$, 也即

由Fermat大定理在指数为$3$时不存在正整数解, 所以$2^{1/3}$是无理数.

有理根判别法

考虑多项式方程$x^{2}-2=0$, 有根$\pm\sqrt{2}$. 如果方程有有理解$\frac{a}{b}$, 则$a\mid2$且$b\mid1$, 所以$\frac{a}{b}\in\left\{ \pm1,\pm2\right\} $. 然而, 直接验证知$\pm1,\pm2$都不是方程$x^{2}-2=0$的根, 所以方程没有有理根, 从而$\sqrt{2}$是无理数.

反证法+自然数的良序性

设$\sqrt{2}$是有理数, 可以表示成$\sqrt{2}=a/b$的形式, 其中$a,b$都是正整数, 考虑集合

首先$S$不空, 因为$a=b\sqrt{2}\in\mathbb{Z}$, 而$b\in\mathbb{Z}$, 所以$b\sqrt{2}\in S$. 由于$S$是自然数的子集, 由良序性, $S$中存在最小元$s=t\sqrt{2}$.

注意, 这时$s\sqrt{2}-s=(s-t)\sqrt{2}=s(\sqrt{2}-1)<s$. 而且不等式左边, $s-t$和$(s-t)\sqrt{2}$都是整数. 所以$s(\sqrt{2}-1)=(s-t)\sqrt{2}\in S$, 这与$s$是$S$中的最小元矛盾.

另有一个由 Theodor Estermann 的证明 $\sqrt{2}$ 的无理性发展出来的推广命题, 它是由 Harley Flanders 给出的证明$\sqrt{m}$ 的无理性的命题, 如下

定理: 假设$m$ 不是完全平方数, 则$\sqrt{m}$是无理数.

设$n$ 是满足$n<\sqrt{m}<n+1$的整数, 则$\alpha=\sqrt{m}-n$是无理数. 用反证法, 则由$0<\alpha<1$, 有有理表示$\alpha=p/q$, 其中$0<p<q$. 假设$q$是$\alpha$的有理表示中分母最小的, 则

由此解得

因此$\alpha$有另一个分母更小的分数表示, 导出矛盾.

定理: 对于自然数$a$和$t$, $a^{1/t}$要么是无理数, 要么是整数.

提示

假设$a^{1/t}$不是整数, 设它是有理数. 则$a^{1/t}$的所有整数幂都是有理数. 考虑有理数序列$a^{i/t}$, $i=1,\cdots,t-1$, 并将其分母的最小公倍数记为$m$, 则$m$是使$ma^{i/t}$, ($i=1,\cdots,t-1$), 均为整数的最小正整数.

因为$a^{1/t}$不是整数, 所以存在整数$b$使得$b<a^{1/t}<b+1$. 因此$0<a^{1/t}-b<1$, 且$0<m\left(a^{1/t}-b\right)<m$. 记$k=m\left(a^{1/t}-b\right)$, 则$k\in\ZZ$.

对于任意的$i=1,\cdots,t-1$, $ka^{i/t}=ma^{(i+1)/t}-bma^{i/t}$. 当$i\le t-2$时, $ka^{i/t}\in\ZZ$; 当$i=t-1$时, 由于$a$是自然数, 所以$ka^{i/t}$仍旧均为整数. 然而$0<k<m$, 也使得$ka^{i/t}\in\ZZ$, $i=1,\cdots,t-1$, 这与$m$的最小性矛盾.

反证法+主理想

定理: 设$n\in\NN$. 如果$r=\sqrt{n}$是有理数, 则$r$是整数.

提示

考虑$r$的所有可能的分母$d$所构成的集合$D$, 也即,

注意到$D$在减法运算下封闭:

进而当$d\in D$时, 由于$r^{2}=n\in\ZZ$, 有 $(dr)r=dn\in\ZZ$, 所以$dr\in D$. 根据以下引理, 当$d$为$D$中最小的正自然数时, 有$d\mid dr$, 也即$r=(dr)/d\in\ZZ$.

引理: 假设$D\subseteq\ZZ$在减法运算下封闭, 且$D$中有非零元. 则$D$中存在最小正元素能够整除$D$中的任何元素.

提示
  1. 先证明有非零元的集合$D$中有正整数.

设$d\ne0$, $d\in D$, 则有$d-d=0\in D$, 从而$0-d=-d\in D$, 所以$D$中至少存在一个正整数, 要么是$d$, 要么是$-d$.

  1. 证明引理的结论.

用反证法, 设$d$为$D$中最小正整数. 由于$d\mid n\Longleftrightarrow d\mid-n$. 由自然数的良序性, 假设 $c\in D$ 为满足 $d\not\mid c$ 的最小正整数. 由此 $c-d>0$ 且有 $d\not\mid c-d\in D$, 是不能被$d$整除的小于$c$的正整数, 与$c$的选取矛盾. 所以$d$能整除$D$中的任何元素.

反证法+构造

设$\sqrt{2}$是有理数, 容易知道它在1和2之间取值. 取最小的自然数$q$使得$p=q\sqrt{2}$是整数. 则$q<p=q\sqrt{2}<2q$. 于是直接计算

而由$q<p<2q$知, $0<p-q<q$. 上式说明$2q-p=(p-q)\sqrt{2}$是整数, 这与$q$的选取矛盾.

注: 这里提一下上面的分式是如何想到的, 主要是用到合分比公式(初中):

然后注意到

反证法+Newton迭代法+Pell方程

考虑函数$f(x)=x^{2}-2$的Newton方法, 得到递推公式

记$x_{n}=\frac{p_{n}}{q_{n}}$, 带入上式有

利用归纳法证明$\left(p_{n},q_{n}\right)$是Pell方程$x^{2}-2y^{2}=1$的整数解. 其实只需要验证下面两个式子:

由此可得不等式$\frac{2}{x_{n}}<\sqrt{2}<x_{n}$.

设$\sqrt{2}=\frac{s}{t}$为有理数. 则有不等式估计

因此$\left|tp_{n}-sq_{n}\right|<\frac{t}{p_{n}}$. 由于$p_{n}$的递推公式知, $p_{n}\to\infty$, $n\to\infty$. 所以当$n$充分大时, $\left|tp_{n}-sq_{n}\right|<1$. 所以只能有$tp_{n}-sq_{n}=0$, 并有$x_{n}=\sqrt{2}$. 矛盾.