欧几里得辗转相除法证明及推论

一、辗转相除法定义

辗转相除法：以大数除以小数，如果能整除，那么小数就是所求的最大公约数（Greatest CommonDivisor：gcd）。否则就用余数来除刚才的除数；再用这新除法的余数去除刚才的余数。依此类推，直到一个除法能够整除，这时作为除数的数就是所求的最大公约数。即：gcd（x,y）表示x与y的最大公约数，有gcd(x,y)=gcd（y,x%y），如此便可把原问题转化为求两个更小数的公约数，直到其中一个数为0，剩下的另外一个数就是两者的最大公约数。

• 例如：求 4453 和 5767 的最大公约数时，可作如下除法．

  5767÷4453＝1 余 1314

  4453÷1314＝3 余 511

  1314÷511 ＝2 余 292

  511 ÷292 ＝1 余 219

  292 ÷219 ＝1 余 73

  219÷73＝3 于是得知，5767 和 4453 的最大公约数是 73。辗转相除法适用比较广，比短除法要好得多，它能保证求出任意两个数的最大公约数。

二、欧几里得辗转相除法证明

辗转相除法就是给出了一个关系： g c d （ a , b ） = g c d ( b , r ) gcd（a,b）=gcd(b,r) gcd（a,b）=gcd(b,r)，其中a、b、r满足a=bq+r。

设u同时整除a和b，则有

a = s u , b = t u a=su,b=tu a=su,b=tu

则 r = a − b q = s u − t u q = ( s − t q ) u r=a-bq=su-tuq=(s-tq)u r=a−bq=su−tuq=(s−tq)u，得到u也整除r。反过来，每一个整除b和r的整数 v v v，则有

b = s ′ v ， r = t ′ v . b=s'v，r=t'v . b=s′v，r=t′v.

则 a = b q + r = s ′ v q + t ′ v = ( s ′ q + t ′ ) v a=bq+r=s'vq+t'v=(s'q+t')v a=bq+r=s′vq+t′v=(s′q+t′)v，得到 v v v也整除a。

综上：a和b的每一个公因子也是b和r的一个因子，反之亦然。所以a和b的全体公因子集合就与b和r的全体公因子集合相同。所以gcd（a,b）=gcd(b,r)。

三、推论

推论一：如果 d = g c d ( a , b ) d=gcd(a,b) d=gcd(a,b)，则能找到正的或负的整数 k k k和 l l l，使得 d = k a + l b . d=ka+lb. d=ka+lb.

我们在使用辗转相除法时，由于 g c d ( a , 0 ) = a gcd(a,0)=a gcd(a,0)=a,我们可以假设 b ≠ 0 b \neq 0 b​=0。这样我们能写出如下

a = b q 1 + r 1 ( 0 < r 1 < b ) a=bq_1+r_1 (0<r_1<b) a=bq1​+r1​(0<r1​<b)公式一

b = r 1 q 2 + r 2 ( 0 < r 2 < r 1 ) b=r_1q_2+r_2(0<r_2<r_1) b=r1​q2​+r2​(0<r2​<r1​)

r 1 = r 2 q 3 + r 3 ( 0 < r 3 < r 2 ) r_1=r_2q_3+r_3(0<r_3<r_2) r1​=r2​q3​+r3​(0<r3​<r2​)

r 2 = r 3 q 4 + r 4 ( 0 < r 4 < r 3 ) r_2=r_3q_4+r_4(0<r_4<r_3) r2​=r3​q4​+r4​(0<r4​<r3​)

…

只要余数 r 1 , r 2 , r 3 , r 4 . . . . . r_1,r_2,r_3,r_4..... r1​,r2​,r3​,r4​.....不是0就继续写下去。从右边的不等式，可以看出余数形成了一个严格递减序列： b > r 1 > r 2 > r 3 > . . . . > 0 b>r_1>r_2>r_3>....>0 b>r1​>r2​>r3​>....>0。因此最多b步，0这个余数必然出现。

r n − 2 = r n − 1 q n + r n r_{n-2}=r_{n-1}q_n+r_n rn−2​=rn−1​qn​+rn​

r n − 1 = r n q n + 1 + 0 r_{n-1}=r_nq_{n+1}+0 rn−1​=rn​qn+1​+0

此时，我们就得到 r n = g c d ( a , b ) r_n=gcd(a,b) rn​=gcd(a,b);

在公式一中，我们可以推出 r 1 = a − q 1 b r_1=a-q_1b r1​=a−q1​b,所以 r 1 r_1 r1​可以写成 k 1 a + l 1 b k_1a+l_1b k1​a+l1​b的形式。所以

r 2 = b − q 2 r 1 = b − q 2 ( k 1 a + l 1 b ) = ( − q 2 k 1 ) a + ( 1 − q 2 l 1 ) b = k 2 a + l 2 b r_2=b-q_2r_1=b-q_2(k_1a+l_1b)=(-q_2k_1)a+(1-q_2l_1)b=k_2a+l_2b r2​=b−q2​r1​=b−q2​(k1​a+l1​b)=(−q2​k1​)a+(1−q2​l1​)b=k2​a+l2​b，显然，通过这一串余数 r 3 , r 4 . . . . . r_3,r_4..... r3​,r4​.....的结果，推导出 r n = g c d ( a , b ) = k a + l b r_n=gcd(a,b)=ka+lb rn​=gcd(a,b)=ka+lb。

推论二：如果一个素数p整除乘积ab，则p必整除a或b。

因为p整除ab，所以 a b = p r ab=pr ab=pr。

因素数p仅有因子p和1，所以如果p不整除a，则gcd（a，p）=1，根据上面的推论一我们能找到整数 k k k和 l l l，使得 1 = k a + l p 1=ka+lp 1=ka+lp.在等式两边同时乘以b，我们得到： b = k a b + l p b = k p r + l p b = p ( k r + l b ) b=kab+lpb=kpr+lpb=p(kr+lb) b=kab+lpb=kpr+lpb=p(kr+lb)，到此显然p整除b。

同理，当p不整除b时，可以证得p整除a。

综上，命题“如果一个素数p整除乘积ab，则p必整除a或b”得证。

注意：不妨举几个例子印证推论二。

• 13是2652的一个因子，以及2652=6*442，就可以得出13是442的因子。
• 6是240的一个因子，而240=15*16，但6既不是15也不是16的因子。why？这表明p是素数这个前提是不可或缺的。