ユークリッドの互除法
はじめに
競プロをやってると、2つの自然数の最大公約数を求める問題が出てくる。
その時に使うのがユークリッドの互除法という手法。
ユークリッドの互除法がなぜ成り立つのか考えたのをまとめる。
（厳密な証明ではなく、ユークリッドの互除法がなぜ成立するかがなんとなく分かることを目標に書いているので証明が知りたい方はブラウザバックを推奨します）
ユークリッドの互除法とは
自然数 があるとき、
（式1）
（式2）
（式3）
という処理を余りが0になるまで繰り返した時の最後の商が最大公約数というものである。
例
(問題) 1071 と 1029 の最大公約数を求める。
1071 を 1029 で割った余りは 42
1029 を 42 で割った余りは 21
42 を 21 で割った余りは 0
よって、最大公約数は21である。
考察
式1において考える。
の最大公約数を
とすると、式1は
と変換できる（これは自明）。
すなわち、全ての項は の倍数である。
上記の式1つ1つを1ステップとすると、 1ステップ毎に割る数と割られる数（式1におけるbとa）を小さくしてくと 最終的に余りが0になり、最小公倍数が求められる。
（考察の部分がかなりざっくりなのであとでちゃんと調べます。）
