3.2　辗转相除法

带余数除法的一个重要推广就是下面的辗转相除法，亦称Euclid算法，它有十分重要的理论和应用价值.

定理4（辗转相除法）设u₀，u₁是给定的两个整数，u₁≠0，u₁｜/u₀.我们一定可以重复应用定理1得到下面k+1个等式：

以上的算法就称为辗转相除法或Euclid算法.

证对u₀，u₁应用定理1，由u₁｜/u₀知必有第一式成立.同样地，如果u₂｜/u₁就得到第二式；如果u₂|u₁就证明定理对k=1成立.继续这样做，就得到

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

及前面j个等式成立.若u_j+1|u_j，则定理对k=j成立；若u_j+1｜/u_j，则继续对u_j，u_j+1用定理1.由于小于|u₁|的正整数只有有限个以及1整除任一整数，所以这过程不能无限制地做下去，一定会出现某个k，要么1＜u_k+1|u_k，要么1=u_k+1|u_k.证毕.

在下节我们将分别应用带余数除法和辗转相除法来建立最大公约数理论.下面的定理是后一途径的基础，它由定理4立即推出，所以先在这里证明.

定理5在定理4的条件和符号下，我们有

（i）u_k+1=（u₀，u₁），即最后一个不等于0的余数u_k+1就是u₀和u₁的最大公约数；（6）

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

（iii）存在整数x₀，x₁，使

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

即两个整数的最大公约数一定可表为这两个整数的整系数线性组合.

证利用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的整系数线性组合，利用式（5）的第k-1式可消去这个整系数线性表示式中的u_k，得到u_k+1表示为u_k-2和u_k-1的整系数线性组合.这样，依此利用式（5）第k-2，k-3，…，2，1式，就可相应地消去u_k-1，u_k-2，…，u₃，u₂，最后得到u_k+1表示为u₀和u₁的整系数线性组合，这就证明了（iii）.如何求出x₀，x₁可见习题三的第二部分.

辗转相除法在数论中十分有用，例如，在连分数（见第七章1例2）中.下面来举两个例子.

例6求198和252的最大公约数，并把它表为198和252的整系数线性组合.

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

例7设m，n是正整数.证明

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

证不妨设m≥n.由带余数除法得

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

我们有