２つの整数a≧0，b＞0を入力として与えられたとき、それらの最大公約数ｇｃｄ(a，b)を出力する問題を考える。

(１)aをbで割った商をq，譲与をr(0≦r＜b)とするとき、ｇｃｄ(a，b)＝ｇｃｄ(b，r)であることを示せ。
(ヒント：a，bの任意の公約数はｇｃｄ(a，b)の約数である。この事実を使ってｇｃｄ(a，b)とｇｃｄ(b，c)は互いに他の約数になっていることを示せ)

(２)(１)の性質を用いて、この問題を解くためのアルゴリズムを構成せよ。

どうか宜しくお願いします。