初等数论书中的最大公因数的辗转相除法求法

根据最大公因数的定义和性质，我们可以得到多种求最大公因数的方法，在此只介绍常用的、重要的基本方法.

（1)分解质因数法.

根据定理5可知，几个数的公因数是这几个数最大公因数的因数，由此和最大公因数的定义，我们可以得到求最大公因数的分解质因数法，其过程如下：

①写出各数的标准分解式；

②写出各分解式共同的质因数及其最小次方数，并把如此得到的幂写成连乘的形式.

例3 求（60，108，24).

解 ∵60=22×3×5，108=22×33，24=23×3，∴（60，108，24)=22×3=12.

（2)提取公因数法（短除法).

根据定理7，可用逐步提取公因数的方法求几个数的最大公因数.

例4 求（162，216，378，108).

解 （162，216，378，108)=2×（81，108，189，54)=2×9（9，12，21，6)

=18×3（3，4，7，2)=54×1=54.

这一过程通常写成下面的短除形式：

∵（3，4，7，2)=1，∴（162，216，378，108)=2×9×3=54.

（3)辗转相除法.

从定理3和定理4的证明过程，可以得到求两个正整数的最大公因数的一般性方法.下面举例说明.(www.xing528.com)

例5 求（5767，4453).

解 ∵5767=4453×1＋1314，∴（5767，4453)=（4453，1314)；

∵4453=1314×3＋511，∴（4453，1314)=（1314，511)；

∵1314=511×2＋292，∴（1314，511)=（511，292)；

∵511=292×1＋219，∴（511，292)=（292，219)；

∵292=219×1＋73，∴（292，219)=（219，73)；

∵219=73×3＋0，∴（219，73)=73.

∴（5767，4453)=73.

上述过程数据、符号书写重复太多，可以简化为下面的竖式：

所以（5767，4453)=73；（a，b)=（b，r1)=（r1，r2)=….

这种方法叫作辗转相除法，也叫作欧几里得算法.它具有一般性，当难以发现非1公因数时非常有效，如用来证明两数互质.在以后各章也均有应用，在理论上也具有重要价值.

例6 求（1008，1260，882，1134).

分析 可改求（（（1008，1260)，882)，1134)或（（1008，1260)，（882，1134)).

解 由辗转相除法可得

而（252，126)=126，故（1008，1260，882，1134)=126.