往期文章
导读
欧几里得算法又称辗转相除法。可以用来求两个整数的最大公约数，两个多项式的最大公因式。在之前的文章《》已经使用了这个算法。本期我们单独来研究它。
回顾
从二年级学习带余数除法后，我们知道
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;
□
