1.算法說明：

輾轉相除法是利用以下性質來確定兩個正整數 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，并返回第一步。

網上鏈接

2.偽代碼：

input(a,b)
c = remainder(a/b)
if c = 0
return(b)
else:
a = b
b = c

3.測試過程：