主要內容： 本文主要論述了中國剩余定理的背景，由來，離散數學證明方法，編程算法解決以及一些簡單的應用，文章闡述了中國剩余定理的由來，介紹了他的幾種解法.包括他的中國剩余定理研究，研究中國剩余定理的歷史發展及在現代數論中的作用（歷史、中國古代算法、現代解析方法、編程等）以及中國剩余定理在計算機科學上的其他的應用。

  中國剩余定理的簡介以及形成

在我國古代勞動人民中，長期流傳著“隔墻算”、“剪管術”、“秦王暗點兵”等數學游戲。有一首“孫子歌”，甚至遠渡重洋，輸入日本：“三人同行七十稀，五樹梅花廿一枝，七子團圓正半月，除百零五便得知。” 這些饒有趣味的數學游戲，以各種不同形式，介紹世界聞名的“孫子問題”的解法，通俗地反映了中國古代數學一項卓越的成就。“孫子問題”在現代數論中是一個一次同余問題，它最早出現在我國公元四世紀的數學著作《孫子算經》中。《孫子算經》是算經十書之一，又作《孫子算術》。現有傳本《孫子算經》分上、中、下共3卷。該書作者和確切成書年代均無法考證，大約成書于公元400年前后。中國古代求解一次同余式組（見同余）的方法。是數論中一個重要定理。又稱中國剩余定理。 

一千多年前的《孫子算經》中，有這樣一道算術題：“今有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二，問物幾何？”按照今天的話來說：一個數除以三余二，除以五余三，除以七余二，求這個數。《孫子算經》給出了一個非常有效的巧妙解法。術曰：“三、三數之剩二，置一百四十；五、五數之剩三，置六十三；七、七數之剩二，置三十，并之，得二百三十三。以二百一十減之，即得。凡三、三數之剩一，則置七十；五、五數之剩一，則置二十一；七、七數之剩一，則置十五。一百六以上，一百五減之，即得。

秦九韶從孫子定理中推廣了“孫子問題”的解法形成了“中國剩余定理”。 秦九韶（秦九韶，字道古，生活于南宋時期，自幼喜好數學，經過長期積累和苦心鉆研，干公元1247年寫成《數書九章》。這部中世紀的數學杰作，在許多方面都有創造，其中求解一次同余組的“大衍求一術”和求高次方程數值解的“正負開方術”，更是具有世界意義的成就。秦九韶在《數書九章》中明確地系統地敘述了求解一次同余組的一般計算步驟。秦的方法，正是前述的剩余定理。）提出了乘率、定數、衍母、衍數等一系列數學概念，并詳細敘述了“大衍求一術”的完整過程。直到此時，由《孫子算經》“物不知數”題開創的一次同余式問題，才真正得到了一個普遍的解法，才真正上升到了“中國剩余定理”的高度。  這個故事中所說的韓信點兵的計算方法，當時歐洲的數學家們對中國古代數學毫無所知.德國數學家高斯(1777~1855)通過獨立研究,于公元1801年出版的《算術探究》上發表了著名的高斯定理,我們把孫子的“物不知其數”問題的解法與高斯定理一對照,不難看出:高斯定理實質上就是孫子解法的推廣. 公元1852年,英國基督教士偉烈亞力將《孫子算經》中的“物不知其數”問題的解法傳到歐洲。公元1874年,馬蒂生指出:孫子的解法完全符合高斯的定理。而此時,高斯定理已比《孫子算經》中的“物不知其數”問題的解法晚一千五百多年.從此,在西文的數學史上將“物不知其數”問題稱為“中國剩余定理”或“孫子定理”. 

 

 中國古代算法

中國剩余定理的古代算法實際上是，首先利用秦九韶發明的大衍求一術求出5和7的最小公倍數35的倍數中除以3余數為1的最小一個70（這個稱為35相對于3的數論倒數），3和7的最小公倍數21相對于5的數論倒數21，3和5的最小公倍數15相對于7的數論倒數15。然后70X2+21X3+15X2=233

233便是可能的解之一。它加減3、5、7的最小公倍數105的若干倍仍然是解，因此最小的解為233除以105的余數23。

附注：這個解法并非最簡，因為實際上35就符合除3余2的特性，所以最小解是：35X1+21X3+15X2-3X5X7=128-105=23 最小解加上105的正整數倍都是解。

但是中國古代的算法存在著許多的局限性，例如： 

（1）沒有把解法總結成文，致使后人研究多憑猜測；

（2）模數僅限于兩兩互質的正整數，未涉及一般情況； 

（3）未能進一步探究同余式（組）有解的條件等理論問題

現代的解析算法

其實中國剩余定理額可以抽象成現代的數學問題。為了比較清除的了解“中國剩余定理”，我們可以引進課本中對于同余的定義：

若兩個整數,b被同一個大于1的的整數m除有相同的余數，那么a，b模m同余(符號不好打，就不寫了)

一次同余方程的求解的一般步驟：

所以 ：

4   計算機編程來解決同余方程問題：

㈠算法思路：

算法用到了C語言結構體的概念，定義一個結構體數組變量，里面定義了：除數：divisor，余數：remainder

范圍最大值，最小值：MAX_NUM, MIN_NUM;，

最大公約數：gcd_max。循環變量：i，j。

步驟：

①首先我們要計算同余方程中的除數的乘積，因為同于方程的除數互素，所以利用一個for循環計算出。

然后利用雙重for循環計算如果j!=i,則，否則跳出循環

③計算%T[i].divisor

④計算*

⑤結果的最小值為sum%m

C語言代碼：

//中國剩余定理#include <stdio.h>struct node {int divisor;			//表示除數int  remainder;		//表示余數}T[1000];//求最大公約數int gcd ( int n, int m){    return m ? gcd(m, n%m) : n;}int main( ){	//MAX_NUM表示的是所求的解的范圍的最大值，MIN_NUM表示所求的解的范圍的最小值，	//n表示的是同于方程的個數，m表示的是三個除數的乘積，gcd_max表示的是兩個數的最大公約數，因為三個除數是互素的	//所以gcd_max=1；    int i, j, n, t = 0,m = 1, sum = 0, gcd_max = 0, MAX_NUM, MIN_NUM;        PRintf("請輸入有幾個方程：/n");   //如上題韓信點兵。輸入3    scanf("%d", &n);    printf("請輸入每組數據（  余數 除數）：/n"); // 3 2 5 4 7 6    for ( i = 0; i < n; i++)        scanf("%d%d",&T[i].remainder,&T[i].divisor );    printf("請輸入所求值的值域：min max/n" );        scanf("%d%d",&MIN_NUM, &MAX_NUM);//求出三個除數的乘積m    for ( i = 0; i < n; i++) {    gcd_max = gcd (T[i].divisor, gcd_max);    m = m * T[i].divisor;    }    gcd_max *= m;//求mI    for ( i = 0; i < n; i++)     {   		t = 0;m = 1; 		for ( j = 0; j < n; j++)		{			if (j != i  )			{				t = gcd( T[j].divisor , t);				m  = m * T[j].divisor;			}		}		t = m * t;		m = t;		while (m % T[i].divisor != 1)			m += t;		sum += m * T[i].remainder;    }    printf("最小的值為：/n");    printf("%d/n",sum % gcd_max);    printf("在所求的值域內值：/n");	if (sum >= MIN_NUM && sum <= MAX_NUM)	{		sum-=gcd_max;	while(sum>=MIN_NUM && sum<=MAX_NUM)	{ 		printf("%d   ",sum);		sum += gcd_max;			}	}else{	 printf("No Solution!/n");	}    return 0;}
例如：求解上面提到的同余方程：
我們換一組方程進行驗證：
例2：對于同余方程：
我們手工進行演算的值為：
這里m1=3, m2=4, m3=5,m=60.
      M1=5×4=20, M1b ≡1(mod 3), M1^(-1) =b=2.
      M2=3×5=15, M2b≡1(mod 4), M2^(-1)=b=3
      M3=3×4=12, M3b≡1(mod 5), M3^(-1)=b=3.
      x≡2×1×20+2×3×15+3×3×12≡238≡58(mod 60).
      所以x=60k+58
編程實現：
通過以上的幾個同余方程的驗證，這個C語言的程序應該是正確的。只是這個程序的數據都是素數，對于合數的編程還沒有實現
中國剩余定理在其他方面的應用
中國剩余定理雖然是數論中的基本定理，但是在計算機密碼學中有著重要的作用，例如在Rabin密碼算法中用于解密運算，在課本中提到的RSA密碼算法中，中國剩余定理一樣可以用于RSA的解密算法，而且能夠提高加密解密的速度，這無論對于計算機硬件還是軟件都十分重要的可見中國剩余定理應用之廣泛