受験数学

ユークリッドの互除法をなぜ学ぶのか?

2020年1月27日

ちなみに答えは1ではありません!

ナナナイル
きちんとした数が出てきます
メメメイナ
でも2でも割り切れないし3でも割り切れないし・・・なかなか見つかりません!

そんなあなたにユークリッドの互除法というツールがあるので紹介します。

ユークリッドの互除法は数学Aの整数の分野で学びます

12と18の最大公約数は?

と言われたら、すだれ算を用いて6とすぐにわかると思います。

しかし、先ほどの12345654321と1234321の最大公約数は?などと言われたらお手上げですよね笑

ナナナイル
もちろん一瞬で出せるすごい方もいらっしゃいますが、ここでは一般的に難しいとしますね

では12と18の最大公約数を別の方法で考えます。

ナナナイル
ひょっとして18を12で割ったら割り切れる?これってどうやったら確かめられる?
メメメイナ
筆算してあまりが0だったらOKです!

18=12×1+6・・・①

残念ながら割り切れませんでした。6あまります。

ナナナイル
では、その6って、ひょっとしたら12と18の最大公約数ではないか?ってどうやったら確かめられる?
メメメイナ
18と12がそれぞれ6で割り切れることを確かめます。でも①より12が6で割り切れれば18も自動的に6で割り切れると断言できます

では12=6×2+0より、最大公約数は6ですね。

  • 厳密な証明は文字式を用いますが、これが互除法のアルゴリズムの考え方の基本的というよりかは、目標に沿った理解と言って良いかと思います。
  • 目標は最大公約数を求めることだからです

ユークリッドの互除法はどんなことに応用できるか?

  • 互いに素を示す時に役立つ
  • 不定方程式の一種を解くために効果を発揮する

などなど、これは一例にすぎませんが、互除法を習いたての人は上の2つを理解できたらまずOKです!

ナナナイル
nを整数とする時、nとn+1は互いに素(最大公約数が1)だと証明せよ!ってできる?
メメメイナ
当たり前のように聞こえますが、やはり互除法を一回使っておしまいですね笑

結構、こう言った変形や発送は数検でも受験でも使うので、できるようにしていただけると良いなと思います。

ナナナイル
軽くて(物理的に)いっぱい整数問題を見たい!解きたい!って方はおすすめです
メメメイナ
この方のシリーズは説明がかみ砕いてされていて読者目線で良いですよね!
  • この記事を書いた人
  • 最新記事

nananairu

英検1級を目指す数検1級と漢検1級合格者の現役数学教師。 ジムに通ってマッチョを目指しています。 数検1級は高校生の時に合格しました! 合格のコツや数学の面白さをお伝えして参ります!

-受験数学
-, ,

Copyright© 数検1級合格対策 , 2020 All Rights Reserved Powered by AFFINGER5.