關於輾轉相除法的證明，及進位製表示法

一.輾轉相除法

1.求最大公因子的方法(a,b) = (b,c)稱為輾轉相除法
  Ⅰ.其中a = qb + c; (a,b)為a,b的最大公因子。
  Ⅱ.簡化了求最大公因子的工作量，因為任意整數和0的公因子為其本身。若餘數c=0時，b即為最大公因子。

2.輾轉相除法的證明：
  Ⅰ.因為(a,b)整除a，(a,b)整除b，根據整除的性質（即a整除b，a整除c，可以得到a整除mb+mc ）可以得到(a,b)整除c，所以有(b,c)>=(a,b)（因為(a,b)是c的因子，也是b的因子，所以(b,c)>=(a,c)。)。同理可得c<=(a,b)，所以可以得到結果：(a,b) = (b,c)

3.輾轉相除法的遞迴實現

int digui(int a , int b){
	if(b==0) return b;
	return digui(b,a%b);
}

二.進位製表示法

  Ⅰ.任何整數n都可以表示為a進位制：r(t)*a^t + r(t-1)a^(t-1) + … +r1a + r0.
  Ⅱ.證明：對於整數n，可表示為 n = q0 * a + r0。現在將q0分解 q0 = q1 * a + r1。原式等於 n = (q1 * a + r1) * a + r0。遞推可得到存在 0 <= q(t-1) < a，使得 q(t-1) = rt。所以可以得到Ⅰ中的式子。