【算法笔记】整除与最大公约数（GCD）专题整理

参考文章链接（已获得作者授权）

一、整除：数学中的"完美分割"

定义
若整数$a$能整除整数$b$（记作$a\mid b$），则存在整数$k$使得$b=a\cdot k$。
通俗理解：将$b$分割为若干份大小为$a$的块，无剩余。

关键性质

1. 符号等价性
   $a\mid b\iff -a\mid b\iff a\mid -b\iff |a|\mid |b|$
   例：$3\mid 12$等价于$-3\mid 12$或$3\mid -12$。

2. 传递性
   $a\mid b$且$b\mid c⟹a\mid c$。
   例：$3\mid 6$且$6\mid 12⟹3\mid 12$。

3. 线性组合性
   $a\mid b$且$a\mid c⟹a\mid (xb+yc)$（$x,y\in \mathbb{Z}$）。
   例：$5\mid 10$和$5\mid 15⟹5\mid (2\cdot 10+3\cdot 15=65)$。

4. 非零约束性
   若$b\ne 0$且$a\mid b$，则$|a|\le |b|$。
   例：$7\mid 14$且$|7|\le |14|$。

二、最大公约数（GCD）：寻找"最大共同因子"

定义
$\gcd (a,b)$是能同时整除$a$和$b$的最大正整数。
应用场景：均匀分配问题（如分糖、分饼干）。

示例

• $\gcd (24,36)=12$
  解释：24和36的公约数为1,2,3,4,6,12，最大的是12。

三、欧几里得算法（GCD计算）

核心思想：通过余数递归缩小问题规模。
步骤（以48和18为例）：

1. $48÷18=2$余12→转$\gcd (18,12)$
2. $18÷12=1$余6→转$\gcd (12,6)$
3. $12÷6=2$余0→终止，$\gcd =6$。

原理：$\gcd (a,b)=\gcd (b,a\mathrm{mod}b)$。

四、贝祖定理：线性方程的整数解

定理内容
对任意整数$a,b$，存在$x,y\in \mathbb{Z}$使得：
$$ax+by=\gcd (a,b)$$

示例

• $a=48$,$b=18$,$\gcd (48,18)=6$
  解：$x=-1$,$y=3$（因$48\cdot (-1)+18\cdot 3=6$）。

应用：密码学（如RSA中计算模逆元）。

五、扩展欧几里得算法（ExGCD）

目标：求解贝祖等式中的$x$和$y$。
步骤（回溯法，以48和18为例）：

1. 欧几里得过程：
   $$\begin{array}{rl}48& =18\times 2+12\\ 18& =12\times 1+6\\ 12& =6\times 2+0(\gcd =6)\end{array}$$
2. 回代表达式：
   $$\begin{array}{rl}6& =18-12\times 1\\ & =18-(48-18\times 2)\times 1\\ & =18\times 3-48\times 1\end{array}$$
   得$x=-1$,$y=3$。

递归逻辑：每一步用上一步的余数表示当前余数。

总结图表

注：所有性质与算法均基于整数运算，且$b\ne 0$时$|a|\le |b|$保证有限步终止。