ユークリッドの互除法
2つの数A、Bがある時、大きい方から小さい方を引き続けて、両方の数が同じになったときに、その数がA、Bの最大公約数になる。
最大公約数($ \mathrm{GCD})は必ず両方共通である。 $ A_0 = a_0 \cdot \mathrm{GCD}
$ B_0 = b_0 \cdot \mathrm{GCD}
ここで、AとBの大きい方から小さい方を引くということは、新しい値は必ず $ |a_n-b_n|\cdot \mathrm{GCD}になる。
これを繰り返していくと、最後は$ |a_n-b_n| \cdot \mathrm{GCD} = 1 \cdot \mathrm{GCD}]にたどり着く。