欧几里得算法程序设计辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的：⒈ 若 r 是 a ÷ b 的余数，且r不为0， 则gcd(a,b) = gcd(b,r)⒉ a 和其倍数之最大公因子为 a
另一种写法是：⒈ 令r为a/b所得余数（0≤r若 r= 0，算法结束；b 即为答案
⒉ 互换：置 a←b，b←r，并返回第一步
以上内容由大学时代综合整理自互联网，实际情况请以官方资料为准。
