この記事は最終更新日から1年以上が経過しています。内容が古くなっているのでご注意ください。
はじめに
最大公約数を求める方法と聞かれてあなたは何と答えますか？
割り算を逆に書いて、小さい数からどんどん割っていくというのが真っ先に思い浮かぶと思います。
それでは、3355と2379の最大公約数を求めてみましょう。
このように大きい数の最大公約数を求めるとき、2でも割れない、3でも、5でも…と繰り返していくのは非常に時間がかかってしまいます。
そんな悩みを解決することができるのが「ユークリッドの互除法」という方法です。
どんなに大きな数字になっても少ない手順で最大公約数を求めることができる、とても便利な方法です。
この記事ではユークリッドの互除法を使った最大公約数の求め方、どうして最大公約数が求まるのかといった基本的なところから、センター試験で頻出の整数問題への応用まで解説します。
ユークリッドの互除法とは？
ユークリッドの互除法を知らないあなたも、まずは実際にどんな解き方をするのか見てみましょう。
実際に3355と2379の最大公約数を求めてみます。
このように
小さい数で大きい数を割る
あまりで割る数を割る
さらにあまりで割る数を割る…
と割り切れるまで続けます。そして最後の割る数が最大公約数となるのです。
ユークリッドの「互除法」とは「割り切れるまであまりで互いに割り（除法）続ける」という意味なんですね。
ユークリッドの互除法の証明
どうしてユークリッドの互除法で最大公約数が求まるのでしょうか。
直感的に理解するのはなかなか難しい計算方法なので、正確に証明してみます。
ユークリッドの互除法を証明する前に、
ということを証明します。
ということがわかりました。
今証明したのは、
「割られる数と割る数の最大公約数と割る数とあまりの最大公約数は一致する」
ということです。
言い換えると
「ユークリッドの互除法の操作を何回行っても、割られる数と割る数は一致する」
ということになります。
割り切れたときには、割る数が最大公約数なのは自明です。
よって、「割り切れるまでユークリッドの互除法を続けたときの最後の割る数が最大公約数である」ということが言えるのです。
ユークリッドの互除法の整数問題への応用
さて、ユークリッドの互除法は最大公約数を求める方法である、ということが感覚的にも理屈的にもわかっていただけたんじゃないかなと思います。
実は互除法にはもう1つ、整数問題の解を見つけるのに役立つという便利な使い方があるのです。
むしろ大学入試で頻出なのはこちらといっても良いでしょう。
まずは例を見てみましょう。
この問題を解くのにユークリッドの互除法は一見結びつかないかもしれません。
しかし、このax+by=1の形を解くのに実はユークリッドの互除法が大活躍するのです。
11と8について互除法で計算してみましょう。
このように互除法の計算式をそれぞれあまりについて整理してみます。（右側の式）
これをどんどん代入していくと、解が求まるようになっているのです。
これは与えられた式にx=3,y=-4を代入した式ですね。
よって、(x,y)=(3,-4)が求める答えになります。
今回のように、入試では
「ax+by=1を満たす整数(x,y)を求めよ」
といったような問題が出ることがあります。
ユークリッドの互除法のやり方さえわかっていれば、闇雲に当てはめる必要なく、計算で求めることができます。とても便利ですね！
