ユークリッドの互除法を長方形の図で徹底図解

はじめに｜式だけだと、なぜかピンとこない

ユークリッドの互除法は、2つの整数 a・b の最大公約数を求める手法です。手順自体はとてもシンプルなのに、式変形の解説を読むと、直感的にわかりづらいと感じる人は少なくないのではないでしょうか。

私自身、高校数学を学んだとき「こんなことを習ったかな」と思い返しながら読み返しても、いまひとつ腹に落ちませんでした。そこでこの記事では、計算式ではなく「長方形を正方形で切り分けていく図」 で、ユークリッドの互除法を考えてみたいと思います。

ユークリッドの互除法の基本手順

まずは王道の手順を確認しておきましょう。これは次の2ステップを、余りが0になるまで繰り返すだけです。

Step1：a を b で割ったときの余りを r とする。

Step2：r＝0 ならば、そのときの b が最大公約数。　　r＞0 ならば、a を b に、b を r に置き換えて Step1 に戻る。

この手順を、具体例で確かめてみます。よく使われるのが「2059 と 899」の例で、最大公約数は 29 になります。

長方形で考える｜「長辺 ÷ 短辺」を繰り返すだけ

考え方はとてもシンプルです。辺 a・b の長方形を描き、次のステップを踏んでいきます。

　　　Step1: “長辺” ÷ “短辺”　　（長辺を短辺で割る）

　　　Step2: 余った領域を、また“長辺” ÷ “短辺”

　　　Step3: 余った領域がなくなるまで繰り返す。

つまり、長辺から「短辺の長さの正方形」を切り出していき、残った長方形で同じことを繰り返す、という作業です。このとき、最後に切り出した正方形の一辺が、そのまま最大公約数 になります。

例1｜最大公約数6である 78 と 30 の場合

それでは、78 と 30 で実際にやってみましょう。

図1-1 で「長辺（78）÷ 短辺（30）」を行うと、30×30 の正方形が2つできます。これは、短辺の長さの正方形を切り出す作業そのものです。残った 18×30 が「余り」で、次はこの余りを使います。

図1-2 では、長辺と短辺が入れ替わります。図1-1で短辺だった「30」が、今度は長辺として扱われるわけです。こうして、以後は長辺と短辺が交互に入れ替わっていきます。

図1-3 も、これまでと同様に行います。

そして 図1-4 で、ようやく余りがなくなりました。12×6 の長方形が、6×6 の正方形2つでぴったり埋まっています。このときの短辺「6」が、最大公約数です。

図1-4で、ようやく余りがなりました。この時の短辺が最大公約数（６）となるわけです。

Step	式	できた正方形	余り
図1-1	78 ＝ 30×2 ＋ 18	30×30 が2つ	18×30
図1-2	30 ＝ 18×1 ＋ 12	18×18 が1つ	18×12
図1-3	18 ＝ 12×1 ＋ 6	12×12 が1つ	6×12
図1-4	12 ＝ 6×2	6×6 が2つ	なし

長方形が転がって転がって、最後に正方形で敷き詰められる——そんなイメージです。ごつごつした石が川の流れの中で転がり、だんだん丸くなっていく感じ、と言ってもいいかもしれません。例えとしては少し強引ですが、「余りを残さず敷き詰められる正方形の大きさ＝最大公約数」 という感覚はつかんでいただけるのではないでしょうか。

例2｜互いに素である 12 と 7 の場合

次は、互いに素（最大公約数が1）の場合はどうなるかを見てみましょう。

図2-1 では、7×7 の正方形が1つでき、余りは 5×7。

図2-2 では、5×5 の正方形が1つでき、余りは 5×2。

図2-3 では、2×2 の正方形が2つでき、余りは 1×2。

そして 図2-4 で、1×1 の正方形2つでぴったり埋まりました。最終的に短辺が「1」となり、最大公約数が1であること が図で示されました。

Step	式	できた正方形	余り
図2-1	12 ＝ 7×1 ＋ 5	7×7 が1つ	5×7
図2-2	7 ＝ 5×1 ＋ 2	5×5 が1つ	5×2
図2-3	5 ＝ 2×2 ＋ 1	2×2 が2つ	1×2
図2-4	2 ＝ 1×2	1×1 が2つ	なし