神马作文网辗转相除法 例子
来源：学生作业帮 编辑：神马作文网作业帮 分类：数学作业 时间：2024/11/18 06:11:32
辗转相除法 例子
典型例题：
一.辗转相除法
例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即为所求的最大公因数.
一.辗转相除法
例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即为所求的最大公因数.