Question

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

Answer 1

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

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

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。

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。证明完毕。