証明
　$ (a,~b) = g,　(b,~r) = h $ とおいて、実は $ g = h $ であることを示しましよう。
　$ a,b $ は $ g $ の倍数なので、自然数 $ a',b' $ を用いて、
　　　　　$ a = a'g,~b = b'g …(1) $
と書くことができます。
　$ a $ を $ b $ で割った商を $ q $ とします。余りが $ r $ ですから、
　　　　　$ a = qb + r …(2) $ 　　これより、$ r = a - qb $
これに $ (1) $ を代入して、$ r = a'g - qb'g = (a' - qb')g $
となり $ r $ も $ g $ を約数として持ちます。もともと $ b $ は $ g $ を約数として持ちますから、$ g $ は $ b $ と $ r $ の公約数です。公約数は最大公約数以下ですから、
$ g \leqq h $ です。
　また、$b,　r $ は $ h $ の倍数なので、自然数 $ c',　r' $ を用いて、
　　　　　$ b = c'h,　　r = r'h $
と書くことができます。$ (2) $ にこれを代入して、
　　　　　$ a = qb + r = qc'h + r'h = (qc' + r')h $
　$ a $ は $ h $ を約数に持ちます。$ b $ はもともと $ h $ を約数に持ちますから、$ h $ は $ a $ と $ b $ の公約数です。公約数は最大公約数以下なので、$ g \geqq h $ です。
　$ g \leqq h $ かつ $ g \geqq h $ が示されたので、$ g = h $ です。
(証明終わり)

これを明確に理解するには下記の図が助けになるでしょう。参考にしてみて下さい。

応援してね。
千里の道も一歩から。そしてその道は登り坂です。ローマは１日にして成らず、です。

(ポチッとブログ村のバナーをクリックしてね）