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