更相減損法是什麽?原理是什麽?

更相減損術,或稱“輾轉相除法”是用來求最大公約數的． 給出兩個正整數a和b，用b除a得商a0，余數r，寫成式子：a=a0b+r，0≤r＜b． ..........(1) 這是最基本的式子．如果r等於0，那麽b可以除盡a，而a、b的最大公約數就是b． 如果r≠0，再用r除b，得商a1，余數r1，即：b=a1r+r1，0≤r1＜r．............ (2) 如果r1=0，那麽r除盡b，由(1)也除盡a，所以r是a、b的公約數．反之，任何壹個除盡a、b的數，由(1)，也除盡r，因此r是a、b的最大公約數． 如果r1≠0，則用r1除r得商a2，余數r2，即：r=a2r1+r2，0≤r2＜r1． ...........(3) 如果r2=0，那麽由(2)可知r1是b、r的公約數，由(1)，r1也是a、b的公約數．反之，如果壹數除得盡a、b，那末由(1)，它壹定也除得盡b、r，由(2)，它壹定除得盡r、r1，所以r1是a、b的最大公約數． 如果r2≠0，再用r2除r1，如法進行．由於b＞r＞r1＞r2＞......逐步小下來，而又都是正整數，因此經過有限步驟後壹定可以找到a、b的最大公約數d(它可能是1)．這就是有名的輾轉相除法，在外國稱為歐幾裏得算法． 例子:求42897與18644的最大公約數： 42897=2×18644+5609， (i) 18644=3×5609+1817， (ii) 5609=3×1817+158， (iii) 1817=11×158+79， (iv) 158=2×79． 所以，42897與18644的最大公約數=79