(涵盖第 6、7 个讲义)

LN6 GCD 最大公因数

基础知识

• 最大公因数：若整数 c 同时整除 a,b，即 c | a 且 c | b，则 c 是 a,b 的公因数；最大公因数叫 gcd，记作 gcd(a, b)。若 a 与 b 没有公因数，则 gcd(a, b)=1（互素）。
• 商余定理 (Quotient-Remainder Theorem)：对任意整数 a 与正整数 b，存在唯一整数 q,r 使 a = q·b + r 且 0 ≤ r < b；通常写 q = a div b，r = a mod b。

Euclid’s Algorithm 欧几里得算法

• 若 a ≥ b > 0： 若 a = kb 直接得到 gcd(a, b)=b；否则写作 a = qb + r (r > 0)，关键思想：
  gcd(a, b) = gcd(b, r) = … = gcd(g, 0) 递归到余数为 0 为止，返回当前非零数 g 即为 a 与 b 的最大公因数。
• 使用例：$$gcd(728, 476) = gcd(476, 252) = gcd(252, 224) = gcd(224, 28), gcd(28, 0) = 28$$

Bézout’s Identity

• 定义 integer linear combination：形如 “sa+tb”（s, t ∈ Z）。 定理（Bézout’s Identity）： gcd(a, b)= min{ |sa + tb| > 0} (最小正整线性组合，s 或 t 可以为负) 记作 gcd(a, b) = spc(a, b)，其证明分两步：$$(i) \gcd(a,b)\mid \mathrm{spc}(a,b)\Rightarrow \gcd\le \mathrm{spc}；\ (ii) \mathrm{spc}(a,b) 也整除 a,b\Rightarrow \mathrm{spc}\le \gcd。$$于是得到两者相等。

• Bézout 等式的推论：若 gcd(a, b)=1 且 gcd(a, c)=1，则 gcd(a, bc)=1 (把两条 Bézout 等式相乘并整理得到)。

• 其他推论：若 gcd(b, c)=1，且 c|ba，那么 c|a：

  因为 gcd(b, c)=1，∃ (sb + tc) = 1，sba + tca = a。因为 c|ba，所以 c|sba；并且显然 c|tca，故 c|a。

Extended Euclid

• 计算完 gcd 之后，利用 Bézout 等式反推 spc。
• 使用例：仍以 728 和 476 为例，反推最大公因数 28 得到 spc(728, 476)：$$28=252-224=252-(476-252)=2\cdot252-476=2(728-476)-476=2\cdot728-3\cdot476$$

素数整除性质(PD) 与算术基本定理(FTA)

• 若 p 为素数且 p | ab，则 p | a 或 p | b。利用 Bézout：$$若\ p\nmid a\ 则\ \gcd(p,a)=1\Rightarrow\exists s,t: sp+ta=1，乘以\ b\ 得\ sbp+tab=b，$$$$因为\ sbp\ 含有\ p,\ p\ |\ sbp；又因为\ p\ |\ (ab\ |\ tab),于是 p\mid b$$
• FTA (分解的唯一性)：任意 n>1 可分解为独一无二的升序素因子乘积。

“Die Hard”取水问题 (不变量法 & 线性组合)

两个壶容量 a,b 情形下，每一步操作后两壶水量都保持为 a,b 的整数线性组合；因此所有可达水量一定是 gcd(a,b) 的整倍数。于是“3 与 9”不可能量出 4（因为gcd = 3）；“21 与 26”可以量出 4（因为 gcd = 1）。当且仅当目标容量 k 是 gcd(a,b) 的倍数才可以量。

LN7 Modular Arithmetic 模运算

同余

• 余数 (mod) 运算等同于求余 (%)，比如 7 mod 2 = 1

• 余数化简恒等式：an mod bn ≡ n(a mod b) (a, b, n ∈ Z)

• 同余的定义：a ≡ b (mod n) ⇔ n | (a-b)。它等价于 “被 n 除后的余数相同”

• “mod”（余数）与“≡”（同余）关系：a ≡ b (mod n) ⇔ a mod n = b mod n

模加法与模乘法

• 若 a ≡ c、b ≡ d (mod n)，则：a+b ≡ c+d (mod n) 与 ab ≡ cd (mod n) 一定成立。

  证明思路：均代回 a=c+nx, b=d+ny 再整理，说明 n | (a+b-c-d) 或 n | (ab-cd)

• 模指数（Modular exponentiation）：由乘法闭包可得 a^m ≡ c^m (mod n)；进而任何整系数多项式 f(a) ≡ f(c) (mod n)。

• 模运算的计算技巧：不断“取模简化”降复杂度，把大数幂分解成模小数连乘。

模运算应用：整除性判别

• 是否能被 9 或 3 整除的判定：因为 10^m ≡ 1 (mod 9) 和 10^m ≡ 1 (mod3) (m ∈ Z⁺)，一个数字与它十进制展开后的各位数字和同余 (mod 3 or 9)。 比如 252 = 2x10²+5x10+2x1 ≡ 2+5+2 ≡ 9，9 | 9

• 是否能被 11 整除的判定：因 10^m ≡ (-1)^m (mod 11)，十进展开变为“奇偶位数字交错和”。 比如 121 ≡ -1+2+-1 = 0，11 | 0

模运算应用：华容道问题

先前的思考题也可以用模运算的思路解答：

假设原状态为基准，空格位置为 (i, j)，处于相反位置的对数为 p，那么状态奇偶性：Parity = (p + i) mod 2

比如图中：Parity(LHS) = (0+4) mod 2 = 0；Parity(RHS) = (1+4) mod 2 = 1 所以是不可能的。

乘法逆元 (Multiplicative Inverse)

• 定义：在模 n 下，a 的逆元 a’ 满足 aa’ ≡ 1 (mod n)。讨论时一切元与逆元都小于模 n。 比如 3 的 “模 10 逆元” 是 7，21 ≡ 1 (mod 10)

• 逆元存在的充要条件：gcd(a, n) = 1 ⇔ 逆元存在 ()。证明用 Bézout：gcd(a, n) = sa+tn = 1，则 s 就是 a 的逆元 (mod n)。 比如 2‘ (mod 10) 是不存在的，因为 gcd(2, 10) = 2。

• Z_n 表示所有小于 n 的数 a mod n 时的逆组成的域。比如 Z₆ 中不存在 2、3、4 的逆元。而素数模的所有情况都有逆元。

• 消元（Cancellation）：一般模运算不能直接约去公因数。比如 3x2 ≡ 5x2 (mod 4) 但 3 与 5 并不同余 4。 当且仅当 gcd(公因数, 除数)=1，因为此情况下公因数存在逆元(根据充要条件)，所以可左右同乘逆元完成“消去”。比如 6x3 ≡ 11x3 (mod 5) → 6x3x3’ ≡ 11x3x3’ (mod 5) → 6 ≡ 11 (mod 5)

费马小定理 & 威尔逊定理

• Fermat’s Little Theorem：若 p 为素数且 gcd(k,p)=1，则： k^p-1 ≡ 1 (mod p) 证明思路：集合 {k,2k,…,(p-1)k} (mod p) 的结果是 {1,…,p-1} 的某种顺序的排列。如果两边分别连乘并“在模 p”可消去时 (也就是 p 为素数时) 得到以上结论。

• 继续推理得到：k^x ≡ k^{x mod p-1} (mod p)，比如 2⁸¹ ≡ 2 (mod 11)

  证明思路：因为乘法中不管乘几个 k^p-1 对余数都都没有影响，故可以全部消掉。

• Wilson’s Theorem：p 为素数 ⇔(p-1)! ≡ -1 (mod p)。 必要性： 如果不是素数，Z_p 中一定有可整除的无逆元项，导致 (p-1)! ≡ 0 (mod p) 充分性：p 为素数时除了 1 和 p-1 外其它数可配对成两两互逆的对，其乘积都为 1，剩下 1 x (p-1) ≡ -1。

一元线性同余方程 ax ≡ b (mod n)

• 可解充要条件：gcd(a,n) | b。若 gcd(a,n)=1，乘以 a^-1 得解；若 gcd=c>1，当且仅当 c | b 时可把方程约化为模 n/c 的可解方程。解集形如“一条等差同余类”。

• CSC3001