4.3　证明的第三个途径

这是利用辗转相除法（3定理4），在由它证明的3定理5的基础上实现的.

显见，当u₁|u₀时，3定理5仍成立，这定理包含了三个方面的重要内容：

（Ⅰ）3定理5的（i）表明辗转相除法给出了求两个数的最大公约数的方便实用的算法；

（Ⅱ）3定理5的（ii）是利用辗转相除法给出了定理2当k=2时成立的直接证明；

（Ⅲ）3定理5的（iii）是利用辗转相除法不仅给出了定理8当k=2时成立的直接证明，而且给出了求系数的算法（见习题三第二部分第5题）.

由3定理5出发建立最大公约数理论可依如下途径：

以上推导的详细证明留给读者，在证明中只许应用1和2中的结论（参看前两个证明途径中的推导）.有了定理2和定理8后，就可如同第一和第二个途径一样，推出其他结论.

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

由4定理4（i）及2例6知

由此及2例6得：（198，252，924）=6，

6=924-51·18=924-51（4·252-5·198）=924-204·252+255·198.