ユークリッドの互除法
\(2\) つの整数の最大公約数を求めるための方法として、ユークリッドの互除法があります。
ユークリッドは紀元 \(3\) 世紀頃の古代ギリシャの数学者です。エウクレイデスとも呼ばれます。
※ラテン語読みに近いのがエウクレイデス、英語読みに近いのがユークリッド
例
\(793\) と \(377\) の最大公約数を求めなさい。
解答
一見して公約数が見えないとき、ユークリッドの互除法を使うと良いです。
ユークリッドの互除法の手順を以下で示します！
まず \(2\) つの数でわり算をし、あまりを求めます。
\(793÷377=2 \cdots 39\)
次に、「割る数\(÷\) あまり」を計算し、あまりを求めます。
これを、割り切れるまで繰り返したときの、割る数が最大公約数です。
\(793÷\)\(377\)\(=2 \cdots \)\(39\)
\(377\)\(÷\)\(39\)\(=9 \cdots\)\( 26\)
\(39\)\(÷\)\(26\)\(=1 \cdots\)\( 13\)
\(26\)\(÷\)\(13\)\(=2 \)
より、\(13\) が 最大公約数です。
\(793\) と \(377\) の最大公約数は \(13\) と求まりました。
公約数の性質
ユークリッドの互除法は、以下のような数の性質を利用したものです。
\(A\) と \(B\) の最大公約数が \(M\) ならば、
\(B\) と \(|A-kB|\) の最大公約数も \(M\) である。
ただし、\(k\) は整数
一読してもピンとこないでしょうから、下の線分図で理解しましょう。
\(793\) と \(377\) の最大公約数を \(M\) とします。
どちらも \(M\) の倍数なので、下図のようになります。
※\(M\) の値は不明ですし、図の比率などは不正確です。
\(A-B=793-377\) が \(M\) の倍数であることがわかりますし、
\(A-2B=793-377×2\) も \(M\) の倍数であることが見て取れます。
さらに、
\(B=377\) と \(A-2B=39\) においても、同様のことが成り立つので、
\(377-39k\) を求めていきます。
これを最後までつきつめるのがユークリッドの互除法です。
しかし・・・
最後までやらなくとも、最大公約数が見つかればそれで良いってこと、あるわけです。
公約数の性質を利用して最大公約数を見つける
ユークリッドの互除法を最後までやることが目的ということはほぼないでしょう。
最大公約数を見つけるために、ユークリッドの互除法を使うだけですからね。
こんなやり方がおススメです。
先ほどの例
\(793\) と \(377\) の最大公約数を求めなさい。
解答
\(793\) と \(377\) の最大公約数は、\(793-377k\) の約数である。
\(k=2\) のとき、
\(793-377×2=39\)
よって、求める最大公約数は \(39\) の約数なので、
\(1,3,13,39\) のどれかである。
\(377\) は \(3\) を素因数に持たないので、\(3,39\) は除外される。
※\(377\) が \(3\) で割り切れないということです！
より、\(1,13\) のどちらかである。
間違いなく \(13\) であろうことが予想される中、
\(377÷13=29\)
と正しいことが確かめられます。
より、最大公約数は \(13\) です。
※\(793\) が \(13\) で割り切れることを確かめる必要はありません。
\(793=377×2+39\)
なので、\(377\) を確かめるだけでＯＫです。
例題１
\(323\) と \(357\) の最大公約数を求めなさい。
解説
\(357-323=34\)
より、\(34\) の約数 \(1,2,17,34\) が最大公約数の候補です。
明らかに奇数なので、\(1,17\) のいずれかです。
間違いなく \(17\) であろうことが予想される中、
\(323÷17=19\)
と正しいことが確かめられます。
より、最大公約数は \(17\) です。
例題２
\(819\) と \(1176\) の最大公約数を求めなさい。
解説
\(1176-819=357\)
より、\(357\) の約数が最大公約数の候補です。
\(357=7×51\)
はすぐわかりますね。
よって、\(357=7×3×17\)
を利用して探し出すのもありです。
しかし、ここはもう一段階差を取りましょう。
\(819-357×2=105\)
より、\(105\) の約数が最大公約数の候補です。
\(105\) の約数から探すか、さらにもう一段階差を取るか。
それはお好みでどうぞ、となります。
さらにもう一段階いくならば、
\(357-105×3=42\)
より、\(42\) の約数 \(1,2,3,6,7,14,21,42\) が最大公約数の候補です。
\(819\) を割り切る数は奇数なので、そこから探すと \(21\) が見つかります。
より、最大公約数は \(21\) です。
※もちろん最後の最後までユークリッドの互除法を用いてもＯＫです。
\(1176÷\)\(819\)\(=1 \cdots \)\(357\)
\(819\)\(÷\)\(357\)\(=2 \cdots\)\(105\)
\(357\)\(÷\)\(105\)\(=3 \cdots\)\(42\)
\(105\)\(÷\)\(42\)\(=2 \cdots\)\(21\)
\(42\)\(÷\)\(21\)\(=2 \)