概要
を で割って とすると、 と の最大公約数= と の最大公約数となる。
これを用いて、 大きい つの数の最大公約数を求める方法を、ユークリッドの互除法という。
紀元前 年頃に作られた、明示的に書かれた最古のアルゴリズムなので、歴史を感じながら使っていこう。
証明は、例えばAKITOさんの動画を参照。
例
と の最大公約数を、ユークリッドの互除法を繰り返し用いて求める。
余りが になるまで続けて、最後に出てきた余りが最大公約数。
最後の余りは、下から つ目の式の であり、最大公約数は とわかる。
と の最大公約数を考えていたのが、 つ目の式で と の最大公約数となり、2つ目の式で と の最大公約数となり・・・と、最大公約数を考える つの数がどんどん小さくなっていくイメージ。
補足
ユークリッドの互除法の式変形は、 一次不定方程式の解を見つけるときにも活躍する。例えば、
の解を求めてみよう。
まずは何かしら解を一つ見つけてくることから物語は始まる（特殊解という）。その作業において、ユークリッドの互除法が活躍する。いま、 と の係数である と は互いに素、つまり最大公約数が であるので、とりあえずは右辺を とした方程式を考えてみる（あとで解を 倍すればOK）。
ここで、 と にユークリッドの互除法を用いると、
余りが になった時点でストップして、これを遡って式変形する。イメージはこんな感じで、一つ上の式の余りを使って数字を大きくしていく。
そうすると、 は の解であることがわかる。（ユークリッドの互除法をいちいち使わなくても、気合いや心の目で見つけてきてもOK）
よって、この解を 倍した は、解きたい方程式 の解の つであることがわかる（特殊解が見つかった、ハッピー！）。そこで、
を辺々引くと、
となる。ここで、 と は互いに素であるので、 は の倍数となり、 を整数として
と表されることが必要。このとき、 より、
となり、確かに整数 も存在する（十分性の確認）。よって、元々の一次不定方程式 の解は全て、整数 を用いて
と表せることがわかる。
