書いた通り、「2つの大きな数の最大公約数を求める」には、結構計算が大変なんですよね。最大公約数は?」という問題を考えてみましょう。2で割れるか、3で割れるか、と小さい数字から順番に割っていってもいいのですが、それだと時間がかかってしまいます。ユークリッドの互除法は、「数が大きすぎて、最大公約数を求めるのが大変だ」というときに使える技です。この技を知っていれば、大きな数がきても、最大公約数を求めるための計算量はグッと少なくなります。詳しい原理については、別ページの【標準】ユークリッドの互除法の原理で説明するとして、このページでは、どのような発想を使っているのか、どうやって計算するのか、を説明していきます。上にも書きましたが、次の問題を考えてみましょう。最大公約数を求めなさい。割り切れることがわかります。何度も引く」を進めていくと、割り算にたどり着きます。\]と書けることがわかります。割り切れるものに注目してみましょう。割り切れないといけません。このような流れから、「割った余りとの最大公約数を考えればいいのではないか」という発想が生まれてきます。余りの方が小さい数になるので、考えやすくなりますよね。最大公約数と同じになります。厳密な証明は、【標準】ユークリッドの互除法の原理ですることにして、ここでは、「割った余りとの最大公約数を考えればいいんだな」ということだけおさえておけばOKです。最大公約数」について考えていきます。最大公約数」を考えるには、割った余りとの最大公約数を考えればいいんでしたね。最大公約数」を考えればいいわけです。実は、「ユークリッドの互除法」は繰り返し使うことができます。割った余り”との最大公約数」を考えればOKなんです。$17$の最大公約数」を考えればいい、ということです。一度繰り返してみます。割った余りを考えてみます。すると、今回は割り切れてしまいます。ある、ということなんですね。これが、ユークリッドの互除法の使い方です。小さい数字から順番に割り切れるかどうかチェックすることなく、最大公約数を求めることができます。「余り」に注目するので、「ユークリッドの互除法」は、大きな数の最大公約数を考える場合に、大きな威力を発揮することがわかります。おわりにここでは、ユークリッドの互除法に関する考え方と、具体的な計算方法を紹介しました。「割り算をして、余りとの最大公約数を考えていく」方法を繰り返し使えば、最大公約数が求められます。このユークリッドの互除法に関する数学的な証明は、【標準】ユークリッドの互除法の原理でとりあげているので、そちらもぜひチェックしておきましょう。