基本編 付録
ユークリッドの互除法の証明

「ユークリッドの互除法ごじょほう」とは、第3話で説明した通り、2つの正の整数(ただし)の最大公約数が簡単に求められる方法です。

をで割った商を、余りをとして、「()」としたときに、「」が成り立つことを利用します。 ですので、元よりも小さい数の最大公約数を求める問題に置き換えられます。

さらにこの置き換えを繰り返すことで最終的に余りがになって、ある整数ととの最大公約数を求める問題に行き着きます。 ここで、との最大公約数はなので、結局との最大公約数はが答えとなります。

第3話に、ユークリッドの互除法を使った例を掲載しています。

それでは、ユークリッドの互除法で唯一自明でない部分の「」を証明しましょう。

前述の通り、を満たす正の整数について、をで割った商を、余りをとして、「()」と表されます。

式を変形して、「」となります。 ここではの倍数で、もの倍数なので、倍数同士を足した「()」もの倍数です。 よって、はの約数です。

一方、はの約数です。 よって、はとの公約数となりますが、「との公約数」は「との最大公約数」以下なので、「」が成り立ちます。

同様に、「」より、はの倍数で、もの倍数なので、倍数同士を足した「()」もの倍数です。 よって、はの約数です。

一方、はの約数です。 よって、はとの公約数となりますが、「との公約数」は「との最大公約数」以下なので、「」が成り立ちます。

「」と「」がいえましたので、「」が成り立ちます。 (証明終)