求两个正整数的最大公约数可以用欧几里得的GCD算法。首先介绍GCD算法的原理，再用一个公式表达出最大公约数和最小公倍数的密切关系。

例题：求986和748的最大公约数，即gcd (986,748)=？

先介绍一个笨办法。它们都能够被2整除，但是不能被3整除。我们不断尝试各种可能的因数，并跟踪结果。当我们达到748时，停止测试除数，因为没有大于748的整数可以成为748的因数。试过所有可能性之后，我们发现986和748仅有的公约数是1、2、17和34。所以986和748的最大公约数( greatest common divisor ）是34。对于任何两个正整数 a 和 b ，标记 gcd ( a , b ）代表它们的最大公约数。

一些简单的例子可以让你检验自己的理解：

gcd (10,15)=5

gcd (12,16)=4

gcd (13,11)=1

gcd (10,20)=10

gcd (17,17)=17

从上述方法产生了一个简单正确的算法来计算两个正整数的最大公约数。它的弱点是效率低下。要找到两个三位数字的 gcd 需要尝试数百个可能的因数。有没有更好的办法？

让我们更仔细地观察986和748。既然我们在寻找共同的因数，那么将它们分解为质数似乎是很自然的，下面是它们的质因数分解：

986=2×17×29和748=2×2×11×17。

在计算 gcd ( a , b ）时，将 a 和 b 进行因数分解的效率要高于在整除实验中一直试到 a 与 b 的最小值的效率。要找到一个整数 a 的质因数，最多只需要 √a 次尝试。所以这比第一种方法有了明显的改进，但对于大的整数来说仍然不可行。因为大整数的质因数分解很困难。

从这些分解中，我们可以通过"抓取"两个数字共有的所有质数来计算 gcd 。由于二者都有一个因数2和一个因数17，他们的 gcd 是2x17=34。

我们如何有效地对数进行分解？不幸的（我们在第一章中提到）是我们不知道。我们需要一个新的想法。

这个新想法来自欧几里得。假设 d 是986和748的一个公约数。这意味着

986= xd 且748= yd

其中 x 和 y 是整数。这意味着 d 是986-748的约数。下面用代数来表示这个说法：

986-748= xd - yd =( x - y ) d

由于 x 和 y 是整数，所以 x - y 也是整数。因此，986和748之差也是 d 的倍数。注意，986-748=238。

同样，任何748和238的公约数都是986的公约数。以下是原因。如果 e 是748和238的公约数，那么我们得出

748= ue 且238= ve

u 和 v 是整数。因此

986=748+238= ue + ve =( u + v ) e

从中我们推导出986是 e 的倍数。

结论：986和748的公约数与748和238的公约数完全相同。为了准确地表示，以下是所有三个数字的约数，加下划线的是它们共享的约数：

986的约数:1,2,17,29,34,58,493,986

748的约数：

1,2,4,11,17,22,34,44,68,187,

374,748

238的约数：

1,2,7,14,17,34,119,238

因为它们的公约数是一样的，我们得出

gcd (986,748)= gcd (748,238) ( A )

因此计算 gcd (986,748）的问题转换为计算 gcd (748,238)。这是进步，因为我们将计算较小的数字。让我们再次尝试相同的技巧。

如果 d 是748和238的一个公约数，那么它也是它们之差的约数。但是我们可以走得更远。我们可以从748中多次减去238，并做出相同的论断。具体而言，如果 d 能整除748和238，那么我们说 d 也是748-3×238的一个约数。下面是支持这个结论的代数表达，写作

748= xd 且238= yd

其中 x 和 y 是整数。那么

748-3×238= xd -3yd=( x -3y) d

因此 d 是748-3×238=34的公约数。

相反，如果 e 是34和238的约数，那么 e 也是748的约数。下面是代数表达，因为 e 是238和34的公约数，所以

238= ue 且34= ve

u 和 v 是整数。因此

748=3×238+34=3×( ue )+ ve =(3u+ v ) e

所以 e 是748的约数。因此，三个整数748,238和34具有完全相同的约数，我们可以得出结论：

gcd (748,238)= gcd (238,34)( B )

联立等式（ A ）和（ B ）得出

gcd(986,748)=gcd(748,238)

=gcd(238,34)

我们差不多完成了。注意到238可被34整除(因为238=34×7)，所以

gcd (238,34)=34。最后的结果是

gcd (986,748)= gcd (748,238)= gcd (238,34)=34

让我们回顾一下在这个计算中如何得出中间数。我们从986中减去748得到238。我们从748中减去3次238，得到34。为什么我们在第一种情况下减去一次而在第二种情况下减去三次呢？我们希望尽可能地使数字变小，因为计算小数字的 gcd 比大数字更容易。所以我们希望尽可能多地从较大的数中减去较小的数。注意，986里只有一个748（在除法的意义上），余下238。然而，748里有三个238，余数为34。我们只能用948次减去一次748，但是我们可以用748减去三次238。

例如，如果 a =100, b =40，那么商 q =2，余数c =20。那么得到100-2x40=20。

我们准备将这个例子的思想汇集成一个计算两个正整数的最大公约数的算法。给出两个正整数 a 和 b ，我们要计算它们的最大公约数 gcd ( a , b )。我们将尽可能减去 b 的倍数。为了弄清楚减去多少次，我们用 a 除以 b 得到商 q 和余数 c 。代数上，我们有

a - qb = c

如果 b 碰巧是 a 的除数，那么这个除法是整除，余数 c 是零。否则， c 是正数，但小于 b （如果 c 大于 b ，我们可以再减去一个 b )。

现在假设 d 是 a 和 b 的一个公约数。意即

a = xd且b = yd

其中 x 和 y 是整数。因此

c = a - qb = xd - q ( yd )=( x - qy ) d

所以 c 也是 d 的倍数（因为 x - qy 是一个整数）。

另一方面，如果 e 是 b 和 c 的公约数，那么得出

b = ue且c = ve

u 和 v 是整数。因此

a = c + qb = ve + q ( ue )=( v + qu ) e

所以 e 是 a 的一个除数。

我们已经证明， a 和 b 的公约数与 b 和 c 的公约数完全相同。因此，

gcd ( a,b )= gcd ( b,c ) (C)

让我们看看等式（ C ）如何使我们有效地计算两个大整数的最大公约数： a =10693和 b =2220。

我们用 a 除以 b ，发现10693有4个2220，余数 c =1813。

10693=4×2220+1813

因此

gcd (10693,2220)= gcd (2220,1813)

2220=1×1813+407。

现在我们"重新开始"并设 a '=2220且 b '=1813。将 a '除以 b '可以看出2220只有一个1813，余数 c '=407。因此，依据等式（ C )

gcd (10693,2220)= gcd (2220,1813)

= gcd (1813,407)

1813=4×407+185.

重新开始，这次设 a "=1813且 b "=407，我们发现1813里有四个407,余数为185。再次，依据等式（ C ):

gcd (10693,2220)= gcd (2220,1813)

= gcd (1813,407)

= gcd (407,185)

设 a '"=407且 b "'=185。相除，我们看到，407里有两个185，余数

c '"=37.

407=2×185+37.

gcd (10693,2220)= gcd (2220,1813)

= gcd (1813,407)

= gcd (407,185)

= gcd (185,37)

我们离结果越来越近！设 a ""=185且 b ""=37，相除——185里正好有五个37。因此 gcd (185,37)=37。我们完成了计算：

185=5×37+0.

gcd (10693,2220)= gcd (2220,1813)

= gcd (1813,407)

= gcd (407,185)

= gcd (185,37)=37

我们找到了10693和2220的最大公约数，只用了五次除法！欧几里得的最大公约数算法可以总结如下：

在第6章中我们介绍了整数互素的概念。它可以这样描述：假设 gcd ( a , b )=1那么 a 和 b 互素。由于欧几里得算法可以高效地计算两个数字的 gcd ，它提供了一个有效的方法来查看两个数字是否互素。

欧几里得的 GCD 算法

输入：两个正整数 a 和 b

输出： gcd ( a , b )

a除以 b 得到商 q 和余数 c 。

2．如果 c =0，则返回 b; c 是 a 和 b 的最大公约数。

3．否则，计算 gcd ( b , c ）并返回该值。

检验你对欧几里得算法的理解，找出1309和1105的最大公约数。你可以使用计算器。答案稍后公布 。

最小公倍数

最大公约数概念与最小公倍数（ least common multiple ）概念密切相关。假设有两个正整数，比如10和15，它们的最小公倍数是同时满足是二者倍数的最小正整数；在这种情况下，答案是30。 a 和 b 的最小公倍数标记为 lcm ( a , b )。最小公倍数概念可以用于分数的相加。例如。1/10和1/15相加，首先要使用一个公分母来重写这些分数。这个公分母可能是任何10和15倍数的数字，其中最简单的是它们的最小公倍数。因为 lcm (10,15)=30，我们可以用分母30重新表示1/10和1/15，然后做加法：

找到小数字的最小公倍数不是太具有挑战性，但是我们如何计算大数字的最小公倍数？例如，364和286的最小公倍数是几？

一种方法是写出这两个数字的倍数，并找到一个匹配：

364的倍数：364,728,1092,1456,1820,2184,...

286的倍数：286,572,858,1144,1430,1716,2002，...

如果我们把这些列表扩展得足够长，会发现4004是它们共同拥有的第一个数字，所以lcm(364,286)=4004

这种方法效率低下，但并不是无望的。我们知道364×286的积是这两个数字的倍数。我们只是希望能碰巧发现一个较小的公倍数。

下面是另外一个想法。将364和286进行质因数分解：

364=2×2×7×13和286=2×11×13

364的倍数必定包括质数因数2×2×7×13，且286的倍数必须包括质数因数2×11×13。因此，在建立这些数字的公倍数时我们必须有以下几个因数：两个2，一个7，一个11和一个13（我们不需要两个13)。

2×2×7×11×13=4004

而实际上，4004是364和286的最小公倍数。

这似乎是一个很棒的方法，正如我们在本章前面和第一章中所解释的那样，没有一种已知的有效方法来分解大整数。

虽然因数分解并没有给出一个计算两个数字的最小公倍数的高效算法，但它确实带给我们一个重要的见解。我们来比较一下 gcd 和 lcm 的分解方法。

这两个数字的七个质数因数是：

我们通过收集这些列表中的共有质数因数来形成364和286的 gcd 。有两个：2和13。

要创建364和286的公倍数，我们需要合并出现在两个列表中的所有质数。但是，我们不需要两个13（一个就足够了），我们不需要三个2（两个就足够了）。换句话说，我们通过把一个列表中所有的质数和另外一个列表中的所有质数合并，但要将“冗余”的质数(两个列表中共有的质数)去掉就能创建lcm。这些质数有五个：2,2,7,11,13。

检验：

gcd (364,286)=26=2×13

Icm (364,286)=4004=2×2×7×11×13

注意，我们用于lcm的质数包括两个数字的所有质数因数，除了用于gcd的那两个：

换句话说，我们得出

364×286=(2×2×7×13) × (2×11×13)

=(2×2×7×11×13) × (2×13)

= lcm (364,286) ×gcd (364,286)

这个例子没有什么特别之处。对于任何两个正整数 a 和 b ，我们有

a×b = lcm ( a , b ) ×gcd ( a , b )

我们可以重新排列这个公式

由于欧几里得的算法给出了一个有效的方法来计算两个整数的最大公约数，所以它也给出——得益于等式（ D )——找到它们的最小公倍数的有效方法。

解决 gcd 问题的答案。使用欧几里得算法：

1309=1×1105+204

1105=5×204+85

204=2×85+34

85=2×34+17

34=2×17+0

因此：

gcd (1309,1105)= gcd (1105,204)

= gcd (204,85)

= gcd (85,34)

= gcd (34,17)=17

文章来源：《美丽的数学》，作者：美国数学家：爱德华·沙伊纳曼