Question

辗转相除法为什么能求出的就是最大公因数？

Answer 1

辗转相除法,
又名欧几里得算法（Euclidean
algorithm）乃求两个正整数之最大公因数的算法。
辗转相除法是利用以下性质来确定两个正整数
a
和
b
的最大公因数的：
若
r
是
a
÷
b
的余数,
则
gcd(a,b)
=
gcd(b,r)
a
和其倍数之最大公因数为
a。
另一种写法是：
a
÷
b，令r为所得余数（0≤r＜b）
若
r
=
0，算法结束；b
即为答案。
互换：置
a←b，b←r，并返回第一步。