質問＜２３７１＞２００５／５／２１
from=ロバ
「ユークリッドの互除法」

a.b∈Nに対し、aをbで割ったあまりをrとする。次を示せ。
①r=0⇒(a,b）=b
②r≧0⇒(a,b）=(b,r）

★希望★完全解答★

お便り２００５／６／１６
from=KINO

(a,b) は a と b の最大公約数を表しているのでしょうね。

(1) ある q∈N を用いて a=qb と表せるわけですから，
b は a の約数でもあり，b≦(a,b) です。
一方，(a,b) は b の約数ですから，(a,b)≦b でなければならず，
結局 (a,b)=b でなければなりません。

(2) r=0 のとき (b,0) がなんなのかよくわかりませんので，
r＞0 とさせていただきます。
a=qb+r (q∈N) とおきます。(b,r)=d とおくと a=qmd+nd (m,n∈N) となり，
a=(qm+n)d となります。
qm+n∈N ですから，d は a の約数です。
d は b の約数でもありますから，d≦(a,b) であることがわかります。
一方，(a,b)=c とおくと，a も b も c で割り切れますので，
a-qb=r も c で割り切れます。
よって c は b と r の公約数となり，c≦(b,r)=d となります。
先に得た d≦(a,b)=c と合わせて c=d が結論されます。