扩展欧几里得（递归与迭代）、CRT 练习、Baby Fermat

解答：

(a) 将等式 \(54a + 17b = 1\) 对 54 取模，第一项为零（因为它是 54 的倍数）。于是剩下 \(17b \equiv 1 \pmod{54}\)，从而 \(17^{-1} \equiv b \pmod{54}\)。换句话说，扩展欧几里得算法给出的系数直接给出了乘法逆元。这是扩展欧几里得算法有用的主要原因之一。

(b) 填空如下：

\[ 3 = 1 \times 54 - 3 \times 17 \] \[ 2 = 1 \times 17 - 5 \times 3 \] \[ 1 = 1 \times 3 - 1 \times 2 \] \[ \bigl[0 = 1 \times 2 - 2 \times 1\bigr] \]

可以将其改写为更易理解的形式：\(54 = 3 \times 17 + 3\)，等等；这直接对应正向过程中的 \(54 \bmod 17 = 3\) 运算，而所需的空白处来自 \(\lfloor 54/17 \rfloor\)。

(c) 从下到上回代并代入，我们有

\[ 1 = 1 \times 3 - 1 \times 2 \] \[ = 1 \times 3 - 1 \times (1 \times 17 - 5 \times 3) \] \[ = -1 \times 17 + 6 \times 3 \] \[ = -1 \times 17 + 6 \times (1 \times 54 - 3 \times 17) \] \[ = 6 \times 54 - 19 \times 17 \]

得到 17 模 54 的乘法逆元为 \(-19\)，或 \(35\)。注意 \(-19 \equiv 35 \pmod{54}\)。

(d) 对方程进行如下操作：

\[ 54 = 1 \times 54 + 0 \times 17 \tag{E1} \] \[ 17 = 0 \times 54 + 1 \times 17 \tag{E2} \] \[ 3 = 1 \times 54 - 3 \times 17 \tag{E3 = E1 - 3E2} \] \[ 2 = -5 \times 54 + 16 \times 17 \tag{E4 = E2 - 5E3} \] \[ 1 = 6 \times 54 - 19 \times 17 \tag{E5 = E3 - E4} \]

注意左边也对应欧几里得算法正向过程中的约化；我们做相同的计算（即确定减去多少倍），同时也在做反向回代。这就是为什么迭代方法比前面各部分的递归方法更直观、更快。

同样，我们得到 17 模 54 的乘法逆元为 \(-19\)，或 \(35\)。

(e) 使用递归算法，我们有

\[ \operatorname{gcd}(39,17) = \operatorname{gcd}(17,5) \quad 5 = 1 \times 39 - 2 \times 17 \] \[ \quad\quad\quad\quad\quad\quad\quad = \operatorname{gcd}(5,2) \quad 2 = 1 \times 17 - 3 \times 5 \] \[ \quad\quad\quad\quad\quad\quad\quad = \operatorname{gcd}(2,1) \quad 1 = 1 \times 5 - 2 \times 2 \] \[ \quad\quad\quad\quad\quad\quad\quad = \operatorname{gcd}(1,0) \quad \bigl[0 = 1 \times 2 - 2 \times 1\bigr] \]

从底部向上回代，我们有

\[ 1 = 1 \times 5 - 2 \times 2 \] \[ = 1 \times 5 - 2 \times (1 \times 17 - 3 \times 5) \] \[ = -2 \times 17 + 7 \times 5 \] \[ = -2 \times 17 + 7 \times (1 \times 39 - 2 \times 17) \] \[ = 7 \times 39 - 16 \times 17 \]

最终得到 \(1 = 7 \times 39 - 16 \times 17\)，因此逆元为 \(17^{-1} \equiv -16 \equiv 23 \pmod{39}\)。

使用迭代算法，我们有

\[ 39 = 1 \times 39 + 0 \times 17 \tag{E1} \] \[ 17 = 0 \times 39 + 1 \times 17 \tag{E2} \] \[ 5 = 1 \times 39 - 2 \times 17 \tag{E3 = E1 - 2E2} \] \[ 2 = -3 \times 39 + 7 \times 17 \tag{E4 = E2 - 3E3} \] \[ 1 = 7 \times 39 - 16 \times 17 \tag{E5 = E3 - 2E4} \]

(a) 观察可知

\[ a + 3b + 4c \equiv 1 + 0 + 0 \pmod{3}, \] \[ a + 3b + 4c \equiv 0 + 3 + 0 \pmod{7}, \] \[ a + 3b + 4c \equiv 0 + 0 + 4 \pmod{11}. \]

因此 \(x = a + 3b + 4c\) 确实满足 (1) 中的所有条件。

(b) 本小题要求找一个满足 \(0 \le a < 3 \cdot 7 \cdot 11\) 的数，它能被 \(7\) 和 \(11\) 整除，且被 \(3\) 除余 \(1\)。

从一个能被 \(7\) 和 \(11\) 整除的数出发，可取 \(7 \cdot 11 = 77\)。注意到我们可以再乘上一个模 \(3\) 的乘法逆元，使结果同余于 \(1 \pmod{3}\)。具体地，由于 \(77 \cdot 77^{-1} \equiv 1 \pmod{3}\)，我们只需计算

\[ 77^{-1} \equiv 2^{-1} \equiv 2 \pmod{3}. \]

于是得到 \(a = 77 \cdot 2 = 154\)。

验证：

\[ 154 = 3 \cdot 51 + 1 \equiv 1 \pmod{3}, \] \[ 154 = 22 \cdot 7 \equiv 0 \pmod{7}, \] \[ 154 = 14 \cdot 11 \equiv 0 \pmod{11}. \]

退一步看，我们实际计算了

\[ a = (7 \cdot 11) \cdot (7 \cdot 11)^{-1} \bmod 3. \]

其中第一项保证它是 \(7\) 和 \(11\) 的倍数，最后一项保证它模 \(3\) 余 \(1\)。

(c) 采用类似方法，先取 \(3\) 与 \(11\) 的公倍数 \(3 \cdot 11 = 33\)。

再乘上它在模 \(7\) 下的乘法逆元，使结果同余于 \(1 \pmod{7}\)。具体地，只需计算

\[ 33^{-1} \equiv 5^{-1} \equiv 3 \pmod{7}. \]

于是得到 \(b = 33 \cdot 3 = 99\)。

同样地，我们实际计算了

\[ b = (3 \cdot 11) \cdot (3 \cdot 11)^{-1} \bmod 7. \]

(d) 类似地，先取 \(3\) 与 \(7\) 的公倍数 \(3 \cdot 7 = 21\)。

再乘上它在模 \(11\) 下的乘法逆元，使结果同余于 \(1 \pmod{11}\)。具体地，只需计算

\[ 21^{-1} \equiv 10^{-1} \equiv 10 \pmod{11}. \]

于是得到 \(c = 21 \cdot 10 = 210\)。

同样地，我们实际计算了

\[ c = (3 \cdot 7) \cdot (3 \cdot 7)^{-1} \bmod 11. \]

(e) 由 (b)、(c)、(d) 得到 \(a = 154\)、\(b = 99\)、\(c = 210\)，分别满足 (2)、(3)、(4)。再结合 (a)，可得

\[ x = a + 3b + 4c = 154 + 3 \cdot 99 + 4 \cdot 210 = 154 + 297 + 840 = 1291 \]

满足 (1) 中的要求。

验证：

\[ 1291 = 430 \cdot 3 + 1 \equiv 1 \pmod{3}, \] \[ 1291 = 184 \cdot 7 + 3 \equiv 3 \pmod{7}, \] \[ 1291 = 117 \cdot 11 + 4 \equiv 4 \pmod{11}. \]

此外，该解在模 \(3 \cdot 7 \cdot 11 = 231\) 下唯一，因此

\[ x \equiv 1291 \equiv 136 \pmod{231}. \]

注记：这里本质上是在构造只满足其中一个同余式、而不影响其余同余式的量。一般地，设同余方程组为 \(x \equiv a_i \pmod{m_i}\)，\(i = 1, \dots, k\)。对每个方程我们希望得到 \(b_i \equiv 1 \pmod{m_i}\) 且 \(b_i \equiv 0 \pmod{m_j}\)（\(j \ne i\)），使得 \(a_i b_i\) 只满足模 \(m_i\) 的同余式，而对其他模均为 \(0\)。于是把所有 \(a_i b_i\) 相加就得到满足全部同余式的量。

每个 \(b_i\) 可按下式计算：

\[ b_i = \frac{M}{m_i} \cdot \left( \left( \frac{M}{m_i} \right)^{-1} \bmod m_i \right), \]

其中 \(M = m_1 m_2 \cdots m_k\)。第一项保证 \(b_i \equiv 0 \pmod{m_j}\)（\(j \ne i\)），第二项保证 \(b_i \equiv 1 \pmod{m_i}\)。方程组的解可写成

\[ x \equiv \sum_{i=1}^{k} a_i b_i \pmod{M}. \]

(a) 模 \(m\) 下只有 \(m\) 个可能的取值，因此在第 \(m\) 项之后必然会出现重复。鸽巢原理（Pigeonhole Principle）在这里适用——我们有 \(m\) 个「盒子」，代表 \(a^k\) 在模 \(m\) 下可能取到的不同值；然后把 \(a, a^2, a^3, \ldots\) 这无穷多个「物品」放进这 \(m\) 个盒子里。一旦物品超过 \(m\) 个（即序列到达 \(a^{m+1}\)），鸽巢原理就保证了至少有两个数在模 \(m\) 下取相同的值，也就是出现了碰撞。

(b) 为避免混淆，我们暂时用 \(a^*\) 表示 \(a\) 的乘法逆元。在等式两边同时乘以 \((a^*)^j\)，得到 \[a^i \equiv a^j \pmod m,\] \[a^{i-j} \underbrace{a \cdots a}_{j \text{ 次}} \equiv \underbrace{a \cdots a}_{j \text{ 次}} \pmod m,\] \[a^{i-j} \underbrace{a \cdots a}_{j \text{ 次}} \cdot \underbrace{a^* \cdots a^*}_{j \text{ 次}} \equiv \underbrace{a \cdots a}_{j \text{ 次}} \cdot \underbrace{a^* \cdots a^*}_{j \text{ 次}} \pmod m,\] \[a^{i-j} \equiv 1 \pmod m.\]

(c) 由 \(a^{i-j} \equiv 1 \pmod m\)，可以改写为 \(a^{i-j-1} \cdot a \equiv 1 \pmod m\)。因此 \(a^{i-j-1}\) 就是 \(a\) 在模 \(m\) 下的乘法逆元，即逆元可以写成 \(a^k\) 的形式，其中 \(k = i - j - 1\)。