質問<3432>2006/10/16
a、b∈Nに対してaをbで割った余りをrとするとき 1)r=0→(a、b)=b 2)r≧0→(a、b)=(b、r) を示せ。 教えて下さい。 ★希望★完全解答★
お便り2006/10/21
from=主夫
まず問題文中の ( , )というのは,最大公約数を表しているのですが, この表記は一般的でないようです。事情を知っている解答者にしか 伝わりませんので,注意されたほうがいいです。 それと, 2)r≧0→(a、b)=(b、r) これは問題文が誤っていますよね? この辺りも十分注意しないと,解答されにくくなりますよ。 というわけで,2)は r≧1→(a、b)=(b、r)を正とします。 1)r=0→(a、b)=b a=bq+r (q∈自然数N)とおける。 r=0より a=bq ∴(a,b)=(bq,b)=b 2)r≧1→(a、b)=(b、r) 1)同様a=bq+rとおく。 (b,r)=dとおくと a=(md)q+nd (m,n∈自然数N)とおけるから, a=(mq+n)d つまりdはaの約数であるといえる。 さらにdはbの約数でもあるから,d≦(a,b) これと同じ論証を (a,b)=cについて述べてみましょう。 それらを合体させればc=dとなるので, (a,b)=(b,r)がいえるはずです。