GCD基础

---

最大公约数 (GCD) 基础

1. 交换律

$$ \gcd(a, b) = \gcd(b, a) $$

证明
根据 $\gcd(a, b)$ 的定义，它是集合 ${d \in \mathbb{Z}^+ : d \mid a \text{ 且 } d \mid b}$ 中的最大元素。由于集合的隶属条件与参数顺序无关，故最大公约数相等。

2. 结合律

$$ \gcd(a, \gcd(b, c)) = \gcd(\gcd(a, b), c) $$

证明
设 $d_1 = \gcd(a, \gcd(b, c))$，$d_2 = \gcd(\gcd(a, b), c)$：

1. 由定义可知 $d_1 \mid a$ 且 $d_1 \mid \gcd(b, c)$，进一步推导得 $d_1 \mid a, d_1 \mid b, d_1 \mid c$。因此 $d_1$ 是三个数的公约数。
2. 同理，$d_2$ 也是这三个数的公约数。
   根据公约数总是整除最大公约数的性质，结合最大性可证 $d_1 = d_2 = \gcd(a, b, c)$。

3. 贝祖定理 (Bézout’s Identity)

$$ \gcd(a, b) = \min{ ax + by > 0 \mid x, y \in \mathbb{Z} } $$

证明
设集合 $S = { ax + by > 0 \mid x, y \in \mathbb{Z} }$。由良序原理，设 $S$ 中的最小正元素为 $d = ax_0 + by_0$：

1. 整除性：设 $a = qd + r$ ($0 \leq r < d$)。则 $r = a - qd = a - q(ax_0 + by_0) = a(1 - qx_0) + b(-qy_0)$。若 $r > 0$，则 $r \in S$，这与 $d$ 是 $S$ 中的最小元矛盾，故 $r = 0$，即 $d \mid a$。同理可证 $d \mid b$。
2. 最大性：若存在公约数 $c$ 满足 $c \mid a$ 且 $c \mid b$，则必有 $c \mid (ax_0 + by_0)$，即 $c \mid d$，故 $c \leq d$。

4. GCD-LCM 恒等式

$$ \gcd(a, b) \cdot \text{lcm}(a, b) = |ab| $$

证明
设 $d = \gcd(a, b)$，令 $a = da’$，$b = db’$，其中 $\gcd(a’, b’) = 1$。
根据最小公倍数的定义，$\text{lcm}(a, b) = d \cdot a’ \cdot b’$。
则：$\gcd(a, b) \cdot \text{lcm}(a, b) = d \cdot (d \cdot a’ \cdot b’) = (da’) \cdot (db’) = |ab|$。

5. 欧几里得算法 (原理)

$$ \gcd(a, b) = \gcd(b, a \bmod b) \quad (b \neq 0) $$

证明
设 $a = qb + r$，其中 $r = a \bmod b$。

1. 若 $d \mid a$ 且 $d \mid b$，则 $d \mid (a - qb)$，即 $d \mid r$。
2. 若 $d’ \mid b$ 且 $d’ \mid r$，则 $d’ \mid (qb + r)$，即 $d’ \mid a$。
   由于 $(a, b)$ 与 $(b, r)$ 的公约数集合完全相同，其最大元素必然相等。

• 递归

long gcd(long a, long b){
    if(b == 0) return a;
    return gcd(b, a%b);
}

• 迭代

long gcd(long a, long b) {
    while (b != 0) {
        long temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

6. 倍法性质 (线性缩放)

$$ \gcd(ka, kb) = k \cdot \gcd(a, b) \quad (k > 0) $$

证明
利用贝祖定理：
$\gcd(ka, kb) = \min{ kax + kby > 0 } = k \cdot \min{ ax + by > 0 } = k \cdot \gcd(a, b)$。

7. 同余不变性

若 $a \equiv b \pmod{m}$，则 $\gcd(a, m) = \gcd(b, m)$。

证明
由同余定义知 $a = km + b$。根据欧几里得算法：
$\gcd(a, m) = \gcd(km + b, m) = \gcd(m, (km + b) \bmod m) = \gcd(m, b \bmod m) = \gcd(b, m)$。

8. 质数相关性质

对于质数 $p$：
$$
\gcd(p, a) =
\begin{cases}
p, & \text{若 } p \mid a \
1, & \text{若 } p \nmid a
\end{cases}
$$

证明
由于质数 $p$ 的正因数仅有 ${1, p}$：

• 若 $p \mid a$，则 $p$ 是公因数中最大的；
• 若 $p \nmid a$，则唯一的正公因数为 $1$。

9. 扩展欧几里得算法 (ExGCD) 递推

扩展欧几里得算法用于求满足 $ax + by = \gcd(a, b)$ 的一组整数解 $(x, y)$。

推导

1. 边界情况：当 $b=0$ 时，$\gcd(a, 0)=a$。此时 $x=1, y=0$ 满足 $a(1) + 0(0) = a$。
2. 递推步骤：假设已知下一层递归 $bx’ + (a \bmod b)y’ = \gcd(a, b)$ 的解 $(x’, y’)$。
   将 $a \bmod b = a - \lfloor a/b \rfloor b$ 代入上式：
   $bx’ + (a - \lfloor a/b \rfloor b)y’ = \gcd(a, b)$
   整理得：$ay’ + b(x’ - \lfloor a/b \rfloor y’) = \gcd(a, b)$
   对应 $ax + by = \gcd(a, b)$，可得：
   $x = y’, \quad y = x’ - \lfloor a/b \rfloor y’$。

10. 分配律 (GCD 与 LCM 复合)

$$ \gcd(a, \text{lcm}(b, c)) = \text{lcm}(\gcd(a, b), \gcd(a, c)) $$
$$ \text{lcm}(a, \gcd(b, c)) = \gcd(\text{lcm}(a, b), \text{lcm}(a, c)) $$

证明思路
利用质因数分解指数的视角，$\gcd$ 对应 $\min$ 函数，$\text{lcm}$ 对应 $\max$ 函数。证明等价于验证算效恒等式：
$\min(\alpha, \max(\beta, \gamma)) = \max(\min(\alpha, \beta), \min(\alpha, \gamma))$。

11. 多元素平权性质

最大公约数运算满足广义的交换律与结合律，计算一组数的 GCD 与处理顺序无关：
$$ \gcd(a, b, c) = \gcd(\gcd(a, b), c) = \gcd(a, \gcd(b, c)) $$