同余（十）——欧几里得辗转相除法

往期文章

导读

欧几里得算法又称辗转相除法。可以用来求两个整数的最大公约数，两个多项式的最大公因式。在之前的文章《》已经使用了这个算法。本期我们单独来研究它。

回顾

从二年级学习带余数除法后，我们知道

7÷2=3……1

写成一般的形式：

设m是非零整数，n是任意整数，则可以唯一确定整数q和r,

使得

n÷m=q……r （0≤r＜|m|）

即

n=m×q+r （0≤r＜|m|）

其中q和r分别称为商和余数。

引理若有等式

n=m×q+r ①

则有(n，m)=(m，r)。

证明：若p|m，p|r, 由①得，p|n。这就是说m、r的公约数都是n、m的公约数。

反过来若p|n, p|m，则p一定整除它们的组合

r=n-m×q

这就是说p是m、r的公约数。由此可见，如果n、m有一个最大公约数p，那么p也是m、r的最大公约数。 □

应用

找1804与328的最大公约数,

1804÷328=5……164

因此

1804=5×328+164

可知

（1804, 328）=（328,164）

继续进行上述的步骤

328=2×164+0

所以

（328,164）=（164, 0）=164

故

（1804, 328）=164.

下面给出一般化的算法。

辗转相除法

算法 设n，m是两个不全为0的整数，

找出最大公因数（n, m）.

分析

我们可以假设,m≠0，这样通过连除我们能写出，

n=q1×m+r1 （0≤r1＜|m|）

m=q2×r1+r2 （0≤r2＜|r1|）

r1=q3×r2+r3 (0≤r3＜|r2|）

… … … …

只要余数不为0就继续写下去，从右边的不等式，我们可以看到一连串的余数形成一个严格递减数列

m>|r1|>|r2|>……≥0

因此最多m步，0这个余数一定出现。

rs-2=qs×rs-1+rs

rs-1=qs+1×rs+0

这是我们知道

(n,m)=(m，r1)，

(m，r1)=(r1，r2)，

(r1，r2)=(r2，r3)，

……

(rs-1，rs)=(rs，0)，

(rs，0)=rs，

得到

(n,m)=rs;

□