ユークリッドの互除法とは
整数の分野では多く目にするこの「ユークリッドの互除法」ですが、まずこれがなんなのかを説明しておきましょう。ユークリッドの互除法とは
自然数\(a,b\)に対し\(a\)を\(b\)で割った余りを\(r\)とするとき、
\(a\)と\(b\)の最大公約数＝\(b\)と\(r\)の最大公約数
が成り立つ
というものです。何がうれしいのか最初はわからないと思います。ですが整数の分野をマスターしていくうえでこの「最大公約数」というのはキーワードになってきます。なのでそれがかかわってくる法則は大事になっていくわけです。
さて、式だけを出してもよくわからないと思いますので簡単に例を挙げていきましょう。
いったん広告の時間です。
ユークリッドの互除法を使ってみる
例えば１０８と５６の最大公約数を求めてみましょう。自力でやろうと思えばできますが簡単にできたほうがいいですよね。
まずは１０８を５６で割ってみます。
$$108=56\times 1+52$$
こうなりました。するとユークリッドの互除法から１０８と５６の最大公約数は５６と５２の最大公約数と等しいので、次は５6と５２の最大公約数を求めればいいことになります。では
$$56=52\times 1+4$$
をすれば次は５２と４の最大公約数を求めればよいことになります。もうわかりましたね。
$$52=4\times 13+0$$
となり割り切れますので、もちろん５２と４の最大公約数は４です。
というわけでずーっと階段を降りるように簡単な数字になっていき最終的には
１０８と５６の最大公約数は４
とわかりました。自分でそれぞれの数字をどんどん割るよりは簡単ですよね。
これぐらいだったら・・・と思う人は
245643と263462の最大公約数を求めよ
と言われてもまだそれぞれの数字を割って公約数を探すでしょうか。さすがに嫌ですよね。ですが互除法ならいけそうな気がしませんか？
いったん広告の時間です。
ユークリッドの互除法はこれだけか
ここまで見てきて「ユークリッドの互除法ってこれにしか使えないの？」と思い、覚えるのをやめた人がいたらこの先の未来の話を聞けば覚える気になってくれるはずです。
実はこのユークリッドの互除法は２つの自然数の最大公約数を求めるという単純なものなのですが、応用範囲が広いです。
この先出てくる「不定方程式」では必須のスキルになります。脅しではありませんが覚えてないと話になりません。
また最大公約数を求めてからその最大公約数を使って問題が展開されることもしばしばです。なので最大公約数を求められないと問題の続きができません。
このように最大公約数自体が広い範囲で応用が利く概念なのです。それに伴ってユークリッドの互除法はかなりの有用性を持ちます。
終わりに
ユークリッドの互除法は整数の問題では欠かせないスキルであり武器です。これ単体の問題はほとんどありませんが、使わなければ先に進めない問題は山ほどあります。一度使い方を押さえれば難しくはありません。
ではまた。
コメント