3.2　輾轉(zhuǎn)相除法

帶余數(shù)除法的一個(gè)重要推廣就是下面的輾轉(zhuǎn)相除法，亦稱Euclid算法，它有十分重要的理論和應(yīng)用價(jià)值.

定理4（輾轉(zhuǎn)相除法）設(shè)u₀，u₁是給定的兩個(gè)整數(shù)，u₁≠0，u₁｜/u₀.我們一定可以重復(fù)應(yīng)用定理1得到下面k+1個(gè)等式：

以上的算法就稱為輾轉(zhuǎn)相除法或Euclid算法.

證對(duì)u₀，u₁應(yīng)用定理1，由u₁｜/u₀知必有第一式成立.同樣地，如果u₂｜/u₁就得到第二式；如果u₂|u₁就證明定理對(duì)k=1成立.繼續(xù)這樣做，就得到

|u₁|＞u₂＞u₃＞…＞u_j+1＞0

及前面j個(gè)等式成立.若u_j+1|u_j，則定理對(duì)k=j成立；若u_j+1｜/u_j，則繼續(xù)對(duì)u_j，u_j+1用定理1.由于小于|u₁|的正整數(shù)只有有限個(gè)以及1整除任一整數(shù)，所以這過程不能無限制地做下去，一定會(huì)出現(xiàn)某個(gè)k，要么1＜u_k+1|u_k，要么1=u_k+1|u_k.證畢.

在下節(jié)我們將分別應(yīng)用帶余數(shù)除法和輾轉(zhuǎn)相除法來建立最大公約數(shù)理論.下面的定理是后一途徑的基礎(chǔ)，它由定理4立即推出，所以先在這里證明.

定理5在定理4的條件和符號(hào)下，我們有

（i）u_k+1=（u₀，u₁），即最后一個(gè)不等于0的余數(shù)u_k+1就是u₀和u₁的最大公約數(shù)；（6）

（ii）d|u₀且d|u₁的充分必要條件是d|u_k+1；

（iii）存在整數(shù)x₀，x₁，使

u_k+1=x₀u₀+x₁u₁，（7）

即兩個(gè)整數(shù)的最大公約數(shù)一定可表為這兩個(gè)整數(shù)的整系數(shù)線性組合.

證利用2定理8的（i）和（iv），從式（5）的最后一式開始，依次往上推，可得

u_k+1=（u_k+1，u_k）=（u_k，u_k-1）=（u_k-1，u_k-2）=…=（u₄，u₃）=（u₃，u₂）=（u₂，u₁）=（u₁，u₀），（8）

這就證明了（i）.利用2定理1的（ii）和（iii），從式（5）立即推出（ii）.由式（5）的第k式知u_k+1可表示成u_k-1和u_k的整系數(shù)線性組合，利用式（5）的第k-1式可消去這個(gè)整系數(shù)線性表示式中的u_k，得到u_k+1表示為u_k-2和u_k-1的整系數(shù)線性組合.這樣，依此利用式（5）第k-2，k-3，…，2，1式，就可相應(yīng)地消去u_k-1，u_k-2，…，u₃，u₂，最后得到u_k+1表示為u₀和u₁的整系數(shù)線性組合，這就證明了（iii）.如何求出x₀，x₁可見習(xí)題三的第二部分.

輾轉(zhuǎn)相除法在數(shù)論中十分有用，例如，在連分?jǐn)?shù)（見第七章1例2）中.下面來舉兩個(gè)例子.

例6求198和252的最大公約數(shù)，并把它表為198和252的整系數(shù)線性組合.

（252，198）=（198，54）=（54，36）=（36，18）=18.

例7設(shè)m，n是正整數(shù).證明

（2^m-1，2ⁿ-1）=2^（m，n）-1.

證不妨設(shè)m≥n.由帶余數(shù)除法得

m=q₁n+r₁，0≤r₁＜n.

我們有