我國剩余定理的背景與證明

1、 15/15 畢業(yè)設(shè)計(jì)（論文）題目名稱：中國剩余定理的背景及證明院系名稱：理學(xué)院班 級(jí)：數(shù)學(xué)與應(yīng)用數(shù)學(xué)081班學(xué) 號(hào)：學(xué)生某：指導(dǎo)教師：李旭紅 2012年4月中國剩余定理的背景及證明摘 要本文主要討論了中國剩余定理的背景、由來、證明方法以及一些簡單的應(yīng)用, 文中闡述了中國剩余定理的由來，介紹了它的幾種解法，及其它在多項(xiàng)式，現(xiàn)代密碼學(xué)，生活方面的應(yīng)用.“中國剩余定理”是由秦九韶從“孫子定理”的基礎(chǔ)上推廣而來的，本文從論述中國剩余定理的形成到中國剩余定理的主要方法和對現(xiàn)代教育的影響來寫。中國剩余定理在高中有初步的基礎(chǔ)應(yīng)用，在大學(xué)中的初等數(shù)論中該定理得到了仔細(xì)的講解。中國剩余定理的思想方法和原則不僅

2、有光輝的歷史意義，而且在近代數(shù)學(xué)中仍然有著重大影響和作用。關(guān)鍵詞：中國剩余定理； 證明；多項(xiàng)式；應(yīng)用；影響THE BACKGROUND AND PROOF OFTHE CHINESE REMAINDER THEOREMABSTRACTThis paper mainly discusses the remainder theorem of the background and origin, and some simple ways to prove the application, this paper expounds the origin of the Chinese remainder

3、theorem is introduced, and a few of its solution, and other in polynomial, modern cryptography, the application of life. the Chinese remainder theorem is by JiuShaoQinfrom grandson theorem in the foundation to promote, this paper discusses the formation of the Chinese remainder theorem to Chinese re

4、mainder theorem, the main method and modern education to the influence of writing. The Chinese remainder theorem in high school to have a preliminary foundation application, the elementary theory in university in this theorem got the sense of the carefully. The Chinese remainder theorem method and p

5、rinciple of thought not only a glorious history significance, and in modern mathematics still have significant influence and function. Keywords:1 引言中國剩余定理源于我國古代孫子算經(jīng), 其中有一題: “ 今有物不知其數(shù), 三三數(shù)之剩二, 五五數(shù)之剩三, 七七數(shù)之剩二, 問物幾何？” 這就是求解一次同余式組: 孫子算經(jīng)中給出最小正整數(shù)解, 解法傳至今世。中國剩余定理又稱“孫子定理”。它數(shù)初等數(shù)論中重要定理之一，在代數(shù)數(shù)學(xué)和計(jì)算機(jī)領(lǐng)域中也有重要應(yīng)用。本文

6、主要討論中國剩余定理的背景以及證明。 2 中國剩余定理的背景2.1中國剩余定理的由來在我國古代勞動(dòng)人民中，長期流傳著“隔墻算”、“剪管術(shù)”、“秦王暗點(diǎn)兵”等數(shù)學(xué)游戲。有一首“孫子歌”，甚至遠(yuǎn)渡重洋，輸入日本：“三人同行七十稀，五樹梅花廿一枝，七子團(tuán)圓正半月，除百零五便得知?！?這些饒有趣味的數(shù)學(xué)游戲，以各種不同形式，介紹世界聞名的“孫子問題”的解法，通俗地反映了中國古代數(shù)學(xué)一項(xiàng)卓越的成就?！皩O子問題”在現(xiàn)代數(shù)論中是一個(gè)一次同余問題，它最早出現(xiàn)在我國公元四世紀(jì)的數(shù)學(xué)著作孫子算經(jīng)中。孫子算經(jīng)是算經(jīng)十書之一，又作孫子算術(shù)?，F(xiàn)有傳本孫子算經(jīng)分上、中、下共3卷。該書作者和確切成書年代均無法考證，大約成書

7、于公元400年前后。中國古代求解一次同余式組（見同余）的方法。是數(shù)論中一個(gè)重要定理。又稱中國剩余定理。一千多年前的孫子算經(jīng)中，有這樣一道算術(shù)題：“今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何？”按照今天的話來說：一個(gè)數(shù)除以三余二，除以五余三，除以七余二，求這個(gè)數(shù)。孫子算經(jīng)給出了一個(gè)非常有效的巧妙解法。術(shù)曰：“三、三數(shù)之剩二，置一百四十；五、五數(shù)之剩三，置六十三；七、七數(shù)之剩二，置三十，并之，得二百三十三。以二百一十減之，即得。凡三、三數(shù)之剩一，則置七十；五、五數(shù)之剩一，則置二十一；七、七數(shù)之剩一，則置十五。一百六以上，一百五減之，即得。 在中國數(shù)學(xué)史上，廣泛流傳著一個(gè)“韓

8、信點(diǎn)兵”的故事：韓信是漢高祖X邦手下的大將，他英勇善戰(zhàn)，智謀超群，為漢朝的建立立下了卓絕的功勞。據(jù)說韓信的數(shù)學(xué)水平也非常高超，他在點(diǎn)兵的時(shí)候，為了保住軍事某，不讓敵人知道自己部隊(duì)的實(shí)力，先令士兵從1至3報(bào)數(shù)，然后記下最后一個(gè)士兵所報(bào)之?dāng)?shù)；再令士兵從1至5報(bào)數(shù)，也記下最后一個(gè)士兵所報(bào)之?dāng)?shù)；最后令士兵從1至7報(bào)數(shù)，又記下最后一個(gè)士兵所報(bào)之?dāng)?shù)；這樣，他很快就算出了自己部隊(duì)士兵的總?cè)藬?shù)，而敵人則始終無法弄清他的部隊(duì)究竟有多少名士兵？因?yàn)閷O子算經(jīng)對這類問題的研究只是初具雛形，還遠(yuǎn)遠(yuǎn)談不上完整，其不足之處在于：（1）沒有把解法總結(jié)成文，致使后人研究多憑猜測；（2）模數(shù)僅限于兩兩互質(zhì)的正整數(shù)，未涉及一般情況

9、；（3） 未能進(jìn)一步探究同余式（組）有解的條件等理論問題。因此，后人把這一命題及其解法成為“孫子定理”主要是推崇孫子算經(jīng)在這一類問題的處理上時(shí)間領(lǐng)先，其實(shí)想方法的成熟，還有待提高。為了解決這一類“孫子問題”中的不足，秦九韶從孫子定理中推廣了“孫子問題”的解法形成了“中國剩余定理”。 秦九韶（秦九韶，字道古，生活于南宋時(shí)期，自幼喜好數(shù)學(xué)，經(jīng)過長期積累和苦心鉆研，干公元1247年寫成數(shù)書九章。這部中世紀(jì)的數(shù)學(xué)杰作，在許多方面都有創(chuàng)造，其中求解一次同余組的“大衍求一術(shù)”和求高次方程數(shù)值解的“正負(fù)開方術(shù)”，更是具有世界意義的成就。秦九韶在數(shù)書九章中明確地系統(tǒng)地?cái)⑹隽饲蠼庖淮瓮嘟M的一般計(jì)算步驟。秦的方

10、法，正是前述的剩余定理。）提出了乘率、定數(shù)、衍母、衍數(shù)等一系列數(shù)學(xué)概念，并詳細(xì)敘述了“大衍求一術(shù)”的完整過程。直到此時(shí)，由孫子算經(jīng)“物不知數(shù)”題開創(chuàng)的一次同余式問題，才真正得到了一個(gè)普遍的解法，才真正上升到了“中國剩余定理”的高度。 這個(gè)故事中所說的韓信點(diǎn)兵的計(jì)算方法，就是現(xiàn)在被稱為“中國剩余定理”的一次同余式解法。后來流傳的孫子歌中所說“七十稀”、“廿一枝”和“正半月”，就是暗指這三個(gè)關(guān)鍵的數(shù)字。孫子算經(jīng)沒有說明這三個(gè)數(shù)的來歷。實(shí)際上，它們具有如下特性：也就是說，這三個(gè)數(shù)可以從最小公倍數(shù)M=357=105中各約去模數(shù)3、5、7后，再分別乘以整數(shù)2、1、1而得到。假令k1=2，K2=1，K3=

11、1，那么整數(shù)Ki（i=1，2，3）的選取使所得到的三數(shù)70、21、15被相應(yīng)模數(shù)相除的時(shí)候余數(shù)都是1。由此出發(fā)，立即可以推出，在余數(shù)是R1、R2、R3的情況下的情況。應(yīng)用上述推理，可以完全類似地把孫子算法推廣到一般情形：設(shè)有一數(shù)N，分別被兩兩互素的幾個(gè)數(shù)a1、a2、an相除得余數(shù)R1、R2、Rn，即NRi（mod ai）（i=1、2、n），只需求出一組數(shù)K，使?jié)M足1（mod ai）（i=1、2、n），那么適合已給一次同余組的最小正數(shù)解是P是整數(shù)，M=a1a2an），就是現(xiàn)代數(shù)論中著名的剩余定理。為了比較清楚地了解“中國剩余定理”這一名稱的由來，我們不妨先引進(jìn)同余定義：般地,若兩個(gè)整數(shù)a、b被同

12、一個(gè)大于1的整數(shù)m除有相同的余數(shù)，那么稱a、b對于模m同余.記作：。應(yīng)用同余原理，我們把“物不知其數(shù)”問題用整數(shù)的同余式符號(hào)表達(dá)出來是：設(shè)，求最小的數(shù)N。答案是N=23。書中問題及其解法,建立起數(shù)學(xué)模型就是：設(shè)a、b、c為余數(shù)， P為整數(shù)。則的解是: N=70a+21b+15c-105P (1)現(xiàn)在,我們把上述解法中的a,b,c作一分析:設(shè)M=357,則 70=257=2(357)/3=2M/321=37=1(357)/5=1M/515=37=1(357)/7=1M/7因此,問題的解(1)式可以寫成: N=2M/3a+1M/5b+1M/7c (2)當(dāng)時(shí)歐洲的數(shù)學(xué)家們對中國古代數(shù)學(xué)毫無所知.德國

13、數(shù)學(xué)家高斯(17771855)通過獨(dú)立研究,于公元1801年出版的算術(shù)探究上發(fā)表了著名的高斯定理:設(shè)為兩兩互質(zhì)的h個(gè)除數(shù), 各為余數(shù), , ,如果我們找得到滿足,那么.我們把孫子的“物不知其數(shù)”問題的解法與高斯定理一對照,不難看出:高斯定理實(shí)質(zhì)上就是孫子解法的推廣.印度學(xué)者對一次同余論也有過重要貢獻(xiàn)。從公元六世紀(jì)到十二世紀(jì)，他們發(fā)展了一種稱為“庫塔卡”的算法，用來求解和一次同余式等價(jià)的不定方程組?！皫焖ā狈ǔ霈F(xiàn)在孫子算法之后，印度數(shù)學(xué)家婆羅門復(fù)多（七世紀(jì)）、摩柯吠羅（九世紀(jì)）等人的著作中，都有和物不知數(shù)題相同的一次同余問題。這當(dāng)然不是要借此斷言“庫塔卡”法一定受到了孫子算法的影響，但是有人（

14、如萬海依等）硬說中自的“大衍求一術(shù)”來源于“庫塔卡”，就是毫無根據(jù)的妄說了。萬海依居然把中國算法中數(shù)碼從左到右橫寫作為“大衍術(shù)”受印度影響的重要根據(jù)。大家知道，中國古代至遲從春秋戰(zhàn)國時(shí)期就開始使用算籌記數(shù)，我們今天還可以從現(xiàn)存的公元前三世紀(jì)的貨幣上看到這種從左到右的記數(shù)方法。由此可見，萬海依的論點(diǎn)多么荒唐可笑。中國古代數(shù)學(xué)家對一次同余論的研究有明顯的獨(dú)創(chuàng)性和繼承性，“大衍求一術(shù)”在世界數(shù)學(xué)史上的崇高地位是毋容置疑的，正因?yàn)檫@樣，在西方數(shù)學(xué)史著作中，一直公正地稱求解一次同余組的剩余定理為“中國剩余定理”。在中國,以剩余定理為代表的同余理論源遠(yuǎn)流長,可追溯到周易中的卜筮古法.秦九韶說:“圣有大衍,

15、微寓于易”,即指此意.另外,同余理論的另一個(gè)來源是古代制定歷法的需要.實(shí)際上,從漢末到宋末1000余年的時(shí)間中,有很多天文學(xué)家熟悉一次同余式的解法,他們在編制歷法時(shí)利用它來推算“上元積年”.中國剩余定理對現(xiàn)代數(shù)學(xué)的研究有很強(qiáng)的啟迪意義.特別是在多項(xiàng)式，密碼學(xué)中的應(yīng)用非常關(guān)鍵. 隨著數(shù)學(xué)學(xué)科的發(fā)展，數(shù)學(xué)方面的知識(shí)得到了不斷的更新和強(qiáng)化。在數(shù)學(xué)發(fā)展史上，剩余問題（即：在整數(shù)除法里，一個(gè)數(shù)同時(shí)除以幾個(gè)數(shù)，整數(shù)商后，均有剩余；已知各除數(shù)及其對應(yīng)的余數(shù)，要求適合條件的這個(gè)被除數(shù)。這類問題統(tǒng)稱剩余問題）曾經(jīng)困擾過人們很長一段時(shí)間。這個(gè)問題的解決，是我們中國人邁出了開拓性的第一步。如果說，一部中國數(shù)學(xué)發(fā)展史

16、像一條淵遠(yuǎn)流長的河流，那么幾千年來祖先們?nèi)〉玫妮x煌成就，就是這河流中耀眼的浪花。在祖先取得的成就中有一個(gè)“中國剩余定理”。大家都知道，“勾股定理”最早是由我國西周時(shí)期的商高發(fā)現(xiàn)的，但國外卻稱其為“畢達(dá)哥拉斯定理”，法國稱為“驢橋定理”，埃及稱為“埃及三角形”等。還有“增乘開方法”，最早是由我國宋代的賈憲發(fā)明的，但現(xiàn)代數(shù)學(xué)卻稱其為“霍納法”，賈憲的發(fā)明比霍納早了800年。而中國剩余定理則是唯一一個(gè)以我國國名命名的定理，大家一定對這個(gè)定理很感興趣，很想知道關(guān)于這個(gè)定理的故事。現(xiàn)在我就為大家簡單介紹一下“中國剩余定理”。 公元1852年,英國基督教士偉烈亞力將孫子算經(jīng)中的“物不知其數(shù)”問題的解法傳到

17、歐洲。公元1874年,馬蒂生指出:孫子的解法完全符合高斯的定理。而此時(shí),高斯定理已比孫子算經(jīng)中的“物不知其數(shù)”問題的解法晚一千五百多年.從此,在西文的數(shù)學(xué)史上將“物不知其數(shù)”問題稱為“中國剩余定理”或“孫子定理”.3中國剩余定理的證明及解法中國剩余定理：設(shè)是兩兩互素的正整數(shù)，設(shè)是整數(shù)，則同余方程組，模有惟一解 ,其中,.3.1中國剩余定理的解法中國剩余定理的解法有許多，本文就介紹幾種常見的，歌訣法，不定方程解法，同余解法。其余的解法就不一一介紹，每種解法有它的優(yōu)點(diǎn)，最基礎(chǔ)的還是歌訣法.2.1 歌訣法2.1.1 兩個(gè)算數(shù)定理定理1被除數(shù)增加(或減少)除數(shù)的倍數(shù),除數(shù)不變,則余數(shù)也不變.即:如果a

18、b=q (余r),則(a+bn)b=q+n (余r) (nZ).證明ab=q (余r)則a=bq+ra+bn =(q+n)b+r,即(a+bn),b=q+n(余r)定理2被除數(shù)擴(kuò)大(或縮小)幾倍,除數(shù)不變,則余數(shù)也擴(kuò)大(或縮小)同數(shù)倍.即:如果ab=q (余r),那么anb=qn (余rn);若rnb,則余rn-bm使rn-bmb (m, nZ),則: anb=qn+m (余rn-bm)證明由ab=q (余r) a=bq+r,則an=b (nq)+rn,所以anb=nq (余rn)2.1.2解法歌訣明朝程大位編著的算法統(tǒng)宗(公元1592年)里記載了此題的解法,他是用一首歌謠(孫子歌)敘述出來的

19、:“三人同行七十稀,五樹梅花廿一枝,七子團(tuán)圓正月半,除百零五便得知.”它的每句歌謠都隱藏著解題需要的數(shù).“三(3)人同行七十(70)稀”,即用被3除所得的余數(shù)乘以70.“五(5)樹梅花廿一(21)枝”,即用被5除所得的余數(shù)乘以21.“七(7)子團(tuán)圓正月半(15)”,即用被7除所得的余數(shù)乘以15.“除百零五(105)便得知”,是說把上面所得的三個(gè)積相加,如果和大于105,就減去105的若干倍,直到差小于105為止,得出的差就是所求的最小正整數(shù).解答算式是:702+213+152=233,233-1052=232.1.3解法的理由及步驟先在5與7的公倍數(shù)中找除以3余1的數(shù),進(jìn)而找到除以3余2的數(shù).

20、5, 7=35353=11(余2),由定理2(352)3=23(余1) 而(702)3=46(余2),所以140是符合條件的數(shù).在3與7的公倍數(shù)中找除以5余3的數(shù).3,7=21215=4(余1)由定理22135=12(余3)即63符合條件在3與5的公倍數(shù)中找除以7余2的數(shù).3,5=15157=2(余1)由定理21527=4(余2)即30符合條件將上面得到的分別符合三個(gè)條件的三個(gè)數(shù)相加:702+213+152=233140加上的數(shù)都是3的倍數(shù),除以3的余數(shù)不變(定理1);即233滿足除以3余2的條件,同理可知,233也滿足題目中的另外兩個(gè)條件,即物數(shù)W=233就是本題的一個(gè)解,又3,5,7=10

21、5,再由定理1可知,233-2105=23也是它的解,又23105,Wmin=23.上面的解法中,總是先求出余1的數(shù),再求出余幾的數(shù),這種解法逐漸被總結(jié)為簡潔實(shí)用的“求一術(shù)”.其實(shí),早在宋朝的周密就曾把這個(gè)題目的解法編成如下的歌謠“三歲孩兒七十稀,五留廿一事尤奇,七度上元重相會(huì),寒食清明便可知”.這里的“上元”指十五,而“寒食”指清明的前一天,冬至后106天是清明節(jié),所以冬至到寒食為105天.歌謠中將解題所用各數(shù)暗暗給出,增加了題目的趣味性和神秘性.2.2.4不定方程解法設(shè)物數(shù)為W, W被3、5、7除所得的不完全商分別為x、y、z則有:消去W,得到 3x-5y=1 (4) 3x=7z (5)由

22、(5)式得x=7z/3令 (N),得 (6)從而有y=(21-1)/5=4+(-1)/5, 再令(-1)/5= (N)則=5+1x=35+7y=+4z=15+3,W=105+23,這就是“物不知數(shù)”問題的通解公式,顯然當(dāng)=0時(shí),有最小正整數(shù)解W=23.1.3同余解法“物不知數(shù)”問題用同余式組來表達(dá),即解由(1)得W= (4)代入(2)式得3(mod5) 31 (mod5) 36(mod5) 2(mod5) =2+5,將其代入(4)式有W=8+15 (5)由(5),(3)兩式,8+15=2(mod7)8+159(mod7)151(mod7)1515(mod7) 1(mod7) =1+7,將代入(

23、5)式,得W=23+105,即W=23(mod105)3、5、7兩兩互質(zhì),所以W23(mod105 )是同余式組的解.在孫子算經(jīng)中給出的解答實(shí)質(zhì)上就是W702+213+152140+63+3023323(mod105)3.2中國剩余定理的證明設(shè) 12 2, , , ,n nmm m L 兩兩互素的正整數(shù)，令 12 1 1 2 2 nnn Mmm m mM mM mM = LL ，則同余式組 1122(mod )(mod )(mod ) nnxc mxc mxc m= = = LLLLLL有正整數(shù)解 111 2 22 (mod ) nnn xMcM c M c M + + L 且解唯一；其中 i

24、 是滿足 1(mod ), 1, 2, , ) ii iMmkn = L 的一個(gè)整數(shù)（參閱 3）.下面我們先給出裴蜀恒等式和一個(gè)性質(zhì)，然后證明中國剩余定理 .裴蜀恒等式 如果兩個(gè)數(shù)的最大公約數(shù)是d ，則必定存在兩個(gè)整數(shù) , xy使得等式ax by d += 成立（參閱 4）.性質(zhì) 同余式組 (mod ), 1, 2, ,jab m j n = L 同時(shí)成立的充要條件是 12 (mod , , , ) n ab mm m L （參閱 5）.證明： 先證存在性：因?yàn)?12 ,n mm m L ，兩兩互素， kkM M m= ，故(,)1, 1,2,kkMm k n = L ，由裴蜀恒等式可知一定存

25、在整數(shù) ,kk 使得1 kk k kMm += ，即 1 kk k kMm = + ，因此必定存在 k ，使1(mod ), 1, 2, ,kk kMmkn = L又因當(dāng) k 時(shí)，恒有 kmM ，所以 1(mod )( ) kkMmk 若令 111 2 22 nnn RMcM c M c =+ + L ，則有111 1222 2(mod )(mod )(mod ) nnn nRMc mRM c mRM c m= = = LLLLLLLL又 kmM ，故 0(mod ) kMm ，從而(mod ), 1, 2, ,kkxRMtRc mk n =+ = L .因此 (mod ) xR M ，即 1

26、11 2 22 (mod ) nnn xMcM c M c M + + L 為同余式組之解 .唯一性：設(shè)該同余式組還有一解 y，則有(mod ), 1, 2, ,kxy mk n = L由于 12 ,n mm m L 兩兩互素，因此 12 12 , , nn Mmm m mmm = LL ，利用所給性質(zhì)可知 (mod ) xy M ，證畢 .4中國剩余定理的應(yīng)用中國定理是中國古代數(shù)學(xué)家為世界數(shù)學(xué)發(fā)展作出的巨大貢獻(xiàn), 它的數(shù)學(xué)思想在近代數(shù)學(xué)、當(dāng)代秘密學(xué)研究及日常生活都有著廣泛應(yīng)用. 4. 1中國剩余定理在賦值理論中的體現(xiàn) 賦值理論是域論的一個(gè)分支, 是研究近代數(shù)學(xué)中幾個(gè)重要分支如代數(shù)數(shù)論、交換數(shù)

27、論的一個(gè)重要工具, 而中國剩余定理在賦值論中起著重要作用, 下面介紹中國剩余定理在賦值理論中的應(yīng)用. 定理 (賦值的獨(dú)立性)對于任意個(gè)賦值, , , 以及任意, , 則存在使; (2), 證明 設(shè)為的最小公分母, 令, , , . 根據(jù)中國剩余定理, 可求得一個(gè), 使得, , , 即 , 設(shè), 取適當(dāng)?shù)? 使, 再令, 則顯然滿足條件(1). 又由距離的性質(zhì): 有, . 4. 2 中國剩余定理在多項(xiàng)式中的應(yīng)用 由中國剩余定理可得相似定理. 設(shè)是個(gè)兩兩互素的多項(xiàng)式, 是個(gè)多項(xiàng)式, 則一定存在多項(xiàng)式, 使當(dāng)?shù)拇螖?shù)不超過的次數(shù)是, 唯一確定. 特別地, 當(dāng)(或), , 是互不相等的常數(shù), 從而也是兩兩互素的多項(xiàng)式, 由余數(shù)定理可知, 從而定理可敘述為, 一定存在多項(xiàng)式, 是其中是任意給定的常數(shù), 且多項(xiàng)式在次數(shù)不超過的條件下唯一確定的, 有等價(jià)于得: 對任意互不相同的存在唯一的次數(shù)小于的多項(xiàng)式, 是. 這就是插值多項(xiàng)式的存在與唯一性定理. 由中國剩余定理的證法, 只要找到多項(xiàng)式, 使, (1)而滿足(1), 于是的插值多項(xiàng)式: 這就是著名的Lagrange內(nèi)插多項(xiàng)式. 中國剩余定理推導(dǎo)出的內(nèi)插多項(xiàng)式是處理許多多項(xiàng)式問題的基本工具如簡化數(shù)列求和問題: 計(jì)算解 假設(shè)和為的三次多項(xiàng)式, 代表項(xiàng)數(shù), 于是有由插值公式得所以, .中國剩余定理主要是解決一次同余式問題, 在算術(shù)中還可以利用它來