ユークリッドの互除法は、2つの自然数a,b (a>b)に対して、
aをbで割った商がqで、余りがrのとき、つまり
a = bq + r ・・・①
のときに、gcd(a,b) = gcd(b,r)が成立すること。
※gcd(a,b)はaとbの最大公約数を表す。
証明がわかりづらいので、自分なりにわかりやすく証明できればと思う。
証明）
(i) まず、gcd(b,r) =Gで、b = b'G, r = r'Gとおくと、①は
a = b'Gq + r'G = ( b'q +r' )G
と書ける。つまり、aも公約数にGを持つことになる。
従って、aとbは共に約数としてGを持つことになる。
よって、 g.c.d(b,r) ≦ g.c.d(a,b)であることがいえる。・・・②
(ii) 次に、①式を次のように変形する。
r = a - bq
ここで、gcd(a,b) =G'で、a = a'G', b = b'G'とおくと、②は
r = a'G' - b'G'q = ( a' +b'q )G
と書ける。つまり、rも公約数にG'を持つことになる。
従って、rとbは共に約数としてG'を持つことになる。
よって、 g.c.d(a,b) ≦ g.c.d(b,r)であることがいえる。・・・③
②、③より、 g.c.d(b,r) ≦ g.c.d(a,b) かつ g.c.d(a,b) ≦ g.c.d(b,r)であるから、
g.c.d(a,b) = g.c.d(b,r)が示せた。
この辺りは、概念がわかりづらいので、
文字を上手く置き換えて理解できるといいのかなと思った。