はじめに
最大公約数を求める方法と聞かれてあなたは何と答えますか？
割り算を逆に書いて、小さい数からどんどん割っていくというのが真っ先に思い浮かぶと思います。
それでは、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)を求めよ」
といったような問題が出ることがあります。
ユークリッドの互除法のやり方さえわかっていれば、闇雲に当てはめる必要なく、計算で求めることができます。とても便利ですね！
センター試験を解いてみよう
さて、それでは実際の入試問題でユークリッドの互除法がどのように使われるかを見てみましょう。
平成28年度センター試験数学1A第4問
92x+197y=1
は正に先ほど見たax+by=1の形ですね。
ユークリッドの互除法を用いて解いてみましょう。
これにより（x,y)=(15,-7)が題意を満たすことがわかりました。
しかし、この問題では「xの絶対値が最小のもの」という条件がついています。この解が本当に絶対値が最小かどうかを確かめるためには、一般解を求めなければいけません。
一般解を求めるためには、求めた一つの解を式から引いてみましょう
92×15+197×(-7)=1より92×150+197×(-70)=10ですね。
これを92x+197y=10から引くと、同様に解くことが出来ます。
最後に
今回はユークリッドの互除法の計算方法、証明、整数問題への応用と見てきました。
特にユークリッドの互除法を使った整数問題は、センター試験でもかなり高い頻度で出題される超重要科目です。
解を見つけるためのポイントは、「互いに割り続けることであまり1を作ること。」
ぜひユークリッドの互除法の使い方をマスターして、入試に役立ててください！
