知识焦点
先建立概念地图
- modular-arithmetic
- modular-inverse
- Fibonacci
- GCD
- Euclidean-algorithm
- induction
CS70 · 讨论课 03a
本节涵盖模运算求末位数字、模方程的真假证明与反例、模逆元的存在性与唯一性，以及斐波那契数列相邻项最大公因数为 1 的归纳证明。
知识焦点
建议顺序
先完整作答，再按需展开提示；最后才展开官方参考解答并逐步核对证明与计算。
本地来源
题面与解答均由本地一手资料整理：discussion/dis03a.pdf、solutions/discussion/dis03a-sol.pdf
本地一手资料完整提取 · 讨论课
本节按本地一手资料完整整理，共 4 道大题。本地官方解答已完整收录并默认折叠；建议先独立完成，再逐题核对推导。
discussion/dis03a.pdf、solutions/discussion/dis03a-sol.pdf在庆祝你完成 CS 70 期中考试的聚会上，展示你的模运算（modular arithmetic）技能，快速求出下列各数的最后一位数字：
(a) 求 \(11^{3142}\) 的最后一位数字。
(b) 求 \(9^{9999}\) 的最后一位数字。
(c) 求 \(3^{641}\) 的最后一位数字。
最后一位数字等价于该数模 10 的余数。对于 (a)，先化简底数 \(11 \bmod 10\)；对于 (b)，注意到 \(9 \equiv -1 \pmod{10}\) 或 \(9^2 \equiv 1 \pmod{10}\)，利用循环节化简指数；对于 (c)，寻找 \(3^k \bmod 10\) 的循环周期，再用带余除法处理指数。
(a) 首先注意到 \(11 \equiv 1 \pmod{10}\)。因此 \[11^{3142} \equiv 1^{3142} \equiv 1 \pmod{10},\] 所以最后一位数字是 1。
(b) \(9\) 是模 10 下自身的乘法逆元，因此 \(9^2 \equiv 1 \pmod{10}\)。于是 \[9^{9999} = 9^{2 \cdot 4999} \cdot 9 \equiv 1^{4999} \cdot 9 \equiv 9 \pmod{10},\] 所以最后一位数字是 9。
另一条思路：我们知道 \(9 \equiv -1 \pmod{10}\)，因此 \[9^{9999} \equiv (-1)^{9999} \equiv -1 \equiv 9 \pmod{10}.\] 你也可以这样写： \[9^{9999} \equiv (-1)^{9998} \cdot 9 \equiv 9 \pmod{10}.\]
(c) 注意到 \(3^4 = 9^2\)，而 \(9^2 = 81 \equiv 1 \pmod{10}\)，因此 \(3^4 \equiv 1 \pmod{10}\)。又有 \[641 = 160 \cdot 4 + 1,\] 所以 \[3^{641} \equiv 3^{4 \cdot 160} \cdot 3 \equiv 1^{160} \cdot 3 \equiv 3 \pmod{10},\] 所以最后一位数字是 3。
解答来源：solutions/discussion/dis03a-sol.pdf · 1 · confidence: high
题面来源：discussion/dis03a.pdf · 1 · confidence: high
判断以下命题的真假，并给出证明或反例：
(a) 存在某个整数 \(x \in \mathbb{Z}\)，使得 \(x \equiv 3 \pmod{16}\) 且 \(x \equiv 4 \pmod{6}\)。
(b) \(2x \equiv 4 \pmod{12} \iff x \equiv 2 \pmod{12}\)。
(c) \(2x \equiv 4 \pmod{12} \iff x \equiv 2 \pmod{6}\)。
对于 (a)，从两个同余式分别考察 \(x\) 的奇偶性，看是否导出矛盾。对于 (b) 和 (c)，思考在什么条件下可以从 \(ax \equiv b \pmod{m}\) 两边同时消去 \(a\) —— 这与 \(a\) 在模 \(m\) 下是否存在乘法逆元（即 \(\gcd(a,m)=1\)）密切相关。
(a) 不可能。假设存在满足两个等式的整数 \(x\)。
由 \(x \equiv 3 \pmod{16}\)，可设 \(x = 3 + 16k\)，其中 \(k\) 为整数。由此可得 \(x \equiv 1 \pmod{2}\)。
由 \(x \equiv 4 \pmod{6}\)，可设 \(x = 4 + 6l\)，其中 \(l\) 为整数。由此可得 \(x \equiv 0 \pmod{2}\)。
于是我们同时得到 \(x \equiv 1 \pmod{2}\) 和 \(x \equiv 0 \pmod{2}\)，矛盾。
(b) 假命题。取 \(x \equiv 8 \pmod{12}\) 即可验证：\(2 \cdot 8 = 16 \equiv 4 \pmod{12}\)，但 \(8 \not\equiv 2 \pmod{12}\)。
我们无法从第一个等式两边消去 2 得到第二个等式，是因为 2 在模 12 下没有乘法逆元，即 2 与 12 不互素。
(c) 真命题。由 \(2x \equiv 4 \pmod{12}\) 可得 \(2x = 4 + 12k\)，其中 \(k \in \mathbb{Z}\)。两边除以 2，得 \(x = 2 + 6k\)，其中 \(k\) 为同一整数。这等价于 \(x \equiv 2 \pmod{6}\)。
解答来源：solutions/discussion/dis03a-sol.pdf · 1-2 · confidence: high
题面来源：discussion/dis03a.pdf · 1-2 · confidence: high
回顾课堂上的逆元（inverse）定义：设 \(a, m \in \mathbb{Z}\) 且 \(m > 0\)；若 \(x \in \mathbb{Z}\) 满足 \(ax \equiv 1 \pmod{m}\)，则称 \(x\) 为 \(a\) 模 \(m\) 的逆元。
现在，我们研究逆元的存在性与唯一性。
(a) \(3\) 是否是 \(5\) 模 \(10\) 的逆元？
(b) \(3\) 是否是 \(5\) 模 \(14\) 的逆元？
(c) 对每个形如 \(3 + 14n\)（其中 \(n \in \mathbb{Z}\)）的整数，它是否是 \(5\) 模 \(14\) 的逆元？
(d) \(4\) 是否存在模 \(8\) 的逆元？
(e) 设 \(x, x' \in \mathbb{Z}\) 都是 \(a\) 模 \(m\) 的逆元。是否可能 \(x \not\equiv x' \pmod{m}\)？
按照逆元的定义逐一验证：计算 \(a \cdot x \bmod m\) 是否等于 1。对于 (c)，将 \(3 + 14n\) 整体代入验证。对于 (d)，考虑 \(4x - 1\) 是否能被 8 整除。对于 (e)，从 \(ax \equiv ax' \equiv 1 \pmod{m}\) 出发，利用其中一个逆元等式进行代换推导。
(a) 不是。因为 \(3 \cdot 5 = 15 \equiv 5 \pmod{10}\)，而 \(5 \neq 1 \pmod{10}\)。
(b) 是。因为 \(3 \cdot 5 = 15 \equiv 1 \pmod{14}\)。
(c) 是。因为 \[(3 + 14n) \cdot 5 = 15 + 14 \cdot 5n \equiv 15 \equiv 1 \pmod{14}.\]
(d) 不存在。用反证法，假设存在 \(x \in \mathbb{Z}\) 为 4 模 8 的逆元，则 \(4x \equiv 1 \pmod{8}\)，即 \(8 \mid 4x - 1\)，这不可能。
(e) 不可能。由已知 \(xa \equiv x'a \equiv 1 \pmod{m}\)，所以 \[xa - x'a = a(x - x') \equiv 0 \pmod{m}.\] 两边同乘 \(x\)，得 \[xa(x - x') \equiv 0 \cdot x \pmod{m}\] \[\implies x - x' \equiv 0 \pmod{m}\] \[\implies x \equiv x' \pmod{m}.\]
解答来源：solutions/discussion/dis03a-sol.pdf · 2 · confidence: high
题面来源：discussion/dis03a.pdf · 2 · confidence: high
斐波那契（Fibonacci）数列由 \(F_n = F_{n-1} + F_{n-2}\) 给出，其中 \(F_0 = 0\)，\(F_1 = 1\)。证明：对所有 \(n \geq 1\)，有 \[\gcd(F_n, F_{n-1}) = 1.\]
用数学归纳法。关键在于归纳步骤中利用斐波那契数列的递推关系 \(F_{k+1} = F_k + F_{k-1}\)，将其代入 \(\gcd(F_{k+1}, F_k)\)，再结合欧几里得算法（Euclid's GCD algorithm）进行化简。
用数学归纳法证明。
基础步骤：\(\gcd(F_1, F_0) = \gcd(1, 0) = 1\)，成立。
归纳假设：假设对于某个 \(k \geq 1\)，有 \(\gcd(F_k, F_{k-1}) = 1\)。
归纳步骤：需要证明 \(\gcd(F_{k+1}, F_k) = 1\)。
我们有： \[\gcd(F_{k+1}, F_k) = \gcd(F_k + F_{k-1}, F_k) = \gcd(F_k, F_{k-1}) = 1.\] 其中第二个等式来自斐波那契数的定义，最后一个等式来自欧几里得算法，即 \(\gcd(x, y) = \gcd(y, x \bmod y)\)，因为 \[F_k + F_{k-1} \equiv F_{k-1} \pmod{F_k}.\]
因此命题对 \(n = k + 1\) 也成立。
由数学归纳法可知，对所有 \(n \geq 1\)，\(\gcd(F_n, F_{n-1}) = 1\)，其中 \(F_0 = 0\)，\(F_1 = 1\)，且 \(F_n = F_{n-1} + F_{n-2}\)。
解答来源：solutions/discussion/dis03a-sol.pdf · 2-3 · confidence: high
题面来源：discussion/dis03a.pdf · 2 · confidence: high
discussion/dis03a.pdfsolutions/discussion/dis03a-sol.pdf