質問＜３４３２＞２００６／１０／１６
from=カノン
「最大公約数」

ａ、ｂ∈Ｎに対してａをｂで割った余りをｒとするとき
１）ｒ＝０→（ａ、ｂ）＝ｂ
２）ｒ≧０→（ａ、ｂ）＝（ｂ、ｒ）
を示せ。
教えて下さい。

★希望★完全解答★

お便り２００６／１０／２１
from=主夫

まず問題文中の
（　，　）というのは，最大公約数を表しているのですが，
この表記は一般的でないようです。事情を知っている解答者にしか
伝わりませんので，注意されたほうがいいです。
それと，
２）ｒ≧０→（ａ、ｂ）＝（ｂ、ｒ）
これは問題文が誤っていますよね？
この辺りも十分注意しないと，解答されにくくなりますよ。

というわけで，２）は
ｒ≧１→（ａ、ｂ）＝（ｂ、ｒ）を正とします。

１）ｒ＝０→（ａ、ｂ）＝ｂ
a=bq+r (q∈自然数N)とおける。
r=0より　a=bq
∴(a,b)=(bq,b)=b

２）ｒ≧１→（ａ、ｂ）＝（ｂ、ｒ）
１）同様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)がいえるはずです。