【整数の性質】『ユークリッドの互除法』大きい自然数の最大公約数

ユークリッドの互除法（ごじょほう）とは，大きな数たちの最大公約数を素早く計算する方法です。

この記事では，ユークリッドの互除法を用いた問題を解説しますのでぜひ読んでみてください！

ユークリッドの互除法

今回はユークリッドの互除法を活用する問題です！

みなさんは、最大公約数を求める際に、一般的には素因数分解をしますよね？

もちろんその解き方でも解けるのですが、数が大きくなればなるほど、素因数分解が面倒になってきます。また、簡単な素数を因数にもたない数の場合、素因数分解をすることが困難なのです。

ここで活用できる方法が、ユークリッドの互除法というものです。この方法の証明は今回は省くことにし、計算方法に焦点を絞って解説していきます。

ユークリッドの互助法の問題

$841$ と $377$ の最大公約数を求めなさい。

答え

$29$

解説

まず、この $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$ になるまで行い、その時の割り算の割る数が最大公約数になると言えますね。大きな数の最大公約数を求めたいときは、ぜひ活用してみましょう。

おわりに