欧几里得法证明最大公约数的一点思考

本文要证明的题目是欧几里得法（碾转相除法）求得的结果是两个数的最大公约数，本文用gcd(a,b)来表示最大公约数。本文讨论的范围是正整数。
本文要证明的结论：

如果q,r是m除以n的商数和余数，即m=qn+r,即r=m%n。则gcd(m,n) = gcd(n,r)。

比如10,15的最大公约数的求解过程：
1.gcd(10,15) => gcd(15,10) => gcd(10,5) => gcd(5,0)。即最大公约数为5。

约定：对于两个自然数a，b。若存在正整数q使得a=qb，则b能被a整除，b是a的因子，a是b的倍数。记作 b | a. 如果c | a,且 c | b.则c是a，b的公约数。

证明本论点前的几点推论：

1.如果a | b，若k是整数，则a | kb。
证明：b= ha，kb=kha，则a | kb。

2.如果a | b，a | c，则a | (b+/-c)
证明：b = ka，c = ha，b+c=ka + ha = (k+h)a.则a | (b+c)。减法同理。

3.如果a | b，b | a，则 a = b。
证明：根据条件可得 b = ka，a = hb。
b = ka 两边同乘以h得: hb = hka，根据hb = a，得hka = a，推出 hk = 1，因为h，k均为自然数，所以h = k = 1.
所以a = b

4.如果a | b，a | c，d = gcd(b, c),则 a | d。
证明：d是最大公约数。根据定义。即 b = md，c = nd。同时gcd (m,n) = 1， 即m，n没有公共因子。如果a为b,c的约数，因为m，n并没有公共因子了，b=ax，c= ay，即md = ax， nd = ay ，因为d是最大公约数，则m，n的最大公约数为1，而x，y的最大公约数则为 k，可以得出 x = km，y = kn，则kma = md ，则ka = d，则 a | d。

下面开始本文的证明：

如果q,r是m除以n的商数和余数，即m = qn+r,即r=m%n。则gcd(m,n) = gcd(n,r)。

a | m, a | n, m = ax, n = ya, qn = qya, m-qn = ax - qya = (x-qy)a,所以a | (m-qn), 即 a | r,又 a | n.根据推论四，a | b。
b | n, b | r, n = gb, r = fb, qn + r = qgb + fb = ( qg + f) b , qn +r = m,所以 b | m, 又 b | n,根据推论四，所以 b | a。
根据推论三，a | b， b | a。得出 a = b。证明完毕。

ruby算法的实现

def gcd(a,b)
  if b == 0
    return a
  end 
  puts "a,b,a % b : #{a}, #{b},#{a%b}"
  gcd(b,a%b)
end

require 'test/unit'
class GcdTest < Test::Unit::TestCase
  def test_gcd
    assert_equal(gcd(10,15), 5)
    assert_equal(gcd(6,8),2)
    assert_equal(gcd(6,12), 6)
  end
end