2024年11月02日くいなちゃん


本記事は「くいなちゃん数学」基本編の補足資料です。 ユークリッドの互除法を証明します。

1ユークリッドの互除法

ユークリッドの互除法ごじょほう」とは、第3話で説明した通り、2つの正の整数(ただし)の最大公約数が簡単に求められる方法です。
で割った商を、余りをとして、「()」としたときに、「」が成り立つことを利用します。 ですので、元よりも小さい数の最大公約数を求める問題に置き換えられます。
さらにこの置き換えを繰り返すことで最終的に余りになって、ある整数との最大公約数を求める問題に行き着きます。 ここで、との最大公約数はなので、結局の最大公約数はが答えとなります。
第3話に、ユークリッドの互除法を使った例を掲載しています。

2ユークリッドの互除法の証明

それでは、ユークリッドの互除法で唯一自明でない部分の「」を証明しましょう。
前述の通り、を満たす正の整数について、で割った商を、余りをとして、「()」と表されます。
式を変形して、「」となります。 ここでの倍数で、の倍数なので、倍数同士を足した「()」もの倍数です。 よって、の約数です。
一方、の約数です。 よって、の公約数となりますが、「の公約数」は「の最大公約数」以下なので、「」が成り立ちます。
同様に、「」より、の倍数で、の倍数なので、倍数同士を足した「()」もの倍数です。 よって、の約数です。
一方、の約数です。 よって、の公約数となりますが、「の公約数」は「の最大公約数」以下なので、「」が成り立ちます。
」と「」がいえましたので、「」が成り立ちます。 (証明終)
1730487174jaf