質問<2371>2005/5/21
a.b∈Nに対し、aをbで割ったあまりをrとする。次を示せ。 ①r=0⇒(a,b)=b ②r≧0⇒(a,b)=(b,r) ★希望★完全解答★
お便り2005/6/16
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 が結論されます。