数理論 へ戻る
ユークリッドの互除法の原理 ：
全体集合を自然数とする。
Ａ を Ｂ で割った余りを Ｒ とする。
Ａ と Ｂ の最大公約数は、 Ｂ と Ｒ の最大公約数に等しい。
全体集合を自然数とする。
Ａ を Ｂ で割った余りを Ｒ とする。
Ａ と Ｂ の最大公約数は、 Ｂ と Ｒ の最大公約数に等しい。
（ 証 明 ）
-
Ａ を Ｂ （ Ａ ＞ Ｂ ） で割った余りを Ｒ とすると、
Ａ ＝ Ｗ×Ｂ ＋ Ｒ （ Ｂ ＞ Ｒ ） ・ ・ ・ ①
Ａ と Ｂ の最大公約数を Ｇ とすると、
Ａ ＝ Ｇ×ａ Ｂ ＝ Ｇ×ｂ （ ａ と ｂ は互いに素 ） ・ ・ ・ ②
② を ① に代入すると、 Ｇ（ ａ－Ｗｂ ） ＝ Ｒ
ｒ ＝ ａ－Ｗｂ と置くと、 Ｒ ＝ Ｇ×ｒ
したがって、 Ｇ は Ｂ と Ｒ の約数である。
Ｂ と Ｒ の最大公約数を Ｇmax とすると、
Ｇ ≦ Ｇmax ・ ・ ・ ③
Ｂ ＝ Ｇmax×ｐ Ｒ ＝ Ｇmax×ｑ （ ｐ と ｑ は互いに素 ） ・ ・ ・ ④
④ を ① に代入すると、 Ａ ＝ Ｇmax（ Ｗｐ＋ｑ ）
ｓ ＝ Ｗｐ＋ｑ と置くと、 Ａ ＝ Ｇmax×ｓ
したがって、 Ｇmax は Ｂ と Ａ の約数である。
したがって、
Ｇmax ≦ Ｇ ・ ・ ・ ⑤
③ と ⑤ より、 Ｇmax ＝ Ｇ
したがって、 Ｂ と Ｒ の最大公約数は Ｇmax である。
（ 証明終わり ）
※ 参考 ： プログラミング ＞ 最小公倍数のプログラムの作り方
十進BASIC ＞ 十進BASIC＿プログラミング ＞ ユークリッドの互除法のプログラム
問題 １ ：
-
a と b が互いに素ならば、 7a + 16b と 3a + 7b も互いに素であることを証明せよ。
-
7a + 16b と 3a + 7b の最大公約数が １ であることを証明すればいい。
7a + 16b = 2 (3a+7b) + (a+2b) なので、
7a + 16b と 3a + 7b の最大公約数は、 3a + 7b と a + 2b の最大公約数に等しい。
3a + 7b = 3 (a+2b) + b なので、
3a + 7b と a + 2b の最大公約数は、 a + 2b と b の最大公約数に等しい。
a + 2b = 2b + a なので、
a + 2b と b の最大公約数は、 b と a の最大公約数に等しい。
a と b が互いに素のとき、 a と b の最大公約数は １ である。
よって、 7a+16b と 3a+7b の最大公約数は １ である。
-
10 n ＋ ２ と 11 n ＋ ３ の最大公約数が ８ になる、 50以下の自然数 n を求めなさい。（ ６個あります ）
-
ユークリッドの互除法 ：
（ 11 n ＋ ３ ） － （ 10 n ＋ ２ ） ＝→ n ＋ １
（ 10 n ＋ ２ ） － （ n ＋ １ ） × 10 ＝→ －８
よって、 10 n ＋ ２ と 11 n ＋ ３ の最大公約数は （ n ＋ １ ） と ８ の
最大公約数に等しい。
（ n ＋ １ ） と ８ の最大公約数が ８ になるためには、
２ ≦ n ＋ １ ≦ 51 の範囲で、 n ＋ １ ＝ 8 or 16 or 24 or 32 or 40 or 48
を n が満たすことである。 したがって、 答えは次の６個になる。
７， 15， 23， 31， 39， 47
-
15721 と 12877 の最大公約数を求めよ。
-
15721 － 12877 × １ ＝ 2844
15721 と 12877 の最大公約数は 12877 と 2844 の最大公約数に等しい。
12877 － 2844 × ４ ＝ 1501
12877 と 2844 の最大公約数は 2844 と 1501 の最大公約数に等しい。
2844 － 1501 × １ ＝ 1343
12877 と 2844 の最大公約数は 1501 と 1343 の最大公約数に等しい。
1501 － 1343 × １ ＝ 158
1501 と 1343 の最大公約数は 1343 と 158 の最大公約数に等しい。
1343 － 158 × ８ ＝ 79
1343 と 158 の最大公約数は 158 と 79 の最大公約数に等しい。
158 － 79 × ２ ＝ ０
158 と 79 の最大公約は 79 である。
したがって、 答えは 79 である。
つまり、
MOD(15721,12877) ＝ 2844 ＊ a/b ＝ INT(a,b) ＋ MOD(a,b)
MOD(12877,2844) ＝ 1501
MOD(2844,1501) ＝ 1343
MOD(1501,1343) ＝ 158
MOD(1343,158) ＝ 79
MOD(158,79) ＝ 0
参考：
十進BASIC ＞ 十進BASIC＿プログラミング ＞ ユークリッドの互除法のプログラム