輾轉相除法求GCD的證明

一直在用gcd（），卻不了解其中的原因，。今天回過頭來，從頭學起。

int gcd(int a, int b)
{
	return b == 0 ? a : gcd(b,a%b);
}
           

1. 首先要知道，0 于 n 的最大公約數是 n。是以當b == 0時候，最大公約數就是a。

重要的是要證明：gcd(a, b) = gcd( b, a%b);

2. 設 gcd（a，b） =  g。    (a >= b)

   則  a = k1g,    b = k2g.

   設  a/b = n......r     ,

   則  a%b = a - n*b = r 。

   則  r = （k1g - n* k2g ） = g * (k1 - n * k2) .

  即證明 :  gcd(  k2g ,   g * (k1 - n * k2)  ) = g;

  即        ：gcd(k2 , k1- n*k2 ) = 1;!!

到這裡 ，隻要證明k2  和  k1 - n*k2 互質，就完畢。  也很簡單 ，用反證法。

3. 假設它們不互質，且  k1 - n*k2 = x*k2,

則                              k1 = (n + x) k2

則                             a = （n + x）k2 * g

                                 b =   k2 * g

顯然必将得到一個大于 g 的最大公約數，沖突，得證。