辗转相除法求最大公因式 辗转相除法例子？

辗转相除法例子？

典型示例：

1。旋转除法

例1。求两个正数8251和6105的最大公因数。

（分析：旋转除法→零余数→结果）

解：8251=6105×1+2146

显然，8251和6105的最大公因数也必须是2146，6105和2146的公因数也必须是8251，所以8251和6105的最大公因数也是6105和2146的最大公因数。

6105=2146×2+1813

2146=1813×1+333

1813=333×5+148

333=148×2+37

148=37×4+0

则37是8251和6105的最大公因数。

上述求最大公因数的方法是依次除法。也称为欧几里德算法，它最早是由欧几里德在公元前300年左右提出的。

1. 为什么用这个算法能得到两个数的最大公因数？

用除法计算最大公因数的步骤如下：

第一步：将较大的数m除以较小的数n，得到商Q0和余数R0；

第二步：如果R0=0，则n是m和n的最大公因数；如果R0≠0，则将除数n除以余数R0得到商Q1和余数R1；

第三步：如果R1=0，则R1是M，N的最大公因数；如果R1≠0，则将除数R0除以余数R1得到商Q2和余数R2；

然后依次计算，直到RN=0，其中RN-1是最大公因数。

辗转相除法求最大公因式 辗转相除法步骤 辗转相除法举例子

版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。