最大公因数

最大公因数刻画两个整数公共的因数结构，辗转相除法（欧几里得算法）给出其高效算法。

定义

设 $a,b$ 是不全为零的整数。它们的最大公因数 $\gcd(a,b)$ 是满足以下条件的正整数 $d$：

• $d\mid a$ 且 $d\mid b$；
• 若 $c\mid a$ 且 $c\mid b$，则 $c\mid d$。

当 $\gcd(a,b) = 1$ 时，称 $a,b$ 互素。

欧几里得算法

由带余除法 $a = bq + r$（$0 \le r < b$）可得 $\gcd(a,b) = \gcd(b,r)$，反复应用即得辗转相除法：

$$a = bq_1 + r_1,\quad b = r_1q_2 + r_2,\quad \dots,\quad r_{n-2} = r_{n-1}q_n + r_n,\quad r_{n-1} = r_n q_{n+1}$$

最后一个非零余数 $r_n$ 即为 $\gcd(a,b)$。

性质

• $\gcd(a,b) = \gcd(b,a) = \gcd(|a|,|b|)$，且 $\gcd(a,0) = |a|$
• $\gcd(a,b) = \gcd(a - bq, b)$（欧几里得算法的依据）
• Bezout 定理：存在整数 $x,y$ 使得 $ax + by = \gcd(a,b)$
• 若 $a\mid bc$ 且 $\gcd(a,b) = 1$，则 $a\mid c$
• 最小公倍数：$\operatorname{lcm}(a,b) = \dfrac{|ab|}{\gcd(a,b)}$

示例

求 $\gcd(252, 105)$：

$$252 = 105\cdot 2 + 42,\quad 105 = 42\cdot 2 + 21,\quad 42 = 21\cdot 2$$

故 $\gcd(252,105) = 21$。其 Bezout 表示为

$$21 = 105 - 42\cdot 2 = 105 - (252 - 105\cdot 2)\cdot 2 = 105\cdot 5 - 252\cdot 2$$