数论04_欧几里得算法

吴老师

2026-08-23 13:29:17

发布于：广东

5阅读

0回复

0点赞

04 欧几里得算法

学习目标

理解并会使用公式 $\gcd(a,b)=\gcd(b,a\bmod b)$ 。

1. 例子

求 $\gcd(252,105)$ ：

$252=105\times2+42$

所以：

$\gcd(252,105)=\gcd(105,42)$

继续：

$105=42\times2+21$

所以：

$\gcd(105,42)=\gcd(42,21)=21$

2. 为什么欧几里得算法成立

欧几里得算法的核心公式是：

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

初看这个公式时，最容易产生三个疑问：

为什么把 $(a,b)$ 换成 $(b,a\bmod b)$ 后，公共因子不会发生变化？
只证明一边的公共因子也是另一边的公共因子，怎么能保证另一边不会“多出来”新的公共因子？
为什么不断辗转相除，最后一个非零余数一定就是最大的那个公共因子？

下面一步一步解决。

2.1 先把余数写出来

设 $a>b>0$ 。

根据带余除法，一定可以写成：

$a=qb+r$

其中：

$q$ 是商；
$r$ 是余数；
$r=a\bmod b$ ；
$0\le r<b$ 。

把式子移项：

$r=a-qb$

所以我们真正需要证明的是：

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

2.2 先证明： $(a,b)$ 的公共因子， $(b,r)$ 一定也有

假设 $d$ 是 $a,b$ 的一个公共因子。

也就是说：

$d\mid a$

并且：

$d\mid b$

因为 $d\mid b$ ，所以 $d$ 也一定能整除 $qb$ ：

$d\mid qb$

又因为 $d\mid a$ ，所以 $d$ 一定能够整除它们的差：

$d\mid(a-qb)$

而：

$a-qb=r$

因此：

$d\mid r$

于是 $d$ 同时整除 $b$ 和 $r$ 。

所以：

任意一个 $(a,b)$ 的公共因子，也一定是 $(b,r)$ 的公共因子。

这里要特别注意：

$d$ 不是某一个特殊的公共因子，而是任意一个公共因子。

因此我们证明的是：

$(a,b)\text{ 的所有公共因子}\subseteq(b,r)\text{ 的所有公共因子}$

2.3 但是，只证明这个包含关系还不够

这是整个证明里非常容易忽略的一点。

假设有两个集合：

$A={1,2}$

$B={1,2,4}$

显然：

$A\subseteq B$

但是 $B$ 比 $A$ 多了一个 4。

所以如果我们只证明：

$(a,b)\text{ 的公共因子}\subseteq(b,r)\text{ 的公共因子}$

那么只能说明：

$(a,b)$ 有的公共因子， $(b,r)$ 全都有。

但是我们还不知道：

$(b,r)$ 会不会额外多出一些公共因子？

甚至可能担心它会多出一个更大的公共因子。

因此，只证明一个方向，还不能推出两边的最大公约数相同。

我们必须再证明反方向。

2.4 再证明： $(b,r)$ 的公共因子， $(a,b)$ 一定也有

现在反过来。

假设 $d$ 是 $b,r$ 的一个公共因子。

也就是说：

$d\mid b$

并且：

$d\mid r$

因为：

$d\mid b$

所以：

$d\mid qb$

又因为：

$d\mid r$

所以 $d$ 一定能够整除：

$qb+r$

而前面已经知道：

$a=qb+r$

因此：

$d\mid a$

所以 $d$ 同时整除 $a$ 和 $b$ 。

也就是说：

任意一个 $(b,r)$ 的公共因子，也一定是 $(a,b)$ 的公共因子。

于是：

$(b,r)\text{ 的所有公共因子}\subseteq(a,b)\text{ 的所有公共因子}$

2.5 两个方向合起来，才能说明公共因子完全一样

现在已经有：

$(a,b)\text{ 的所有公共因子}\subseteq(b,r)\text{ 的所有公共因子}$

同时又有：

$(b,r)\text{ 的所有公共因子}\subseteq(a,b)\text{ 的所有公共因子}$

两个集合互相包含，所以它们只能完全相等：

$\boxed{(a,b)\text{ 的公共因子集合}=(b,r)\text{ 的公共因子集合}}$

这句话意味着：

$(b,r)$ 不会多出新的公共因子；
$(a,b)$ 也不会少掉任何公共因子；
两边拥有的是完全同一批公共因子。

2.6 为什么公共因子完全一样，就能说明最大公约数一样？

举个具体例子。

取：

$a=48$

$b=18$

有：

$48=18\times2+12$

所以：

$r=12$

现在看 $(48,18)$ 的所有公共因子：

$1,2,3,6$

再看 $(18,12)$ 的所有公共因子：

$1,2,3,6$

两边完全一样。

既然公共因子集合都是：

${1,2,3,6}$

那么其中最大的元素当然也一样，都是 6。

所以：

$\gcd(48,18)=\gcd(18,12)=6$

一般地，因为 $(a,b)$ 与 $(b,r)$ 的公共因子集合完全相同，所以它们最大的公共因子也必然相同：

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

又因为：

$r=a\bmod b$

所以得到欧几里得算法的核心公式：

$\boxed{\gcd(a,b)=\gcd(b,a\bmod b)}$

2.7 为什么可以一直辗转相除？

既然每一次都有：

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

那么我们就可以不断把问题换成更小的一组数。

例如：

$\gcd(48,18)$

第一次：

$48=18\times2+12$

所以：

$\gcd(48,18)=\gcd(18,12)$

第二次：

$18=12\times1+6$

所以：

$\gcd(18,12)=\gcd(12,6)$

第三次：

$12=6\times2+0$

所以：

$\gcd(12,6)=\gcd(6,0)$

连起来就是：

$\gcd(48,18)=\gcd(18,12)=\gcd(12,6)=\gcd(6,0)$

这里最重要的不是：

数字越来越小。

而是：

数字虽然一直在变小，但最大公约数从头到尾都没有发生变化。

2.8 为什么辗转相除一定会停止？

每次计算余数：

$r=a\bmod b$

余数一定满足：

$0\le r<b$

如果 $r\ne0$ ，那么：

$r<b$

也就是说，新的第二个数一定严格小于旧的第二个数。

于是会出现类似：

$18>12>6>0$

这样的过程。

这些数：

都是非负整数；
每一步都严格变小。

非负整数不可能无限地严格变小。

所以经过有限次计算以后，一定会出现余数为 0。

因此欧几里得算法一定会停止。

2.9 为什么最后一个非零余数就是最大公约数？

最后一定会走到：

$\gcd(d,0)$

现在看 $d$ 和 0 的公共因子。

假设 $k\mid d$ 。

那么 $k$ 也一定整除 0，因为：

$0=k\times0$

所以：

$d$ 的所有因子，也全部都是 $d$ 和 0 的公共因子。

而 $d$ 的最大因子显然就是 $d$ 自己。

因此：

$\gcd(d,0)=d$

再回头看前面的过程：

$\gcd(a,b)=\cdots=\gcd(d,0)=d$

因为每一步的最大公约数都没有改变，所以：

最后一个非零余数 $d$ ，就是最开始 $a,b$ 的最大公约数。

2.10 最容易产生的误解

不要把辗转相除理解成：

“不断除下去，最后剩下的数碰巧是最大的公共因子。”

真正的逻辑是：

每一次从 $(a,b)$ 变成 $(b,a\bmod b)$ 时，都证明了新旧两组数的所有公共因子完全相同。

因此：

最大公约数从头到尾根本没有改变。

算法只是不断把数字变小，使这个一直没有改变的最大公约数最终变得“直接可见”。

当问题变成：

$(d,0)$

时，我们立刻就知道：

$\gcd(d,0)=d$

于是 $d$ 就是答案。

2.11 整个证明的逻辑链

第一步，带余除法：

$a=qb+r$

其中：

$r=a\bmod b$

第二步，证明：

$(a,b)\text{ 的公共因子}\subseteq(b,r)\text{ 的公共因子}$

第三步，再证明反方向：

$(b,r)\text{ 的公共因子}\subseteq(a,b)\text{ 的公共因子}$

第四步，得到：

$(a,b)\text{ 的公共因子集合}=(b,r)\text{ 的公共因子集合}$

第五步，因此：

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

也就是：

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

第六步，不断重复：

$(a,b)\rightarrow(b,a\bmod b)\rightarrow\cdots\rightarrow(d,0)$

整个过程中最大公约数始终不变。

最后：

$\gcd(d,0)=d$

所以：

$\boxed{\gcd(a,b)=d}$

也就是说：

辗转相除法中最后一个非零余数，就是最开始两个数的最大公约数。

3. C++ 模板

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

循环版：

int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

4. 复杂度

可以记为 $O(\log\min(a,b))$ 。

5. 和后续知识的连接

以后经常会写：

if (gcd(a, mod) == 1) {
    // a 在 mod 下存在逆元
}

6. 小练习

求：

$\gcd(48,18)$
$\gcd(100,35)$
$\gcd(17,13)$

答案

有帮助，赞一个

去预览

0/2000

这里空空如也

04 欧几里得算法

学习目标

1. 例子

2. 为什么欧几里得算法成立

2.1 先把余数写出来

2.2 先证明：(a,b)(a,b)(a,b) 的公共因子，(b,r)(b,r)(b,r) 一定也有

2.3 但是，只证明这个包含关系还不够

2.4 再证明：(b,r)(b,r)(b,r) 的公共因子，(a,b)(a,b)(a,b) 一定也有

2.5 两个方向合起来，才能说明公共因子完全一样

2.6 为什么公共因子完全一样，就能说明最大公约数一样？

2.7 为什么可以一直辗转相除？

2.8 为什么辗转相除一定会停止？

2.9 为什么最后一个非零余数就是最大公约数？

2.10 最容易产生的误解

2.11 整个证明的逻辑链

3. C++ 模板

4. 复杂度

5. 和后续知识的连接

6. 小练习

答案

热门讨论

2.2 先证明： $(a,b)$ 的公共因子， $(b,r)$ 一定也有

2.4 再证明： $(b,r)$ 的公共因子， $(a,b)$ 一定也有