【最大公約数】ユークリッドの互助法を使えるようになりましょう!

ユークリッドの互除法を使えば、素因数分解が難しい比較的大きな数どうしでも最大公約数を求められます。

なぜ互除法で最大公約数が求められるのか、その理由を知らなくても、ともかく使えてしまえれば、機械的に最大公約数が求められるようになるので、最初に具体的な使い方を説明し、その後その理由を説明します。

最大公約数とは何か

今更かもしれませんが「最大公約数」の意味から確認しましょう。公約数とは次のようなものですね。

ですから「最大公約数」とは、公約数の中で最大のものを言います。

小さな数なら小学生や中学生でも最大公約数を見つけられますが、大きな数どうしとなると簡単には見つけられない場合が多くあります。

しかし「ユークリッドの互助法」を使えば、機械的な作業で必ず最大公約数を見つけられます。

さっそくユークリッドの互助法を使ってみる

では早速「ユークリッドの互助法」を使ってみましょう。次の問題を解いてみます。

このふたつの数では直感的に公約数を求めるのは無理ですね。そこで「ユークリッドの互助法」の出番です。

順を追って説明します。まずふたつの数で大きな数を小さな数で割り算しましょう。このとき下の図のように紙の右端に書くようにします。

商は「1」余りは「177」ですね。次に割った数の「649」を余りである「177」で割ります。次のように書いてください。これを続けていくので紙の右端から書くと都合がよいのです。

商は「3」余りは「118」ですね。今度は「177」を「118」で割ります。

これを繰り返し、余りが「0」になるまで続けます。

すると最後に現れた「59」が実は「826」と「649」の最大公約数なのです。

やり方さえ知っていれば確実に最大公約数が求められますね。

互助法で最大公約数が求められる理由

では、このようにすると、なぜ最大公約数が求められるのでしょうか?

ここでは誰にでもわかりやすいように、厳密な方法ではなく、具体値を使って簡易的に説明します。

最大公約数の図形的な意味を考えます。

例えば「18」と「24」の最大公約数は「6」ですが、それは縦と横の長さがそれぞれ「18」と「24」である長方形の中に、できるだけ大きな正方形のタイルを詰めるイメージで考えることができます。その正方形の辺の長さが「18」と「24」の最大公約数「6」を意味しています。

ところで「24」を「18」で割った余りは「6」ですが、当然なことながら、その余りも最大公約数で割り切れますね。

このことを覚えておいて下さい。

ユークリッドの互除法の図形的な意味

ではユークリッドの互助法の計算と図形的な意味を照らし合わせてみましょう。

縦が「649」横が「826」の長方形を考えます。

最初に「826」を「649」で割るのは、この長方形の中に、1辺が「649」の正方形、すなわち、いちばん大きな正方形がいくつでき、その余りがいくつなのか求めているのと同じです。

さて、今度はその余りの長方形には着目しましょう。その長方形の中に、できるだけ大きな正方形がいくつできるのか、その余りはいくなのかを考えます。余りは「118」ですね。

次にまた、その余りの長方形の中にできるだけ大きな正方形を作ります。余りは「59」ですね。

次に「118」を「59」で割ります。

するとあまりが無くなり、ちょうど長方形が正方形に分割されました。

この正方形の1辺の長さ「59」が最大公約数となる訳ですが、それは次のように逆算していけば理由がわかります。

ひとつ前に作った正方形は、最後にできた正方形でちょうど分割できるはずです。前の図と次の図を見比べて考えてみて下さいね。

そのまた前の正方形だって最後にできた正方形で分割できます。

これを最初まで戻せば、すべて最後に求めた正方形で分割できるという訳です。

ですから「826」と「649」の最大公約数は「59」となるのです。

まとめ

「ユークリッドの互助法」の使い方さえ知っていれば最大公約数を機械的な作業だけで求められます。その理由は長方形の面積で考えれば理解できるでしょう。

互助法は最大公約数を求めるだけに役立つのではありませんが、これに一度納得できてしまえば、今後「ユークリッドの互助法」を用いた応用問題にも果敢にチャレンジできるようになるでしょう。