A = Bq + R...(I), (A,B) = Gとおくと A=Ga, B=Gbとおける。このときaとbは互いに素である。(I)に代入すると
Ga = (Gb)q + R...(II)
G(a-bq) = R となりGはRの約数である(★)。R=Grとおく。(II)に代入すると
Ga = Gbq + Gr
Ga = G(bq + r)
a = bq + r...(III)
(b, r) = gが存在すると仮定すると b = gs, r = gtとおける。これを(III)に代入すると
a = gsq + gt
a = g(sq + t) となりgはaの約数となる。b = gsよりaとbが互いに素の条件を満たさない。よって(b, r)=gは存在しない。(☆)
よって(A,B)=Gとすると、★と☆より(B,R)=G.(A,B)の最大公約数と(B,R)の最大公約数が一緒。
ユークリッドの互除法はその性質を利用して漸化的に求めていく方法。

(A, B) = (B, R)を順次適用していくことでgcdを求める
(An, Bn) = (Bn, Rn)
Bn = 0 -> return An
otherwise -> (Bn, An%Bn)