0.2 间接证明法

0.2.1 $\quad$ 请用反证法证明以下命题。

$\\$ 1. 若$p \gt 2$是素数，则$p$是奇数。$\\$ 2. 对正整数$n$，若$n^2$是奇数，则$n$是奇数。$\\$ 3. 不存在最小的正有理数。$\\$ 1.证明：$\\$ 假设命题不成立，即存在素数$p \gt 2$但$p$是偶数，于是$2$是$p$的一个因数，这与素数性质矛盾。$\\$ 2.证明：$\\$ 假设命题不成立，即存在$n^2$是奇数但$n$是偶数，于是存在正整数$k$满足$n=2k$，但此时$n^2=4k^2$也是偶数，矛盾。$\\$ 3.证明：$\\$ 假设命题不成立。设$q$是最小的正有理数，显然有$\frac{q}{2} \lt q$也是正有理数，矛盾。$\\$

0.2.2 $\quad$ 存在两个无理数$a,b$，满足$a^b$是一个有理数。请先假设$\sqrt{2}^{\sqrt{2}}$是有理数，再假设$\sqrt{2}^{\sqrt{2}}$是无理数。针对两种情形讨论来证明这个命题。

$\\$ 证明：$\\$ 分两种情况讨论：$\\$ (a) 若$\sqrt{2}^{\sqrt{2}}$是有理数。命题显然成立。$\\$ (b) 若$\sqrt{2}^{\sqrt{2}}$是无理数。令$p=\sqrt{2}^{\sqrt{2}}$，则$p^{\sqrt{2}}=(\sqrt{2})^2=2$是有理数。命题也成立。$\\$ 于是存在两个无理数$a,b$，满足$a^b$是一个有理数。$\\$

0.2.3 $\quad$ 证明$2^{2^{n-1}}-1$必然至少有互异的$n-1$个奇素因数。(因此第$n$个素数$p_n$一定小于等于$2^{2^{n-1}}.$)

$\\$ 证明：$\\$ 反复利用因式分解得$$2^{2^{n-1}}-1=(2^{2^{n-2}}+1)(2^{2^{n-3}}+1)\cdots(2^{2^{0}}+1)$$这样就得到了$n-1$个奇因数。分两种情况讨论：$\\$ (a) 若这些奇因数均为素数，命题显然成立。$\\$ (b) 若这些奇因数不全为素数，则那些不是素数的奇因数又可以分解出至少一个奇素因数。而$m\neq n$时，$2^{2^{m}}+1$与$2^{2^{n}}+1$互素，即对不同正整数$k$，$2^{2^{k}}+1$分解得到的奇素因数完全不同。于是$2^{2^{n-1}}-1$至少有互异的$n-1$个奇素因数。$\\$

0.2.4 $\quad$ 假设有一个$a \times b$的巧克力排块，我们需要将他掰成$1 \times 1$的小块，在掰的同时会被打分。假设掰一次将$x+y$块掰成了$x$块和$y$块，则得分$xy$。证明：当巧克力被完全掰成$1 \times 1$的小块时，总得分永远为$\cfrac{1}{2}ab(ab-1).\\$

证明：$\\$ 用数学归纳法。$a=b=1$时显然成立。设排块形状小于$a \times b$时均成立。考虑$a \times b$排块。$\\$ 若将$a$行排块掰成$k$行和$a-k$行，则得分$kb(a-k)b$，还剩下$k\times b$排块和$(a-k)\times b$排块，由归纳假设，最后得分为$$kb(a-k)b+\cfrac{1}{2}kb(kb-1)+\cfrac{1}{2}(a-k)b((a-k)b-1)=\cfrac{1}{2}ab(ab-1)$$