a, b為自然數，若a=bq+r,0≤r<b則(a, b)=(b, r) 各位大大可以幫個忙嗎，謝謝?

令 (a, b) = d , (b, r) = d'

(1)
因為 (a, b) = d
所以 d｜a 且 d｜b
即 d｜(bq+r) 且 d｜b
所以 d｜[ 1*(bq+r) + (-q)b ] ..... 請參考底下的性質1
即 d｜r
因此 d｜b 且 d｜r
即 d｜(b,r) = d'

(2)
因為 (b,r) = d'
所以 d'｜b 且 d'｜r
因此 d'｜q*b + 1*r ..... 性質1
即 d'｜a
因此 d｜a 且 d｜b
即 d｜(a,b) = d

由 (1) 與 (2) 得 :
d｜d' 且 d'｜d
所以 d = d'
即 (a, b)=(b, r)
Q.E.D.

性質1
若 d｜a 且 d｜a
則 d｜( ma + nb )
以上常數皆非0整數
pf :
因為 d｜a 且 d｜a
故存在整數 p , q , 使得:
a = pd , b = qd
ma + nb = mpd + nqd = d( mp + nq )
所以 d｜( ma + nb )
Q.E.D.

註解.
此題之結果即"輾轉相除法 求 gcd "的理論依據.