輾轉相除的reason是什麼

輾轉相除法",中國古代叫作"更相減損求等",有兩個應用:
(1)求兩數a,b的最大公因數
(2)求不定方程式ax+by=c的整數解

預備性質(1)若,則對任意整數m,n,
預備性質(2)若,則

輾轉相除法原理
a,b是整數,則存在整數q,r,,使得a=bq+r,這叫作歐幾里德除法原理
此時(a,b)=(b,r) 這叫作輾轉相除法原理
證明
假設(a,b)=d,(b,r)=d'
因為(a,b)=d,則,由(1) ,亦即 ,由(2) ,亦即d
又,因為(b,r)=d',則,由(1) ,亦即 ,由(2) ,亦即
,所以d=d',得證

3.求最大公因數時，有兩種方法，一種是「短除法」，一種是「輾轉相除法」！

A、短除法，將數字以橫寫方式，在畫一底線，在最左方數字旁，畫一垂直與底線的現段，再來在此線段的左方寫出可以「整除」要求的數字，要求得數字被除後的商，再繼續重複除！直到「無法再除」！而左方那些數字就是他們得公因數！全部乘起來就是最大公因數，任意乘就是公因數！

B、輾轉相除法（注意，此法只能求最大公因數），將其中兩個數字兩旁「都劃上」往下得直線！所以有三條！以最小的數複製到最大數的下方，然後相減，減完的數再往小的地方去複製、相減！直到其中一數為「0」！而另一方的數則是最大公因數！

輾轉相除是找出兩數是否互質的一種最常用的方法，是指有兩數 x 和y, 把它們大減小至無法減為止。若最後之數為 1, 則兩數互質；若最後之數為零, 兩數不互質。

例:
567, 2205
567, 504 (2205 - 567 x 3 = 2205 - 1701)
63 (567 - 504), 504
63, 0 ( 504 - 63 x 8 = 504 - 504)

so 567 and 2205 不互質, 均可被63 整除

625, 882
625, 257
111, 257
111, 35
6, 35
6, 5
1, 5

so 625 and 882 互質