1. 首頁 > 生活經驗 > >

更相減損法是什么 原理是什么 更相減損法求最大公約數具有什么性質

知識經驗


更相減損法是什么 原理是什么 更相減損法求最大公約數具有什么性質

文章插圖
大家好,小跳來為大家解答以上的問題 。更相減損法求最大公約數具有什么性質 ， 更相減損法是什么 原理是什么這個很多人還不知道,現在讓我們一起來看看吧！
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 。
【更相減損法是什么 原理是什么 更相減損法求最大公約數具有什么性質】本文到此分享完畢，希望對大家有所幫助 。