「高校数学の知識庫」を今より10倍活用する方法

ユークリッドの互除法とその先

スポンサーリンク

 


 

 

こんにちは。 da Vinch (@mathsouko_vinch)です。

 

 

ユークリッドの互除法とは

整数の分野では多く目にするこの「ユークリッドの互除法」ですが、まずこれがなんなのかを説明しておきましょう。ユークリッドの互除法とは

 

自然数\(a,b\)に対し\(a\)を\(b\)で割った余りを\(r\)とするとき、

\(a\)と\(b\)の最大公約数=\(b\)と\(r\)の最大公約数

が成り立つ

 

というものです。何がうれしいのか最初はわからないと思います。ですが整数の分野をマスターしていくうえでこの「最大公約数」というのはキーワードになってきます。なのでそれがかかわってくる法則は大事になっていくわけです。

さて、式だけを出してもよくわからないと思いますので簡単に例を挙げていきましょう。

ユークリッドの互除法を使ってみる

例えば108と56の最大公約数を求めてみましょう。自力でやろうと思えばできますが簡単にできたほうがいいですよね。

まずは108を56で割ってみます。

$$108=56\times 1+52$$

こうなりました。するとユークリッドの互除法から108と56の最大公約数は56と52の最大公約数と等しいので、次は56と52の最大公約数を求めればいいことになります。では

$$56=52\times 1+4$$

をすれば次は52と4の最大公約数を求めればよいことになります。もうわかりましたね。

$$52=4\times 13+0$$

となり割り切れますので、もちろん52と4の最大公約数は4です。

というわけでずーっと階段を降りるように簡単な数字になっていき最終的には

108と56の最大公約数は4

とわかりました。自分でそれぞれの数字をどんどん割るよりは簡単ですよね。

これぐらいだったら・・・と思う人は

245643と263462の最大公約数を求めよ

と言われてもまだそれぞれの数字を割って公約数を探すでしょうか。さすがに嫌ですよね。ですが互除法ならいけそうな気がしませんか?

ユークリッドの互除法はこれだけか

ここまで見てきて「ユークリッドの互除法ってこれにしか使えないの?」と思い、覚えるのをやめた人がいたらこの先の未来の話を聞けば覚える気になってくれるはずです。

実はこのユークリッドの互除法は2つの自然数の最大公約数を求めるという単純なものなのですが、応用範囲が広いです。

この先出てくる「不定方程式」では必須のスキルになります。脅しではありませんが覚えてないと話になりません。

また最大公約数を求めてからその最大公約数を使って問題が展開されることもしばしばです。なので最大公約数を求められないと問題の続きができません。

このように最大公約数自体が広い範囲で応用が利く概念なのです。それに伴ってユークリッドの互除法はかなりの有用性を持ちます。

終わりに

ユークリッドの互除法は整数の問題では欠かせないスキルであり武器です。これ単体の問題はほとんどありませんが、使わなければ先に進めない問題は山ほどあります。一度使い方を押さえれば難しくはありません。

ではまた。

スポンサーリンク
整数の性質
スポンサーリンク
高校数学の知識庫

コメント

タイトルとURLをコピーしました