【基本】ユークリッドの互除法の使い方 | なかけんの数学ノートこの最大公約数を G とおくと、$1649$ は G で割り切れるし、 $221$ も G で割り切れますよね。ということは、この2つの差「$1649-221$」も $G$ で割り切れることがわかります。 これをもっと進めていけば、$1649-221\times 2$ も $1649-221\times 3$ も $1649-221\times 4$ だって、$G$ で割り切れるはずです。 「$1649$ から $221$ を何度も引く」を進めていくと、割り算にたどり着きます。割り算をすると「$7$ 余り $102$」と計算できるので、\[ 1649 -221 \times 7 = 102 \]と書けることがわかります。この式で、 G で割り切れるものに注目してみましょう。 $1649$ も $221$ も G で割り切れるので、余りである $102$ も G で割り切れないといけません。
