ユークリッドの互除法（ごじょほう）とは，大きな数たちの最大公約数を素早く計算する方法です。
この記事では，ユークリッドの互除法を用いた問題を解説しますのでぜひ読んでみてください！
ユークリッドの互除法
今回はユークリッドの互除法を活用する問題です！
みなさんは、最大公約数を求める際に、一般的には素因数分解をしますよね？
もちろんその解き方でも解けるのですが、数が大きくなればなるほど、素因数分解が面倒になってきます。また、簡単な素数を因数にもたない数の場合、素因数分解をすることが困難なのです。
ここで活用できる方法が、ユークリッドの互除法というものです。この方法の証明は今回は省くことにし、計算方法に焦点を絞って解説していきます。
重要な性質
割り算の等式：\(a=bq+r\) において、
「\(a\) と \(b\) の最大公約数」＝「\(b\) と \(r\) の最大公約数」
ユークリッドの互助法の問題
\(841\) と \(377\) の最大公約数を求めなさい。
理系大学レベル別おすすめ数学テキスト
＞＞【理系大学向け】選ぶ時間を短縮！レベル別おすすめの数学参考書
答え
\(29\)
解説
今回は、「答案の例」ではなく、「答え」という形で表現しました。
おそらくこの問題では、途中経過を書かせるような出題のされ方はしないと思います。ユークリッドの互除法を使って最大公約数を求め、あとはそれを答案に書くだけの問題ですね。
まず、この \(2\) 数を見たとき、素因数分解がかなりしにくいと思います。数が大きくなればなるほど、分解の作業に手間がかかるわけですね。ここで活用できるのが、ユークリッドの互除法です。
さて、前述した通り、ユークリッドの互除法の証明は今回は省き、実際の使い方を示していきたいと思います。ユークリッドの互除法を端的に言葉で説明しようとした場合、以下のようになります。
＜ユークリッドの互除法＞
ある \(2\) 数の割り算を考えたとき、割る数と割られる数の最大公約数は、割る数と余りの最大公約数に等しい。
例えば、今回の場合、\(841\) と \(377\) の最大公約数を問われているので、まず \(841\) を \(377\) で割った結果を式に表してみます。
\(841=377 \times 2+87\)
さて、ここでユークリッドの互除法の考えを使って最大公約数を求めていきます。つまり、今回の割る数は \(377\) 、余りは \(87\) なので、当初の最大公約数を求めることは、この \(2\) 数の最大公約数を求めることに等しいわけです。
よって、これらの数でもう一度割り算を行ってみます。
\(377=87 \times 4+29\)
ここでもまた、今度は \(87\) と \(29\) の最大公約数を求めれば、もともとの \(2\) 数の最大公約数を求めることに等しくなるわけです。よって、同様に式を作ると、
\(87=29 \times 3+0\)
となります。ここで、余りが \(0\) になってしまいましたね。この時点でユークリッドの互除法による割り算は終了です。 \(87\) が \(29\) の倍数であることがわかったため、必然的にこれらの最大公約数は \(29\) であることが判明しました。
これにより、もともとの \(841\) と \(377\) の最大公約数もまた、 \(29\) であることがわかりました。
ユークリッドの互除法は、最後の余りが \(0\) になるまで行い、その時の割り算の割る数が最大公約数になると言えますね。大きな数の最大公約数を求めたいときは、ぜひ活用してみましょう。
おわりに
さいごまで記事を読んでいただきありがとうございました！
数学は、時間をかけて勉強すれば誰でも成績を上げられます！
しかし、時間には限りがあります。
アプリや塾/家庭講師など自分に合ったサポートを取り入れることで、限りある時間を効率的に使うことができます。
▼自走して学習が進められる人
日々の悩みを解決できるコーチング面談や日々の学習計画を見直せるサポートがおすすめです。
▼自走して学習が進められない人
毎週講師による授業をしっかり受けて、宿題を設定してもらうサポートがおすすめです。
コメントはお気軽に♪