ユークリッドの互除法（ごじょほう）とは，大きな数たちの最大公約数を素早く計算する方法です。
この記事では，ユークリッドの互除法を用いた問題を解説しますのでぜひ読んでみてください！
ユークリッドの互除法
今回はユークリッドの互除法を活用する問題です！
みなさんは、最大公約数を求める際に、一般的には素因数分解をしますよね？
もちろんその解き方でも解けるのですが、数が大きくなればなるほど、素因数分解が面倒になってきます。また、簡単な素数を因数にもたない数の場合、素因数分解をすることが困難なのです。
ここで活用できる方法が、ユークリッドの互除法というものです。この方法の証明は今回は省くことにし、計算方法に焦点を絞って解説していきます。
重要な性質
割り算の等式：\(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\) になるまで行い、その時の割り算の割る数が最大公約数になると言えますね。大きな数の最大公約数を求めたいときは、ぜひ活用してみましょう。
おわりに
さいごまで読んでいただきありがとうございました！
- 大学受験数学で困っている方
- 公務員試験の数学で困っている方
- 統計学（統計検定）の勉強で困っている方
個人家庭教師やってるので、ぜひコメントやXでご連絡ください。（Xはこちら）
私自身、数学に関して順風満帆に理解できてきたわけではありませんでした。
周りを見渡せば数学の天才がゴロゴロいて、そんな人たちに比べれば私は足元にも及びませんでした。
だからこそ、わからない、理解できない方の気持ちを少しはわかってあげられると自負しております。
数学に困っている方の一助になれれば幸いです。
ご連絡お待ちしております。
質問や感想はコメントへ！