更相减损法是什么原理是什么更相减损法求最大公约数具有什么性质

文章插图
大家好,小跳来为大家解答以上的问题。更相减损法求最大公约数具有什么性质，更相减损法是什么原理是什么这个很多人还不知道,现在让我们一起来看看吧！
1、更相减损术,或称“辗转相除法”是用来求最大公约数的．给出两个正整数a和b，用b除a得商a0，余数r 。
2、写成式子：a=a0b+r，0≤r＜b． ..........(1) 这是最基本的式子．如果r等于0，那么b可以除尽a 。
3、而a、b的最大公约数就是b．如果r≠0，再用r除b，得商a1 。
4、余数r1，即：b=a1r+r1 ， 0≤r1＜r．............ (2) 如果r1=0 。
5、那么r除尽b ，由(1)也除尽a ，所以r是a、b的公约数．反之。
6、任何一个除尽a、b的数，由(1)，也除尽r 。
7、因此r是a、b的最大公约数．如果r1≠0，则用r1除r得商a2，余数r2 。
8、即：r=a2r1+r2，0≤r2＜r1． ...........(3) 如果r2=0，那么由(2)可知r1是b、r的公约数。
9、由(1)，r1也是a、b的公约数．反之，如果一数除得尽a、b 。
10、那末由(1)，它一定也除得尽b、r ，由(2) 。
11、它一定除得尽r、r1，所以r1是a、b的最大公约数．如果r2≠0，再用r2除r1 。
12、如法进行．由于b＞r＞r1＞r2＞......逐步小下来，而又都是正整数，因此经过有限步骤后一定可以找到a、b的最大公约数d(它可能是1)．这就是有名的辗转相除法。
13、在外国称为欧几里得算法．例子:求42897与18644的最大公约数： 42897=2×18644+5609，(i) 18644=3×5609+1817，(ii) 5609=3×1817+158 。
14、 (iii) 1817=11×158+79，(iv) 158=2×79．所以，42897与18644的最大公约数=79 。
【更相减损法是什么原理是什么更相减损法求最大公约数具有什么性质】本文到此分享完毕，希望对大家有所帮助。

更相减损法是什么 原理是什么 更相减损法求最大公约数具有什么性质

更相减损法是什么原理是什么更相减损法求最大公约数具有什么性质