【基本】ユークリッドの互除法の使い方
【導入】ユークリッドの互除法 で書いた通り、「2つの大きな数の最大公約数を求める」には、結構計算が大変なんですよね。「$1649$と$221$の最大公約数は？」という問題を考えてみましょう。2で割れるか、3で割れるか、と小さい数字から順番に割っていってもいいのですが、それだと時間がかかってしまいます。
「ユークリッドの互除法」というのは、このように「数が大きすぎて、最大公約数を求めるのが大変だ」というときに使える技なんですね。この技さえ知っていれば、大きな数がきても、計算量はグッと少なくなります。
詳しい原理については、別ページの【標準】ユークリッドの互除法（近日公開）で説明するとして、このページでは、どのような発想を使っているのか、どうやって計算するのか、を説明していきます。
「ユークリッドの互除法」の発想
上に書いた問題「$1649$と$221$の最大公約数」について考えてみます。この最大公約数をGとおくと、$1649$ は $G$ で割り切れるし $221$ も $G$ で割り切れますよね。ということは、この2つの差「$1649-221$」も$G$ で割り切れることがわかります。
これをもっと進めていけば、$1649-221\times 2$ も $1649-221\times 3$ も $1649-221\times 4$ だって、$G$で割り切れるはずです。
「$1649$から$221$を何度も引く」を進めていくと、割り算にたどり着きます。割り算をすれば、\[ 1649 = 221 \times 7 + 102 \]と書けることがわかります。この式で、$G$で割り切れるものに注目してみましょう。
$1649$ も $221$ も $G$ で割り切れるので、余りである$102$ も$G$で割り切れないといけません。
このような流れから、「割った余りとの最大公約数を考えればいいのではないか」という発想が生まれてきます。余りの方が小さい数になるので、考えやすくなりますよね。実際、$1649$と$221$の最大公約数は、$221$と$102$ ($1649$を$221$で割った余り) の最大公約数と同じになります。より厳密な説明は、【標準】ユークリッドの互除法（近日公開）ですることにして、ここでは、「割った余りとの最大公約数を考えればいいんだな」ということだけおさえておけばOKです。
「ユークリッドの互除法」の具体的な計算方法
ここでも、「$1649$と$221$の最大公約数」について考えていきます。
先ほども書いた通り、「$1649$と$221$の最大公約数」を考えるには、「割った余りとの最大公約数を考えればいい」んでしたね。$1649$を$221$で割った余りは、計算すると$102$だとわかるので、「$221$と$102$の最大公約数」を考えればいいわけです。
実は、「ユークリッドの互除法」は繰り返し使うことができます。つまり、「$221$と$102$の最大公約数」を考えるには、「$102$と、”$221$を$102$で割った数”との最大公約数」を考えればOKです。
$221$を$102$で割った余りを計算すると$17$だとわかるので、「$102$と$17$の最大公約数」を考えればいいことが分かります。
さらにさらに、もう一度繰り返してみます。今度は、$102$を$17$で割った余りを考えてみますが、今回は割り切れてしまいます。つまり、「$102$と$17$の最大公約数」は$17$であることがわかります。
これを逆にたどっていくと、「$221$と$102$の最大公約数」も$17$だし、「$1649$と$221$の最大公約数」も$17$である、ということがわかるんですね。
小さい数字から順番に割り切れるかどうかチェックすることなく、最大公約数を求めることができます。「余り」に注目すればいいので、「ユークリッドの互除法」は、特に大きな数の最大公約数を考える場合に、大きな威力を発揮します。