CS70Disc 03A

聚会技巧：最后一位数字

问题陈述

在庆祝 CS 70 期中考试结束的聚会上，展示你的模算术技巧，快速找出以下数字的最后一位数字：

1. 1. 找出 $ 11^{3142} $ 的最后一位数字。
2. 2. 找出 $ 9^{9999} $ 的最后一位数字。
3. 3. 找出 $ 3^{641} $ 的最后一位数字。

解决方案

(a) 计算 $ 11^{3142} $ 的最后一位数字

• 步骤：
  • 我们注意到 $ 11 $。
  • 因此，$ 11^{3142} ^{3142} $。
• 结论：最后一位数字是 1。

---

(b) 计算 $ 9^{9999} $ 的最后一位数字

• 方法一：
  • $ 9 $ 是它自己的模 $ 10 $ 乘法逆元，所以 $ 9^2 $。
  • 因此，$ 9^{9999} = 9^{2 + 1} = (9²⁾{4999} ^{4999} $。
• 方法二：
  • 我们知道 $ 9 \(，所以：\) 9^{9999} (-1)^{9999} $
  • 你也可以使用这个方法说： $ 9^{9999} (-1)^{9998} $
• 结论：最后一位数字是 9。

---

(c) 计算 $ 3^{641} $ 的最后一位数字

• 步骤：
  • 注意到 $ 3^4 = 81 $，所以我们可以将 $ 641 $ 除以 $ 4 \(：\) 641 = 4 + 1 $ 因此，$ 3^{641} $ 可以写成： $ 3^{641} = 3^{4 + 1} = (3⁴⁾{160} ^{160} $
• 结论：最后一位数字是 3。

---

模算术混合问题

问题陈述

证明或反驳以下语句：

1. 1. 存在某个 $ x $ 使得 $ x $ 且 $ x $。
2. 2. $ 2x x $。
3. 3. $ 2x x $。

解决方案

(a) 存在性问题

• 答案：不可能。
• 解释：假设存在一个 $ x $ 同时满足两个方程。

  • 从 $ x \(，我们可以写成：\) x = 3 + 16k (k ) $ 由此得出 $ x $，即 $ x $ 是奇数。

  • 从 $ x \(，我们可以写成：\) x = 4 + 6l (l ) $ 由此得出 $ x $，即 $ x $ 是偶数。

  • 现在我们得到了两个矛盾的结论：$ x $ 和 $ x $。因此，这个方程组没有解。

---

(b) 等价性问题

• 答案：假。
• 解释：考虑 $ x $ 的情况。

  • 对于 $ 2x $，代入 $ x = 8 \(：\) 2 = 16 $ 这个方程成立。

  • 但是对于 $ x $，代入 $ x = 8 \(：\) 8 $ 这个方程不成立。因此，$ 2x $ 不等价于 $ x $。

  • 另外，不能简单地消去第一个方程中的 2 得到第二个方程，因为 2 在模 12 下没有乘法逆元，因为 $ (2, 12) $。

---

(c) 等价性问题

• 答案：真。
• 解释：我们可以将 $ 2x $ 写成： $ 2x = 4 + 12k (k ) $ 除以 2，得到： $ x = 2 + 6k (k ) $ 这等价于说 $ x $。

---

模逆的存在性与唯一性

定义

设 $ a, m $ 且 $ m > 0 $，如果存在 $ x $ 满足： $ ax $ 则称 $ x $ 是 $ a $ 对 $ m $ 的模逆。

问题陈述

我们将调查模逆的存在性和唯一性：

1. 1. 3 是否是 5 对模 10 的模逆？
2. 2. 3 是否是 5 对模 14 的模逆？
3. 3. 对于所有 $ n \(，\) 3 + 14n $ 是否是 5 对模 14 的模逆？
4. 4. 4 是否有模逆对模 8？
5. 5. 假设 $ x, x' $ 都是 $ a $ 对模 $ m $ 的模逆，是否可能 $ x x' $？

解决方案

(a) 是否是模逆？

• 答案：否。
• 解释：计算 $ 3 = 15 \(，然后求模：\) 15 = 5 $ 因此，$ 3 $，而不是 1，所以 3 不是 5 对模 10 的模逆。

---

(b) 是否是模逆？

• 答案：是。
• 解释：计算 $ 3 = 15 \(，然后求模：\) 15 = 1 $ 因此，$ 3 $，所以 3 是 5 对模 14 的模逆。

---

(c) 对于所有 $ n $，是否是模逆？

• 答案：是。
• 解释：计算 $ (3 + 14n) \(：\) (3 + 14n) = 15 + 70n $ 然后求模： $ 15 + 70n $ 因为 $ 70n $ 是 14 的倍数，所以 $ 15 = 1 $ 因此，$ (3 + 14n) $，所以 $ 3 + 14n $ 是 5 对模 14 的模逆。

---

(d) 是否有模逆？

• 答案：否。
• 解释：假设存在 $ x $ 使得 $ 4x $。
  • 则有 $ 4x - 1 = 8k $ 对于某个 $ k $。
  • 这意味着 $ 4x = 8k + 1 $，因此 $ 4x $ 是奇数，而 $ 4x $ 只能是偶数。这是矛盾的，因此 4 对模 8 没有模逆。

---

(e) 是否可能不同的模逆？

• 答案：否。
• 解释：假设 $ x $ 和 $ x' $ 都是 $ a $ 对模 $ m $ 的模逆，则有： $ xa x'a $ 由此得： $ xa - x'a $ 简化可得： $ a(x - x') $ 这意味着 $ m $ 必须整除 $ a(x - x') $。如果 $ (a, m) = 1 $，则 $ x - x' $，即 $ x x' $。因此，不同的模逆是不可能的。

---

斐波那契数列的GCD性质

问题陈述

斐波那契数列定义为：

• $ F_0 = 0 $
• $ F_1 = 1 $
• 对于 $ n \(，\) F_n = F_{n-1} + F_{n-2} $

证明对于所有 $ n \(，都有：\) (F_n, F_{n-1}) = 1 $

解决方案

使用数学归纳法进行证明

1. 基础案例：
   • 当 $ n = 1 $ 时： $ (F_1, F_0) = (1, 0) = 1 $
   • 这是正确的。
2. 归纳假设：
   • 假设对于某个 $ k \(，有：\) (F_k, F_{k-1}) = 1 $
3. 归纳步骤：
   • 现在需要证明： $ (F_{k+1}, F_k) = 1 $
   • 根据斐波那契数列的定义，我们有： $ F_{k+1} = F_k + F_{k-1} $
   • 因此， $ (F_{k+1}, F_k) = (F_k + F_{k-1}, F_k) $
   • 根据欧几里得算法的性质，我们有： $ (x, y) = (y, x y) $
   • 这里，$ x = F_{k+1} = F_k + F_{k-1} $ 和 $ y = F_k \(：\) (F_{k+1}, F_k) = (F_k, F_{k-1}) $
   • 根据归纳假设，我们知道： $ (F_k, F_{k-1}) = 1 $
   • 因此： $ (F_{k+1}, F_k) = 1 $
4. 结论：
   • 通过数学归纳法，我们已经证明了对于所有 $ n \(，都有：\) (F_n, F_{n-1}) = 1 $

解释

• 斐波那契数列的定义意味着每一个数都是前两个数的和。通过归纳法，我们首先验证了基础情况（$ n = 1 $），然后假设对于某个 $ k $ 成立，再证明对于 $ k+1 $ 也成立。
• 重要的是使用了欧几里得算法的性质，表明两个数的最大公约数可以通过替换为其余数来计算，这使得我们能够通过归纳假设来完成证明。
• 这一性质表明，斐波那契数列中的相邻数之间总是互质，这在数论和组合数学中是一个有趣且重要的结果。

---