今、正の整数ｍとｎを考える。(ただし、m＜ｎとする。)
ｎをｍで割った余りをｒとする。
ユークリッドの互助法とは次のようにしてｍとｎの最大公約数を求める方法のことである。
ｍ、ｎ、ｒについて次のような操作を行う。
１)ｒ＝０の時、
ｍが最大公約数。
２)r≠０の時、
新しいｎ＝(これまでの)ｍ
新しいｍ＝(今の余り)ｒ
としてこれを繰り返す。
以上の操作を行うことにより、ｎとｍの最大公約数が求まる。
ところで、この方法は次のような事実をその根拠としている。
ｎとｍの最大公約数は、ｍとｒの最大公約数に等しい。…(＊)
(＊)を証明しなさい。
