• https://www.eecs70.org/assets/pdf/notes/n2.pdf
• https://www.eecs70.org/assets/pdf/mini-vitamins/mini-vitamin-0b.pdf

CS 70 离散数学与概率论笔记：证明方法专题 (Proofs)

本笔记基于 UC Berkeley CS 70 Course Note 2 整理，结合个人手写笔记的框架逻辑进行了完善和深度润色。

1. 证明的定义与结构 (Proofs: Definition and Structure)

什么是证明？

在自然科学中，我们通过实验积累证据来“断言”一个命题的正确性。但在数学中，我们追求的是绝对的确定性 (Absolute Certainty)。

• 证明 (Proof) 是由有限个逻辑推理步骤 (a finite sequence of logical deductions) 组成的序列，用以确立目标命题的绝对真理性。
• 证明的强大之处在于：用有限的步骤，去保证包含无限种可能性的命题的真理性。这与计算机程序（在有限的代码内处理无限的输入）有着深度的历史渊源。

证明的基本结构

一个严谨的数学证明通常由以下结构组成：

1. 从公理或假设出发：
   • 公理 (Axioms / Postulates)：无需证明即可接受的根本性陈述（证明必须有起点）。
   • 前提假设 (Assumptions)：在具体定理中假设为真的条件。
2. 通过逻辑推理 (Logical Deductions) 逐步推进：
   • 应用严谨的逻辑规则，每一步推出的新陈述，在前一步为真的前提下都必须绝对成立。
3. 得出最终结论 (Conclusion)。

2. 记号与基本事实 (Notation and Basic Facts)

在进行严谨的证明前，我们需要统一定义语言和符号：

• 常用数集：

  • $\mathbb{Z}$：整数集，即 $\mathbb{Z} = \{..., -2, -1, 0, 1, 2, ...\}$。
  • $\mathbb{N}$：自然数集，即 $\mathbb{N} = \{0, 1, 2, ...\}$（注意：在 CS 70 中，自然数包含 $0$）。
  • $\mathbb{Z}^+$：正整数集，即 $\{1, 2, 3, ...\}$。

• 封闭性 (Closure Property)：整数集 $\mathbb{Z}$ 和自然数集 $\mathbb{N}$ 对加法和乘法是封闭的（即两个整数相加或相乘，其结果依然是整数）。

• 整除 (Divisibility)： 对于整数 $a$ 和 $b$，我们说 $a$ 整除 $b$（记作 $a \mid b$），当且仅当存在一个整数 $q$ 使得：

  $b = aq$

  例如：$2 \mid 10$，因为存在整数 $q = 5$ 使得 $10 = 5 \cdot 2$。

• 素数 (Prime Number)：一个大于等于 2 的自然数 $p \ge 2$，若它仅能被 $1$ 和它本身整除，则称其为素数。

• 定义符号 :=：用于明确定义一个新变量。例如 $q := 6$ 表示“定义变量 $q$ 的值为 $6$”。

3. 直接证明 (Direct Proof)

💡 核心思想与套路模板

直接证明是最基础、最直观的证明方法。对于蕴含式命题 $P \Rightarrow Q$（若 $P$ 成立，则 $Q$ 成立），直接证明的通用模板如下：

直接证明套路模板

• 目标 (Goal): 证明 $P \Rightarrow Q$
• 方法 (Approach):
  1. 假设 $P$ 成立（Assume $P$）
  2. 通过代数变形或逻辑推理，一步一步推导…
  3. 得出 $Q$ 成立（Therefore $Q$）

如何证明一个等价命题（双向蕴含）？

当我们需要证明一个“当且仅当 (if and only if)”的等价命题 $A \iff B$ 时，直接证明的经典策略是将其拆解为两个单向蕴含命题，然后分别予以证明：

$A \iff B \quad \text{拆解为} \quad (A \Rightarrow B) \wedge (B \Rightarrow A)$

• 第一步：证明充分性 ($A \Rightarrow B$)
• 第二步：证明必要性 ($B \Rightarrow A$)

经典定理与步骤拆解

定理 2.1

对于任意 $a, b, c \in \mathbb{Z}$，若 $a \mid b$ 且 $a \mid c$，则 $a \mid (b + c)$。

概念自测：该定理用一阶逻辑符号可表示为 $(\forall a,b,c \in \mathbb{Z})((a \mid b \wedge a \mid c) \Rightarrow a \mid (b + c))$。

证明：

1. 假设前提：假设 $a \mid b$ 且 $a \mid c$。

2. 展开定义：根据整除定义，存在整数 $q_1, q_2 \in \mathbb{Z}$ 满足：

   $b = q_1 a \quad \text{且} \quad c = q_2 a$

3. 代数推导：将它们相加：

   $b + c = q_1 a + q_2 a = (q_1 + q_2) a$

4. 得出结论：因为整数对加法具有封闭性，所以 $(q_1 + q_2) \in \mathbb{Z}$。由此可得 $a \mid (b + c)$。 $\square$

💡 难点深度解析：定理 2.2 与 定理 2.3 的“联立理解”

在阅读这两个关于“数字之和被 9 整除”的定理时，你可能会觉得逻辑和代数符号有些绕。让我们在这里将它们彻底拆解，并联立起来看：

这两个定理其实完整地证明了一个等价关系：一个三位数 $n$ 能被 9 整除，当且仅当它的各位数字之和能被 9 整除。

设三位数 $n$ 的百位、十位、个位数分别为 $a, b, c$（其中 $0 < n < 1000$）。 我们可以将 $n$ 写作十进制代数式：

$n = 100a + 10b + c$

同时，其各位数字之和为 $a + b + c$。

定理 2.2 (正向：数字和整除 $\Rightarrow$ 原数整除)

设 $0 < n < 1000$ 为整数。如果 $n$ 的各位数字之和能被 9 整除，那么 $n$ 也能被 9 整除。

证明：

1. 假设前提：设数字之和能被 9 整除，即存在整数 $k \in \mathbb{Z}$ 使得：

   a + b + c = 9k \tag{1}

2. 代数变形（核心巧妙之处）： 我们将原数 $n = 100a + 10b + c$ 进行重组，分离出能够显而易见被 9 整除的部分：

   $n = (99a + a) + (9b + b) + c$

   $n = (99a + 9b) + (a + b + c)$

3. 代入假设 (1)：

   $n = 99a + 9b + 9k = 9(11a + b + k)$

4. 得出结论：因为 $a, b, k$ 均为整数，所以 $(11a + b + k) \in \mathbb{Z}$。因此 $n$ 能被 9 整除。 $\square$

定理 2.3 (逆向：原数整除 $\Rightarrow$ 数字和整除)

设 $0 < n < 1000$ 为整数。如果 $n$ 能被 9 整除，那么 $n$ 的各位数字之和也能被 9 整除。

证明：

1. 假设前提：设 $n$ 能被 9 整除，即存在整数 $l \in \mathbb{Z}$ 使得：

   $n = 9l$

2. 代数变形：用数位表示 $n$：

   $100a + 10b + c = 9l$

   $99a + 9b + (a + b + c) = 9l$

3. 分离目标项 $a+b+c$：

   $a + b + c = 9l - 99a - 9b$

   $a + b + c = 9(l - 11a - b)$

4. 得出结论：设 $k = l - 11a - b$。由于 $l, a, b$ 是整数，所以 $k$ 也是整数。故各位数字之和 $a + b + c = 9k$ 能被 9 整除。 $\square$

💡 起承转合思考： 联立定理 2.2 和 定理 2.3，我们就完美证明了：

$9 \mid (a+b+c) \iff 9 \mid n$

这就是我们小学学到的“能被9整除的数的特征”的严谨数学证明！

补充直接证明简单例题

为了让你更好地巩固这个套路，我们来看一个简单的经典例题：

例题：证明：若 $n$ 是奇数，则 $n^2$ 也是奇数。

证明：

1. 假设前提：假设 $n$ 是奇数。

2. 写出定义式：根据奇数的定义，存在整数 $k \in \mathbb{Z}$ 使得：

   $n = 2k + 1$

3. 代数平方：

   $n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$

4. 得出结论：因为 $k$ 是整数，所以 $m := 2k^2 + 2k$ 也是整数。因此 $n^2 = 2m + 1$ 符合奇数的定义，所以 $n^2$ 是奇数。 $\square$

4. 逆否命题证明 (Proof by Contraposition)

💡 为什么需要逆否命题证明？（承前启后）

在尝试使用直接证明时，我们有时会陷入僵局。例如，在要证明“若 $n^2$ 是偶数，则 $n$ 是偶数”时，如果假设 $n^2 = 2k$，我们很难直接对 $n = \sqrt{2k}$ 展开奇偶性讨论，因为根号破坏了整数的代数结构。 此时，利用命题逻辑的等价律 $P \Rightarrow Q \equiv \neg Q \Rightarrow \neg P$，证明其逆否命题往往会柳暗花明！

💡 套路模板

逆否命题证明套路模板

• 目标 (Goal): 证明 $P \Rightarrow Q$
• 方法 (Approach):
  1. 假设结论的否定成立（Assume $\neg Q$）
  2. 通过逻辑推导…
  3. 证明前提的否定也成立（Therefore $\neg P$）
• 结论 (Conclusion): 因为 $\neg Q \Rightarrow \neg P$，根据逆否等价律，原命题 $P \Rightarrow Q$ 成立。

(注：在写证明时，在第一行明确写出“We proceed by contraposition（我们采用逆否命题证明法）”是极佳的写作习惯，能大大提高阅卷人的好感度。)

定理与证明

定理 2.4

设 $n$ 为正整数，且 $d$ 整除 $n$（即 $d \mid n$）。若 $n$ 是奇数，则 $d$ 是奇数。

直接证明为什么难？ 如果我们假设 $n$ 是奇数，我们只知道 $n = 2k+1$ 且 $n = dl$，此时很难直接拆解出 $d$ 的奇偶性。 而逆否命题是：“若 $d$ 是偶数，则 $n$ 是偶数”（即否定结论 $\Rightarrow$ 否定条件）。

证明：

1. 采用逆否命题法：假设 $d$ 是偶数。

2. 展开定义：根据偶数定义，存在整数 $k \in \mathbb{Z}$ 使得 $d = 2k$。

3. 结合已知条件 $d \mid n$：这意味着存在整数 $l \in \mathbb{Z}$ 使得 $n = dl$。

4. 代数代入：将 $d = 2k$ 代入：

   $n = (2k)l = 2(kl)$

5. 得出结论：因为 $k, l$ 均为整数，所以 $kl$ 也是整数。因此 $n$ 是偶数。

6. 根据逆否命题的等价性，原命题“若 $n$ 是奇数，则 $d$ 是奇数”成立。

定理 2.5：鸽巢原理 (Pigeonhole Principle)

设 $n$ 和 $k$ 为正整数。将 $n$ 个物体放入 $k$ 个盒子中。如果 $n > k$，那么至少有一个盒子包含多个（即 $\ge 2$ 个）物体。

这是一个极其经典且看似直观、实则极强大的原理。我们用逆否命题来极简地证明它。

• 否定结论 $\neg Q$：所有盒子都包含最多一个物体（即每个盒子的物体数 $\le 1$）。
• 否定条件 $\neg P$：物体的总数 $n \le k$。

证明：

1. 采用逆否命题法：假设每一个盒子中最多只放了 1 个物体。

2. 累加物体总量：由于一共有 $k$ 个盒子，因此所有盒子里的物体总数 $n$ 满足：

   $n \le 1 \times k = k$

3. 由于这证明了 $\neg Q \Rightarrow \neg P$，因此其等价的逆否命题 $P \Rightarrow Q$ 成立：即若 $n > k$，至少有一个盒子包含多个物体。 $\square$

💡 现实中有趣的例子： 根据鸽巢原理，旧金山（人口超 80 万）一定有至少两个人的头发根数完全相同！

• 盒子 (Boxes): 头发的根数（假设人头上的发量上限为 50 万根，即盒子的编号为 $0$ 到 $500,000$，共 $500,001$ 个盒子）。
• 物体 (Objects): 旧金山的居民（超过 800,000 人）。
• 由于“物体数 $n$” > “盒子数 $k$”，必然有至少两个居民掉进同一个“发量盒子”里！

5. 反证法 (Proof by Contradiction)

💡 核心思想：reductio ad absurdum（归于荒谬）

反证法是数学中最迷人的武器之一。当你想证明一个命题 $P$ 为真时，你先假设它是假的（即假设 $\neg P$ 成立），然后进行一系列合法的逻辑推导，最终推导出一个极其荒谬的、自我矛盾的结论（例如 $1=2$，或者某个数既是偶数又是奇数）。因为推导过程无误，唯一的错误只能是你的假设 $\neg P$，从而逼迫我们承认 $P$ 必须为真。

反证法套路模板

• 目标 (Goal): 证明命题 $P$ 为真
• 方法 (Approach):
  1. 假设 $\neg P$ 成立（假设命题为假）。
  2. 开展推理，推导出某个陈述 $R$ 和它的否定 $\neg R$ 同时成立（即 $R \wedge \neg R$，产生矛盾）。
  3. 宣布“这不可能，产生了矛盾！”
• 结论 (Conclusion): 假设不成立，因此 $P$ 必须为真。

💡 什么时候用反证法最合适？

手写笔记中提到的一点非常关键：当我们要证明“某样东西不存在”或者“是无限的”时候，反证法是最好的选择。

• 证明“无限” $\Rightarrow$ 反设“有限”（有限个就可以排出来、相乘，非常方便）。
• 证明“不存在” $\Rightarrow$ 反设“存在”（既然存在，就可以写成代数式 $a/b$ 或具体的变量来算，从而制造矛盾）。

定理与证明

定理 2.6：素数有无穷多个

这是由古希腊数学家欧几里得在 2000 多年前做出的伟大证明。

证明所用引理 2.1：任何大于 1 的自然数要么是素数，要么能被某个素数整除。

反证法证明：

1. 反设：假设定理不成立，即素数只有有限多个，设为 $k$ 个：

   $\{p_1, p_2, p_3, ..., p_k\}$

2. 构造新数：定义一个新数 $q$，它是所有这些有限素数的乘积再加上 1：

   $q := (p_1 \cdot p_2 \cdot p_3 \cdots p_k) + 1$

3. 分析 $q$ 的整除性：

   • 首先，$q$ 显然比已知的任何素数 $p_i$ 都大，所以 $q$ 本身不在我们的素数列表里，即 $q$ 不是素数。
   • 根据引理 2.1，因为 $q$ 不是素数，它必须能被某个素数 $p$ 整除。
   • 既然 $p$ 是素数，它必须是我们列表 $\{p_1, ..., p_k\}$ 中的某一个。

4. 制造矛盾：

   • 因为 $p$ 是列表中的某一个，所以 $p$ 显然能整除乘积项 $r = p_1 p_2 \cdots p_k$。

   • 根据定理 2.1 的整除性质，由于 $p \mid q$ 且 $p \mid r$，那么 $p$ 也必须能整除它们的差：

     $p \mid (q - r) \implies p \mid 1$

   • 但是，没有任何素数（素数都 $\ge 2$）能整除 1！我们得出了一个荒谬的结论 $p \mid 1$。

5. 结论：产生矛盾，反设不成立，因此素数必定有无穷多个。 $\square$

定理 2.7：$\sqrt{2}$ 是无理数

证明所用引理 2.2：若 $a^2$ 是偶数，则 $a$ 也是偶数。（在第9节课后习题中要求证明，我们在此使用它）。

反证法证明：

1. 反设：假设 $\sqrt{2}$ 是有理数。

2. 写出定义式：根据有理数的定义，$\sqrt{2}$ 可以写成两个整数之比：

   $\sqrt{2} = \frac{a}{b} \quad (b \neq 0)$

   并且，我们可以假设这个分数已经约分到了最简形式，即 $a$ 和 $b$ 没有大于 1 的公因数（记为命题 $R$）。

3. 代数推导：

   • 两边平方：$2 = \frac{a^2}{b^2} \implies a^2 = 2b^2$。
   • 因为 $b^2$ 是整数，所以 $a^2$ 必定是偶数。
   • 根据引理 2.2，既然 $a^2$ 是偶数，那么 $a$ 也必定是偶数。
   • 因此，我们可以将 $a$ 写为 $a = 2c$（其中 $c \in \mathbb{Z}$）。

4. 继续推导 $b$：

   • 将 $a = 2c$ 代入原方程：$(2c)^2 = 2b^2 \implies 4c^2 = 2b^2 \implies b^2 = 2c^2$。
   • 因为 $c^2$ 是整数，所以 $b^2$ 是偶数。
   • 再次应用引理 2.2，$b$ 也必定是偶数。

5. 产生矛盾：

   • 我们证明了 $a$ 和 $b$ 都是偶数，这意味着它们共享公因数 2（即 $\neg R$）。
   • 这与我们最初的假设“$a$ 和 $b$ 互质、没有大于 1 的公因数（最简分数）”直接矛盾！

6. 结论：假设不成立，$\sqrt{2}$ 必须是无理数。 $\square$

6. 分情况证明 (Proof by Cases)

💡 核心思想

有时候，我们无法一步到位证明一个结论，但我们可以把问题空间划分为几种互斥且完备的可能情况 (Cases)。只要我们在每一种情况下都能证明结论成立，那么整个定理就必定成立。

定理 2.8：存在无理数 $x$ 和 $y$，使得 $x^y$ 是有理数

这个定理非常有趣，它向我们展示了分情况证明法的威力，同时也带来了一个极其惊艳的概念——非构造性证明 (Non-constructive Proof)。

证明：

1. 我们已知 $\sqrt{2}$ 是无理数（由定理 2.7 证得）。

2. 我们尝试令 $x = \sqrt{2}$ 且 $y = \sqrt{2}$。现在来看数：

   $\sqrt{2}^{\sqrt{2}}$

3. 我们不知道这个数到底是有理数还是无理数。但没关系，它只有两种可能。我们分情况讨论：

• 情况 (a)：若 $\sqrt{2}^{\sqrt{2}}$ 是有理数 那么我们已经找到了答案！此时令 $x = \sqrt{2}$（无理数），$y = \sqrt{2}$（无理数），得到的 $x^y = \sqrt{2}^{\sqrt{2}}$ 是有理数。命题成立。

• 情况 (b)：若 $\sqrt{2}^{\sqrt{2}}$ 是无理数 既然它是无理数，我们就可以用它来构造下一代： 令 $x = \sqrt{2}^{\sqrt{2}}$（根据假设是无理数），令 $y = \sqrt{2}$（无理数）。 现在我们计算 $x^y$：

  $x^y = \left(\sqrt{2}^{\sqrt{2}}\right)^{\sqrt{2}} = \sqrt{2}^{\sqrt{2} \cdot \sqrt{2}} = \sqrt{2}^2 = 2$

  而 $2$ 显然是有理数！命题依然成立。

由于情况 (a) 和情况 (b) 必有一个为真，所以在所有情况下，我们都成功证明了“存在这样的无理数 $x, y$ 使得 $x^y$ 为有理数”。 $\square$

💡 难点解析：什么是非构造性证明 (Non-constructive Proof)？

你在手写笔记里写道：“我没有看明白 non-constructive proof”。

通俗解释： 通常，如果一个数学定理说“存在一个宝藏 $X$”，我们习惯的证明方式是直接带读者去找，指着它说：“看，这就是 $X$！”（这叫构造性证明）。 但是在上面的证明中，我们证明完了之后，你如果问我：“所以，到底 $x=\sqrt{2}, y=\sqrt{2}$ 是我们要找的无理数对，还是 $x=\sqrt{2}^{\sqrt{2}}, y=\sqrt{2}$ 是我们要找的无理数对？” 数学家会耸耸肩回答你：“我也不知道。但我能向你 100% 保证，这两个组合里绝对有一个是正确的！”

这就是非构造性证明：我们通过严密的逻辑网（情况a和情况b的互斥性），证明了符合某种条件的数学对象“必定存在”，但却无需具体指出这个对象到底是谁。这展示了纯数学逻辑中超越直觉的奇妙魅力。

7. 证明中的常见错误 (Common Errors When Writing Proofs)

写证明是一门艺术，但初学者极易陷入思维误区。下面是三个在作业和考试中非常经典的“翻车现场”分析：

错误一：循环论证 / 假设了待证结论 (Circular Reasoning)

伪命题 Claim 2.1: $-2 = 2$

伪证明 False Proof: 假设 $-2 = 2$。对两边进行平方，得到 $(-2)^2 = 2^2$，即 $4 = 4$。由于 $4 = 4$ 显然成立，因此我们得出结论：$-2 = 2$。

• 错误根源解析： 你绝对不能把“想要证明的结论”作为推理的起点！ 在这个伪证明中，我们实际上证明的是：“如果 $-2 = 2$ 为真，那么我们可以推出 $4 = 4$ 这一真理”（即 $P \Rightarrow \text{True}$）。 但在逻辑学中，一个假命题完全可以推出一个真命题（例如：“如果太阳从西边升起，那么 $1+1=2$”在逻辑逻辑蕴含上是 True 的）。这完全无法证明前提 $P$ 自身为真！

错误二：忽略特殊情况——“除以零” (Dividing by Zero)

伪命题 Claim 2.2: $1 = 2$

伪证明 False Proof: 假设 $x = y$（$x, y$ 均为非零整数）。 两边同乘 $x$：$x^2 = xy$ 两边同时减去 $y^2$：$x^2 - y^2 = xy - y^2$ 因式分解：$(x - y)(x + y) = y(x - y)$ 两边同时除以 $(x - y)$：$x + y = y$ 既然 $x = y$，代入得：$y + y = y \implies 2y = y$ 两边同时除以 $y$（因为 $y \neq 0$）：$2 = 1$。

• 错误根源解析： 问题出在这一步：“两边同时除以 $(x-y)$”。 因为我们最开始假设了 $x = y$，所以 $x - y = 0$。在数学中，除以 0 是没有定义的！一旦你在代数推理中悄悄除以了 0，接下来的所有推导都会坍塌，并能推出任何荒谬的结论（比如 $1=2$）。

错误三：不等式平方与负数处理 (Inequalities & Negatives)

伪命题 Claim 2.3: $4 \le 1$

伪证明 False Proof: 我们已知 $-2 \le 1$ 是成立的。对不等式两边同时平方，得到 $4 \le 1$。由于每一步都有依据，所以结论成立。

• 错误根源解析： 不等式不满足“若 $a \le b$，则 $a^2 \le b^2$”。 只有在两边都是非负数（即 $0 \le a \le b$）时，平方才保持不等号方向。 如果是负数，平方会改变绝对值的大小。例如，若 $a < b$，其绝对值 $|a| \le |b|$ 并不一定成立（本例中 $|-2| > |1|$，故平方后不等号反向）。 另外要记住：不等式两边同乘负数时，不等号必须改变方向！

8. 课后习题自我提升 (Exercises Solutions)

习题 1：推广定理 2.2 的证明到任意位数的正整数 $n$

题目：推广定理 2.2 的证明，使其适用于任意正整数 $n$。（提示：假设 $n$ 有 $k$ 位数字，其各位数字写为 $a_i$，因此 $n = \sum_{i=0}^{k-1} a_i \cdot 10^i$。）

解答证明：

1. 表示原数 $n$： 任何一个 $k$ 位正整数 $n$ 可以用十进制展开式写作：

   $n = a_{k-1} \cdot 10^{k-1} + a_{k-2} \cdot 10^{k-2} + \cdots + a_1 \cdot 10^1 + a_0 \cdot 10^0 = \sum_{i=0}^{k-1} a_i \cdot 10^i$

   其中其各位数字之和为 $\sum_{i=0}^{k-1} a_i$。

2. 建立假设：假设各位数字之和能被 9 整除，即存在 $m \in \mathbb{Z}$，满足：

   $\sum_{i=0}^{k-1} a_i = 9m$

3. 代数重组： 注意到对于任意非负整数 $i$，$10^i - 1$ 是一个由 $i$ 个 9 组成的数（例如 $10^2 - 1 = 99$, $10^3 - 1 = 999$），因此 $10^i - 1$ 必定能被 9 整除。 我们可令 $10^i = (10^i - 1) + 1$，代入原数 $n$ 的代数式中：

   $n = \sum_{i=0}^{k-1} a_i \big((10^i - 1) + 1\big) = \sum_{i=0}^{k-1} a_i (10^i - 1) + \sum_{i=0}^{k-1} a_i$

4. 提取公因数 9： 因为 $10^i - 1$ 总是 9 的倍数，我们可以将其写为 $10^i - 1 = 9C_i$（其中 $C_i$ 是整数）。 代入上式并结合我们的假设：

   $n = \sum_{i=0}^{k-1} a_i (9C_i) + 9m = 9 \left( \sum_{i=0}^{k-1} a_i C_i + m \right)$

5. 结论：由于小括号内全是整数的和与乘积，其结果必为整数。因此，任意正整数 $n$ 如果其各位数字之和能被 9 整除，则 $n$ 本身必能被 9 整除。 $\square$

习题 2：证明引理 2.2

题目：证明：对于任意整数 $a$，若 $a^2$ 是偶数，则 $a$ 也是偶数。并思考：直接证明和逆否命题证明，哪种更适合解决这个问题？

解答分析：

• 若尝试直接证明：假设 $a^2 = 2k$，我们得到 $a = \sqrt{2k}$。在实数范围内，我们很难直接推导出 $\sqrt{2k}$ 是一个偶整数，因为根号运算打破了整数的离散和代数结构。因此，直接证明极不适合此题。
• 若采用逆否命题证明：
  • 原命题：若 $a^2$ 是偶数 $\Rightarrow a$ 是偶数。
  • 逆否命题：若 $a$ 是奇数 $\Rightarrow a^2$ 是奇数。 这个逆否命题非常容易证明！

逆否命题法证明：

1. 假设前提：假设 $a$ 是奇数。

2. 写出代数式：存在整数 $k \in \mathbb{Z}$，使得 $a = 2k + 1$。

3. 计算平方 $a^2$：

   $a^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$

4. 得出结论：因为 $k \in \mathbb{Z}$，所以 $2k^2 + 2k$ 也是整数。这符合奇数的定义，因此 $a^2$ 是奇数。

5. 根据逆否命题的等价性，原命题“若 $a^2$ 是偶数，则 $a$ 是偶数”成功立论。 $\square$