最终，余数为零会出现在序列中：

.这个序列中最多不能包含超过 a 项 根据引理 1 可证.

最大公约数表示成一个线性组合#

如果 a 和 b 是任意整数，且不全为 0,那么 gcd(a,b) 是集合

中的最小正整数元素.

证明#

设 s 是 a 和 b 的最小线性组合.

设 q 是 a 除以 s 的商.那么

因此，a mod s 是 a 和 b 的线性组合.

由于 s 是所有线性组合中的最小整数，并且 a ≤ a mod s < s,

a mod s 不能是正数，因此 a mod s = 0.

这意味着 s 是 a 的因子，同样 s 也是 b 的因子.因此 s 是 a 和 b 的公约数，gcd(a,b) ≥ s.

由于 gcd(a,b) 同时整除 a 和 b，且 s 是 a 和 b 的线性组合，我们有 gcd(a,b) | s. 但是 gcd(a,b) | s 并且 s > 0 意味着 gcd(a,b) ≤ s.

推论#

对于整数 a 和 b，如果 d | a 并且 d | b，那么 d | gcd(a,b).

贝祖定理 Bézout’s Theorem#

定理#

如果 a 和 b 是正整数，那么存在整数 s 和 t 使得 gcd(a,b) = sa + tb. 这里的整数 s 和 t 被称为贝祖系数.

根据贝祖定理，整数 a 和 b 的最大公约数可以表示为 sa + tb，其中 s 和 t 是整数. 这是 a 和 b 的一个线性组合，其系数为整数.

• gcd(6,14) = (-2) * 6 + 1 * 14

例子 - 求贝祖系数#

将 gcd(252,198) = 18 表示为 252 和 198 的线性组合.

首先使用欧几里得算法证明 gcd(252,198) = 18

1. 252 = 1 * 198 + 54
2. 198 = 3 * 54 + 36
3. 54 = 1 * 36 + 18
4. 36 = 2 * 18

• 现在从上面第 3 个式子和第 1 个式子反向推导

  • 18 = 54 - 1 * 36
  • 36 = 198 - 3 * 54

• 将第 2 个方程带入第 1 个方程中

  • 18 = 54 - 1 * (198 - 3 * 54) = 4 * 54 - 1 * 198

• 接着将 54 = 252 - 1 * 198 代入上式：

  • 18 = 4 * 252 - 5 * 198

这个方法展示了“两步法”，先使用欧几里得算法找到最大公约数，然后通 过回代的方式将最大公约数表示为原始两个整数的线性组合.

扩展欧几里得算法#

还有一种称为扩展欧几里得算法的“单步法”，可以在进行欧几里得算法的同时贝祖系数，将最大公约数直接表示为线性组合.

算法过程#

简单地说，这个算法的过程就是在使用原数字对进行欧几里得算法结束后又代入了两个自己假设的数组，这个数组开头被设计为 0 和 1,接着将这两个系数数组像原先的数字一样进行欧几里得算法，最后算出来的就是一个贝祖系数对.

首先，进行一个完整的欧几里得算法：

之后定义两个数列 s 和 t.它们有以下的属性：

则因为

所以 s 和 t 就是 a 和 b 的贝祖系数.

例子#

将 gcd(100,35) 表示为 100 和 35 的线性组合.

由

可进行欧几里得算法：

• 100 = 35 * 2 + 30
• 35 = 30 * 1 + 5
• 30 = 5 * 6

接着构建 s 和 t 数列，有如下过程：

计算有

则

将同余式两边同时除去整数#

将有效同余式的两边同时除以一个整数，并不总是能得到一个有效的同余式。

但如果这个整数与模数互素，则可以得到一个有效的同余式:

定理#

设 m 为正整数，a, b 和 c 为整数. 如果

并且 gcd(c,m) = 1,那么

证明#

因为

那么

又由于 gcd(c,m) = 1, 所以 m | a - b.

因此：

定理得证.

算术基本定理的唯一性证明#

引理#

1. 如果 $a, b, c$ 为正整数，$\gcd(a,b)=1$ 且 $a \mid bc$，则 $a \mid c$.
2. 如果素数 $p \mid a_1a_2\cdots a_n$，则对于某个 $i$，有 $p \mid a_i$.

证明思路（反证法）#

假设存在两种不同的素因数分解。

其中 $p_i$ and $q_j$ 均为素数且非降序排列。 消去公共因子后，利用引理 2 可导出矛盾（左边素数整除右边，但右边是不含左边素数的乘积），从而得证唯一性。

线性同余方程 (Linear Congruences)#

定义#

形如 $ax \equiv b \pmod m$ 的同余式，其中 $m$ 为正整数，$a, b$ 是整数，$x$ 是变量，称为线性同余式。

逆元 (Inverse)#

如果整数 $\bar{a}$ 满足 $\bar{a}a \equiv 1 \pmod m$，称 $\bar{a}$ 为 $a$ 的模 $m$ 的逆元。

定理：如果 $a$ 和 $m$ 互素（$\gcd(a,m)=1$）且 $m>1$，那么 $a$ 在模 $m$ 下有逆元，且该逆元在模 $m$ 下是唯一的。

求解逆元#

利用扩展欧几里得算法求出贝祖系数 $s, t$ 使得 $sa + tm = 1$。 则 $sa + tm \equiv 1 \pmod m \Rightarrow sa \equiv 1 \pmod m$。 因此，$s$ 即为 $a$ 的逆元。

例子：求 101 在模 4620 下的逆元。

1. 使用欧几里得算法确认 $\gcd(101, 4620)=1$。
2. 回代求贝祖系数，得到 $1 = -35 \cdot 4620 + 1601 \cdot 101$。
3. 逆元为 1601。

用逆元求解线性同余式#

求解 $ax \equiv b \pmod m$。

1. 求出 $a$ 的逆元 $\bar{a}$。
2. 方程两边同时乘以 $\bar{a}$： $$\bar{a}ax \equiv \bar{a}b \pmod m \Rightarrow x \equiv \bar{a}b \pmod m$$

中国剩余定理 (Chinese Remainder Theorem)#

问题背景#

“有物不知其数，三分之余二，五分之余三，七分之余二，此物几何？” 即求解方程组：

定理#

设 $m_1, m_2, \dots, m_n$ 是两两互素的大于 1 的正整数，则对任意整数 $a_1, a_2, \dots, a_n$，同余方程组：

在模 $m = m_1m_2\cdots m_n$ 下有唯一解。

构造解法#

1. 令 $m = m_1m_2\cdots m_n$。
2. 令 $M_k = m / m_k$。
3. 求 $y_k$，使得 $M_k y_k \equiv 1 \pmod {m_k}$（即 $y_k$ 是 $M_k$ 模 $m_k$ 的逆元）。
4. 通解为： $$x = \sum_{k=1}^{n} a_k M_k y_k \pmod m$$

例子#

求解孙子算经问题：

• $m = 3 \times 5 \times 7 = 105$
• $M_1=35, M_2=21, M_3=15$
• 逆元：$y_1=2, y_2=1, y_3=1$
• $x = 2\cdot 35\cdot 2 + 3\cdot 21\cdot 1 + 2\cdot 15\cdot 1 = 140 + 63 + 30 = 233$
• $233 \equiv 23 \pmod {105}$。最小正整数解为 23。

反向替换法 (Back Substitution)#

另一种求解方法。将第一个同余式写成 $x = m_1t + a_1$，代入第二个同余式求解 $t$，依此类推。

数论重要定理#

威尔逊定理 (Wilson’s Theorem)#

$p$ 是素数当且仅当 $(p-1)! \equiv -1 \pmod p$。

欧拉定理与欧拉函数#

欧拉函数 $\phi(n)$：小于 $n$ 且与 $n$ 互素的正整数的个数。

• 若 $p$ 是素数，$\phi(p) = p-1$。
• 若 $n = pq$ 且 $p, q$ 互素，$\phi(n) = (p-1)(q-1)$。

欧拉定理：如果 $\gcd(a,n)=1$，则 $a^{\phi(n)} \equiv 1 \pmod n$。

推论：用于简化幂运算。 若 $\gcd(a,n)=1$，则 $a^x \equiv a^{x \bmod \phi(n)} \pmod n$。

费马小定理 (Fermat’s Little Theorem)#

如果 $p$ 是素数且 $p \nmid a$，则：

或者对于任意整数 $a$：

应用：计算大次幂的模。例如 $7^{222} \bmod 11$。

伪素数与原根#

伪素数 (Pseudoprimes)#

如果 $n$ 是合数，但满足 $b^{n-1} \equiv 1 \pmod n$，则称 $n$ 为以 $b$ 为基数的伪素数。

卡米切尔数 (Carmichael Numbers)：一个合数 $n$，如果对所有满足 $\gcd(b,n)=1$ 的正整数 $b$ 都满足 $b^{n-1} \equiv 1 \pmod n$，则称 $n$ 为卡米切尔数（如 561）。

原根 (Primitive Roots)#

模素数 $p$ 的原根是 $\mathbb{Z}_p$ 中的整数 $r$，使得 $\mathbb{Z}_p$ 中的每一个非零元素都是 $r$ 的某个幂次。 即 $r^1, r^2, \dots, r^{p-1} \bmod p$ 生成了 $1$ 到 $p-1$ 的所有整数。

离散对数 (Discrete Logarithms)#

设 $g$ 是模 $p$ 的原根。如果 $g^x \equiv a \pmod p$，则称 $x$ 为以 $g$ 为底 $a$ 模 $p$ 的离散对数。 记作 $\log_g a = x$。 注意：计算离散对数在计算上是非常困难的（Discrete Logarithm Problem），这是许多密码学算法的基础。

同余式的应用#

哈希函数 (Hashing Functions)#

常用函数：$h(k) = k \bmod m$。

• 冲突解决：线性探测 $h(k, i) = (h(k) + i) \bmod m$。

伪随机数 (Pseudorandom Numbers)#

线性同余法：

需要选择合适的模数 $m$、乘数 $a$、增量 $c$ 和种子 $x_0$。

校验位 (Check Digits)#

• UPC (通用产品代码)：12位，利用模 10 同余检测错误。

  $$3x_1 + x_2 + 3x_3 + \dots + x_{12} \equiv 0 \pmod{10}$$

• ISBN-10：利用模 11 同余。

  $$\sum_{i=1}^{10} ix_i \equiv 0 \pmod{11}$$

  (其中 X 代表 10)。

密码学 (Cryptography)#

古典密码#

1. 凯撒密码 (Caesar Cipher)：移位 $k=3$。 加密：$f(p) = (p+3) \bmod 26$。
2. 移位密码 (Shift Cipher)：任意 $k$。 加密：$f(p) = (p+k) \bmod 26$。 解密：$f^{-1}(p) = (p-k) \bmod 26$。
3. 仿射密码 (Affine Cipher)： 加密：$f(p) = (ap+b) \bmod 26$，其中 $\gcd(a, 26)=1$。
4. 分组密码 (Block Cipher)： 将字符分组，通过置换映射到另一组字符。例如换位密码。

密码系统 (Cryptosystems)#

五元组 $(P, C, K, E, D)$：明文、密文、密钥空间、加密函数集、解密函数集。

公钥密码学 (Public Key Cryptography)#

• 私钥密码：双方共享同一个密钥（对称）。
• 公钥密码：每个人有一对密钥（公钥加密，私钥解密）。解决了密钥分发问题。

RSA 密码系统#

最常用的公钥密码系统，基于大整数分解的困难性。

算法过程#

1. 密钥生成：

   • 选择两个大素数 $p, q$。
   • 计算 $n = pq$ 和 $\phi(n) = (p-1)(q-1)$。
   • 选择整数 $e$，使得 $\gcd(e, \phi(n)) = 1$。
   • 计算 $d$，使得 $de \equiv 1 \pmod{\phi(n)}$（即 $d$ 是 $e$ 的逆元）。
   • 公钥：$(n, e)$。私钥：$d$。

2. 加密： 将明文 $M$ 转换为整数（分组），计算密文 $C$：

   $$C = M^e \bmod n$$

3. 解密： 利用私钥 $d$ 恢复明文 $M$：

   $$M = C^d \bmod n$$

正确性#

基于 $M^{ed} \equiv M \pmod n$（欧拉定理推论）。

加密协议#

迪菲-赫尔曼密钥交换 (Diffie-Hellman Key Exchange)#

允许双方在不安全信道上协商共享密钥。基于离散对数难题。

1. 公开参数：大素数 $p$ 和原根 $g$。
2. Alice 选私钥 $a$，发送 $A = g^a \bmod p$。
3. Bob 选私钥 $b$，发送 $B = g^b \bmod p$。
4. 双方计算共享密钥：$K = B^a \bmod p = (g^b)^a = g^{ab} \bmod p = A^b \bmod p$。

数字签名 (Digital Signatures)#

用于验证消息来源和完整性。

• 发送方用私钥对消息（或其哈希）进行“解密”操作：$S = M^d \bmod n$。
• 接收方用发送方的公钥进行“加密”操作验证：$M' = S^e \bmod n$。若 $M'=M$，则签名有效。

同态加密 (Homomorphic Encryption)#

允许在密文上直接进行计算。RSA 具有乘法同态特性：

零知识证明 (Zero Knowledge Proof)#

证明者向验证者证明某个命题为真，而不泄露任何额外信息。

• 属性：完备性、可靠性、零知识。
• 例子：Schnorr 协议（证明知道离散对数而不泄露该数值）。

处理大整数#

余数系统 (Residue Number System, RNS)#

利用中国剩余定理，将大整数表示为一组较小模数的余数元组。

• $x = (x_1, x_2, \dots, x_k)$，其中 $x_i = x \bmod P_i$，$P_i$ 两两互质。
• 优点：加法和乘法可以并行地在每个分量上独立进行，大大提高了计算大整数运算的效率。
• $$x+y \leftrightarrow (x_1+y_1, \dots, x_k+y_k)$$
• $$x\cdot y \leftrightarrow (x_1\cdot y_1, \dots, x_k\cdot y_k)$$