(密碼學(xué))初等數(shù)論 PPT

初等數(shù)論數(shù)論簡介以下內(nèi)容部分來自于“百度百科”整數(shù)分為正整數(shù)（自然數(shù)）、負整數(shù)和零確切地說，數(shù)論就是一門研究整數(shù)性質(zhì)的學(xué)科。整數(shù)的特性，比如，加、減、乘、除四則運算中，加、減、乘可以在整數(shù)范圍內(nèi)毫無阻礙地進行，但是除法卻不行。在古希臘時代，數(shù)學(xué)家對數(shù)論的整除性問題就有過系統(tǒng)的研究，在我國古代，許多著名的數(shù)學(xué)著作中都記載有數(shù)論的相關(guān)內(nèi)容，如，孫子定理、勾股數(shù)組、百錢買百雞、韓信點兵問題等。數(shù)論簡介在整數(shù)性質(zhì)的研究中，人們發(fā)現(xiàn)素數(shù)是構(gòu)成正整數(shù)的基本“材料”，而算術(shù)基本定理正是深刻揭示正整數(shù)與素數(shù)的重要關(guān)系。因此，深入研究整數(shù)的性質(zhì)就劃歸為對素數(shù)性質(zhì)的研究。18世紀末，歷代數(shù)學(xué)家積累的關(guān)于整數(shù)性質(zhì)的零散結(jié)論已經(jīng)十分豐富。德國數(shù)學(xué)家高斯集前人之大成，撰寫《算術(shù)探討》一書，于1800年寄給法國科學(xué)院，但是遭到拒絕出版，高斯于1801年自己出版，標志現(xiàn)代數(shù)論新紀元的開始。數(shù)論簡介按照研究方法，分為初等數(shù)論、解析數(shù)論、代數(shù)數(shù)論和幾何數(shù)論。初等數(shù)論是數(shù)論中不求助于其他數(shù)學(xué)學(xué)科的幫助，只依靠初等方法來研究整數(shù)性質(zhì)的分支，比如著名的“孫子定理”的證明就是典型的初等方法。早期的時候，人們并不清楚它的實際意義，目前，由于近代計算機學(xué)科和應(yīng)用數(shù)學(xué)學(xué)科的發(fā)展，數(shù)論得到了廣泛應(yīng)用。比如，在計算方法、代數(shù)編碼、組合論、密碼學(xué)中都得到了廣泛應(yīng)用。數(shù)論簡介數(shù)論在數(shù)學(xué)中具有獨特地位，高斯：“數(shù)學(xué)是科學(xué)的皇后，數(shù)論是數(shù)學(xué)中的皇冠”。在我國近代，從20世紀30年代開始，我國在解析數(shù)論方面都有過重要貢獻，如華羅庚在三角和估值、堆砌素數(shù)等方面的研究成果享有盛名。1949年以后，陳景潤證明“哥德巴赫猜想”的“一個大偶數(shù)可以表示為一個素數(shù)和一個不超過兩個素數(shù)的乘積之和”，至今仍是最好的結(jié)果。數(shù)論簡介數(shù)論中的數(shù)學(xué)方法對數(shù)學(xué)的發(fā)展起著重要作用。許多數(shù)論難題的解決是對數(shù)學(xué)思維方法的極大挑戰(zhàn)，由此產(chǎn)生了大量代數(shù)的、解析的、初等的、高等的、簡單的和高深復(fù)雜的數(shù)學(xué)方法。內(nèi)容素數(shù)與互素同余與模運算歐拉（Euler）定理幾個重要算法中國剩余定理模為素數(shù)的二次剩余離散對數(shù)素數(shù)與互素1整除定義：如果整數(shù)a、b、c之間存在關(guān)系a=b·c且b≠0，則稱b整除a或者a能被b整除，且b是a的因子或除數(shù)，a是b的倍數(shù)。記為b|a。素數(shù)與互素1整除整除的性質(zhì)：a|a如果a|1，則有a=±1對于任何a≠0，則有a|0如果a|b且b|a，則有a=±b如果a|b且b|c，則有a|c如果a|b且a|c，那么對所有的x，y∈Z有a|(bx+cy)，Z表示整數(shù)集。素數(shù)與互素1整除整除的特殊例子末1位能被2整除，則該數(shù)能被2整除末2位能被4整除，則該數(shù)能被4整除末3位能被8整除，則該數(shù)能被8整除素數(shù)與互素1整除整除的特殊例子末1位能被5整除，則該數(shù)能被5整除末2位能被25整除，則該數(shù)能被25整除末3位能被125整除，則該數(shù)能被125整除若各位數(shù)字之和能被3整除，則該數(shù)能被3整除若各位數(shù)字之和能被9整除，則該數(shù)能被9整除素數(shù)與互素1整除·7的倍數(shù)若一個整數(shù)的個位數(shù)字截去，再從余下的數(shù)中，減去個位數(shù)的2倍，如果差是7的倍數(shù)，則原數(shù)能被7整除。例：133是否7的倍數(shù)？過程如下：13-3×2＝7，所以133是7的倍數(shù)；又例如判斷6139是否7的倍數(shù)的過程如下：613-9×2＝595，59-5×2＝49，所以6139是7的倍數(shù)，余類推。如果差太大，可繼續(xù)上述「截尾、倍大、相減、驗差」的過程，直到能清楚判斷為止。素數(shù)與互素1整除·11的倍數(shù)若偶數(shù)位數(shù)字之和與奇數(shù)位數(shù)字之和的差能被11整除，則該數(shù)能被11整除。例如：1364是否是11的倍數(shù)？·偶數(shù)位數(shù)字之和與奇數(shù)位數(shù)字之和的差為0·截尾法：136-4×1=132，13-2×1=11素數(shù)與互素1整除·11的倍數(shù)使用“截尾、倍大（1倍）、相減、驗差”的過程。·13的倍數(shù)使用“截尾、倍大（4倍）、相加、驗和”的過程?！?7的倍數(shù)使用“截尾、倍大（5倍）、相減、驗差”的過程?！?9的倍數(shù)使用“截尾、倍大（2倍）、相加、驗和”的過程。例：驗證23446是否是19的倍數(shù)？1整除若一個整數(shù)的末三位與3倍的前面的隔出數(shù)的差能被17整除，則這個數(shù)能被17整除。（例如，17017：17-17×3=-34，能被17整除）若一個整數(shù)的末三位與7倍的前面的隔出數(shù)的差能被19整除，則這個數(shù)能被19整除。若一個整數(shù)的末四位與前面5倍的隔出數(shù)的差能被23(或29)整除，則這個數(shù)能被23(或29)整除其他規(guī)律…素數(shù)與互素素數(shù)與互素2素數(shù)定義：如果p≠±1且p的因子僅為±1和±p，則整數(shù)p被稱為素數(shù)或質(zhì)數(shù)。非素數(shù)的整數(shù)被稱為合數(shù)，1既不是素數(shù)也不是合數(shù)。素數(shù)與互素3最大公因子設(shè)a,b,c∈Z，如果c|a且c|b，則稱c是a與b的公因子或公約數(shù)。如果d滿足以下條件，則稱正整數(shù)d是a與b的最大公因子：（1）d是a與b的公因子（2）如果c也是a與b的公因子，則c必是d的因子最大公因子是公因子中的最大的那一個，記為d＝gcd(a,b)=max{c|c|a且c|b}如果a和b全為0，則它們的公因子和最大公因子均無意義。素數(shù)與互素3最大公因子例，gcd(1080,945)=1351080=23×33×5945=33×5×7素數(shù)與互素3最大公因子互素：如果a與b的最大公因子為1，則稱整數(shù)a與b互素，即gcd(a,b)=1。同余與模運算3最大公因子帶余數(shù)除法定理：設(shè)a和b是兩個整數(shù)，b≠0，則存在唯一的一對整數(shù)q和r，使得a=bq+r(0≤r<|b|)例：若a=17，b=5，則a=3b+2，q=[17/5]=3，r=17mod5=2素數(shù)與互素3最大公因子最大公因子有下列性質(zhì)：（1）任何不全為0的兩個整數(shù)的最大公因子存在且唯一素數(shù)與互素3最大公因子（2）設(shè)整數(shù)a與b不全為0，則存在整數(shù)x和y，使得ax+by=gcd(a,b)證明：設(shè)S={ax+by>0|x,y∈Z}，由于整數(shù)a,b不全為0，可知S非空，設(shè)S中最小的正整數(shù)為e，令e=am+bn，m,n∈Z。由帶余除法定理，可設(shè)a=qe+r，0≤r<e，所以r=a-qe=a-q(ma+nb)=(1-qm)a-qnb。若r≠0，則r∈S，由于e是S中的最小正整數(shù)，與r<e矛盾，故r=0，從而e|a，同理e|b，即e是a，b的一個公因子，所以e≤gcd(a,b)。另一方面，設(shè)gcd(a,b)=d，知d|a，d|b，則d|(am+bn)，即d|e，因此d≤e，所以e=d。得證素數(shù)與互素3最大公因子（2）推論：特別地，如果a與b互素，則存在整數(shù)x與y，使得ax+by=1（gcd(a,b)=1）（問題：逆否命題是否成立？即，設(shè)整數(shù)a與b不全為0，若存在整數(shù)x與y使得ax+by=1，則a與b是否互素？）素數(shù)與互素3最大公因子（3）如果gcd(a,b)=d，那么證明：設(shè)，則e|，e|，即ed|a，ed|b。也就是說ed是a，b的一個公因子，又gcd(a,b)=d，從而ed≤d，所以e=1。素數(shù)與互素3最大公因子（4）如果c|(ab)，且gcd(b,c)=1，那么c|a證明：由性質(zhì)（2），由于gcd(b,c)=1，則存在x,y，使得xb+cy=1，等式兩邊乘以a得，axb+acy=a又c|(ab)，所以c|(axb+acy)，即c|a素數(shù)與互素3最大公因子（5）整數(shù)a,b不全為0，如果d是a,b的一個正公因子，且存在整數(shù)m,n，使得d=am+bn，則gcd(a,b)=d。證明：設(shè)gcd(a,b)=e，則e|a,e|b，由于d=am+bn，得e|d，又d>0，所以e≤d，另一方面，由于d是a,b的一個正公因子，知d≤e，故d=e。素數(shù)與互素3最大公因子（6）gcd(a,b)=1的充要條件是存在整數(shù)u,v使得au+bv=1。證明：由性質(zhì)（2）和（5）既得。素數(shù)與互素3最大公因子（7）如果gcd(a,x)=gcd(b,x)=1，那么gcd(ab,x)=1證明：根據(jù)性質(zhì)（2）即推論，存在整數(shù)t,y,z,w，使得at+xy=1，bz+xw=1，上兩式相乘并整理得，abtz+x(w+y+xwy)=1由性質(zhì)（6）得，gcd(ab,x)=1素數(shù)與互素4算術(shù)基本定理定理1：

設(shè)a是大于1的整數(shù)，則a的除1外最小正因子q是一素數(shù)，且當a是合數(shù)時，證明：假設(shè)q不是素數(shù)，由定義，q除1及本身外還有一個正因子q1，因而1＜q1＜q，但q|a，所以q1|a，這與q是a的除1外最小正因子相矛盾，故q是素數(shù)。當a是合數(shù)時，則a=a1q，且a1＞1，由于q是a的除1外最小正因子，所以q≤a1，q2≤qa1=a，故素數(shù)與互素4算術(shù)基本定理說明：判斷n是否為素數(shù)的最笨拙的方法是依次用2,3,…,n-1去除n，如果這n-2個數(shù)都不整除n，則n為素數(shù)，否則n不是素數(shù)。這種方法要作n-2次除法運算，所花費的時間至少要與n成正比。根據(jù)定理1，我們只需用以內(nèi)的整數(shù)去除n即可判別n是否為素數(shù)。素數(shù)與互素4算術(shù)基本定理定理2：若p是一個素數(shù)，a是任一整數(shù)，則a能被p整除或p與a互素。證明：因p是素數(shù)，由素數(shù)的定義有g(shù)cd(p,a)=1，或者gcd(p,a)=p素數(shù)與互素4算術(shù)基本定理推論1：設(shè)a1,a2,…,an是n個整數(shù)，p是素數(shù)，若p|a1a2…an，則p一定能夠整除某一個ai。證明：

假設(shè)a1,a2,…,an都不能被p整除，則由定理2，gcd(p,ai)=1，i=1,2,…,n。因此gcd(p,a1a2…an)=1，這與p|a1a2…an矛盾，結(jié)論成立。素數(shù)與互素4算術(shù)基本定理定理3：任何大于1的正整數(shù)a可以寫成素數(shù)之積，即a=p1p2…pn，其中pi（1≤i≤n）是素數(shù)。證明：當a是素數(shù)時，定理成立。當a是合數(shù)時，由定理1知必存在素數(shù)p1，且，所以a=p1a1，且1<a1<a。若a1是素數(shù)，則定理成立。若a1是合數(shù)，同理，則必有素數(shù)p2以及適合1<a2<a1的正整數(shù)a2，使a=p1p2a2成立。由于a是有限的，所以有限次重復(fù)上述過程可得a=p1p2…pn，其中pi（1≤i≤n）是素數(shù)。素數(shù)與互素4算術(shù)基本定理算術(shù)基本定理：設(shè)2≤a∈Z，則a可以分解成素數(shù)冪的乘積其中，pi（i=1,2,…,k）是互不相同的素數(shù)，αi（i=1,2,…,k）是正整數(shù)。若不計因子順序，上式唯一。證明：由定理3可知，任何大于1的整數(shù)可以表示成只需證明唯一性。假設(shè)pi（i=1,2,…,n）與qi（i=1,2,…,k）都是素數(shù)，p1<p2<…<pn，q1<q2<…<qk，且a=p1p2…pn=q1q2…qk，因為p1|a=q1q2…qk，則有某個qj，使得p1|qj，從而p1=qj。同理，有某個pi，q1=pi。又p1<p2<…<pn，q1<q2<…<qk，可知p1=q1。重復(fù)上述過程，得到n=k，pi=qi，結(jié)論成立。素數(shù)與互素例：寫出51480的標準分解式：51480=23·32·5·11·13其中2,3,5,11,13都是素數(shù)。分解整數(shù)：524287？素數(shù)與互素關(guān)于素數(shù)的一些基本結(jié)論（1）素數(shù)有無窮多個，但目前尚無有效辦法確定所有素數(shù)。例如，將形如Mn=2n?1的數(shù)稱為梅森數(shù)（Mersenne,17世紀法國數(shù)學(xué)家）。以下是最近發(fā)現(xiàn)的一些梅森素數(shù)。序號pMp=2p-1Mp的位數(shù)發(fā)現(xiàn)時間發(fā)現(xiàn)者1231古代古人2371古代古人………………4225,964,951122164630…5770772477,816,2302005年2月18日GIMPS/MartinNowak43*30,402,457315416475…6529438719,152,0522005年12月15日GIMPS/CurtisCooper及StevenBoone44*32,582,657124575026…0539678719,808,3582006年9月4日GIMPS/CurtisCooper及StevenBoone45*37,156,667202254406…30822092711,185,2722008年9月6日GIMPS/Hans-MichaelElvenich46*42,643,801169873516…56231475112,837,0642009年4月12日GIMPS/OddM.Strindmo47*43,112,609316470269…69715251112,978,1892008年8月23日GIMPS/EdsonSmith48*57,885,161581887266…72428595117,425,1702013年1月25日GIMPS/CurtisCooper截止2013年2月6日，已經(jīng)發(fā)現(xiàn)了48個梅森素數(shù)，并且確定M25964951位于梅森素數(shù)序列中的第42位。列表如下：（現(xiàn)在還不知道在第42個梅森素數(shù)（M25,964,951）和第48個（M57,885,161）之間是否還存在未知梅森素數(shù)，所以在其序號之前用*標出）素數(shù)與互素（2）素數(shù)定理描述素數(shù)的大致分布情況。素數(shù)的出現(xiàn)規(guī)律一直困惑著數(shù)學(xué)家。單個來看，素數(shù)在正整數(shù)中的出現(xiàn)沒有規(guī)律，但從總體上看，素數(shù)的個數(shù)有規(guī)律可循：設(shè)x∈Z，則不超過x的素數(shù)個數(shù)可以近似的用x/lnx表示。同余與模運算1.帶余除法對于任意的兩個正整數(shù)a和b，存在唯一確定的兩個整數(shù)k和r，滿足a=kb+r且0≤r<b，分別稱為k和r為a除以b（或者b除a）的商和余數(shù)，并稱滿足這種規(guī)則的運算為帶余除法。K=[a/b]，記a除以b的余數(shù)為amodb，帶余除法表示成：a=[a/b]b+amodb例：若a=17，b=5，則a=3b+2，K=[17/5]=3，r=17mod5=2同余與模運算2.整數(shù)同余與模運算設(shè)a,b,c∈Z且n＞0，如果a和b除以n的余數(shù)相等，即amodn=bmodn，則稱a與b模n同余，記為a≡bmodn，n稱為模數(shù)。例：17≡2mod5，73≡27mod23顯然，如果a與b模n同余，則必然有n|(a-b)，也可以寫成a-b=kn或a=kn+b，其中k∈Z。同余與模運算2.整數(shù)同余與模運算剩余類由帶余除法的定義可知，任何整數(shù)a除以正整數(shù)n的余數(shù)一定在集合{0,1,2,…,n-1}中，所有整數(shù)根據(jù)模n同余關(guān)系可以分成n個集合，每一個集合中的整數(shù)模n同余，將這樣的集合稱為模n同余類或剩余類，依次記為[0]n,[1]n,[2]n,…,[n-1]n，即[x]n={y|y≡xmodn,y∈Z}，x∈{0,1,2,…,n-1}。同余與模運算2.整數(shù)同余與模運算完全剩余系如果從每一個模n同余類中取一個數(shù)為代表，形成一個集合，此集合稱為模n的完全剩余系，以Zn表示。顯然，Zn最簡單表示就是集合Zn={0,1,2,…,n-1}，這也是最常用的表示。同余與模運算2.整數(shù)同余與模運算模運算綜上，amodn將任一個整數(shù)a映射到Zn={0,1,2,…,n-1}中一個數(shù)，這個數(shù)就是a模n的余數(shù)，amodn稱為模運算。同余與模運算2.整數(shù)同余與模運算模運算的性質(zhì)（其中n＞1）（1）如果n|(a-b)，則a≡bmodn證明：設(shè)y=amodn，w=bmodn，又a=xn+y，b=zn+w，x,y,z,w∈Z，則a-b=(x-z)n+(y-w)因n|(a-b)，所以y-w=0，即a≡bmodn同余與模運算2.整數(shù)同余與模運算模運算的性質(zhì)（其中n＞1）（2）模n同余關(guān)系是整數(shù)間的一種等價關(guān)系，具有等價關(guān)系的三個基本性質(zhì)，即自反性：對任意整數(shù)a，有a≡amodn對稱性：如果a≡bmodn，則b≡amodn傳遞性：如果a≡bmodn且b≡cmodn，則a≡cmodn同余與模運算2.整數(shù)同余與模運算模運算的性質(zhì)（其中n＞1）（3）如果a≡bmodn且c≡dmodn，則a±c≡b±dmodn，ac≡bdmodn。證：因a≡bmodn，可設(shè)a=kn+b;因c≡dmodn，可設(shè)c=tn+d.有a±c=(k±t)n+(b±d)，所以a±c≡b±dmodn；還有ac=ktn2+(kd+bt)n+bd，所以ac≡bdmodn。同余與模運算2.整數(shù)同余與模運算模運算的性質(zhì)（其中n＞1）（4）模運算具有普通運算的性質(zhì)，可交換、結(jié)合、分配，(amodn±bmodn)modn=(a±b)modn(amodn×bmodn)modn=(a×b)modn((a×b)modn±(a×c)modn)modn=(a×(b±c))modn例：已知a=11，b=17，n=9，對性質(zhì)（4）進行驗證同余與模運算2.整數(shù)同余與模運算模運算的性質(zhì)（其中n＞1）（5）加法消去律：如果(a＋b)≡(a＋c)modn，b≡cmodn（消去a）（6）乘法消去律：如果ab≡acmodn且gcd(a,n)=1，則b≡cmodn（消去a）證明：n|((a＋b)-(a＋c)),n|(b-c)，所以b≡cmodn。n|(ab-ac),n|a(b-c)，又gcd(a,n)=1，則n|(b-c)，所以b≡cmodn同余與模運算2.整數(shù)同余與模運算模運算的性質(zhì)（其中n＞1）（7）如果ac≡bdmodn且c≡dmodn及gcd(c,n)=1，則a≡bmodn證明：c≡dmodn，則bc≡bdmodn，又ac≡bdmodn，則ac≡bcmodn，另gcd(c,n)=1，根據(jù)性質(zhì)（6）有a≡bmodn。（8）若a≡bmodn，d|n，d＞0，則a≡bmodd同余與模運算2.整數(shù)同余與模運算由性質(zhì)（4）可知，指數(shù)模運算可以變成模指數(shù)運算，從而使計算得以簡化。例如計算1311mod17可以按如下方式進行：132mod19=17134mod19=(132×132)mod19=(17×17)mod19=4138mod19=(134×134)mod19=(4×4)mod19=161311mod19=(13×132×138)mod19=(13×17×16)mod19=2例如：利用同余演算證明(560-1)是56的倍數(shù)。證明：由于53mod56=125mod56=1356mod56=(53)2mod56=132mod56=1于是560mod56=(56)10mod56=110mod56=1所以560≡1mod56即56|(560-1)，(560-1)是56的倍數(shù)。同余與模運算同余與模運算2.整數(shù)同余與模運算逆元定義：設(shè)a，n∈Z且n＞1，如果存在b∈Z使得a+b≡0modn，則a,b稱為互為模n的加法逆元，記為b≡-amodn。設(shè)a，n∈Z且n＞1，如果存在b∈Z使得ab≡1modn，則a,b稱為互為模n的乘法逆元，記為b≡a-1modn。顯然，對于任何整數(shù)a，其模n的加法逆元總是存在，n-a就是其中的一個，但不能保證任何整數(shù)都有模n的乘法逆元（需滿足一定條件）。同余與模運算2.整數(shù)同余與模運算定理4：設(shè)a，n∈Z，如果gcd(a,n)=1，則存在唯一的b∈Zn，滿足ab≡1modn。證明：任取i,j∈Zn且i≠j，故i?j

modn，又gcd(a,n)=1，根據(jù)性質(zhì)（6）有ai?aj

modn，因此，aZnmodn=Zn，即{amodn,2amodn,…,(n-1)amodn}={1,2,…,n-1}所以1∈aZnmodn，即存在b∈Zn使得abmodn≡1∈aZnmodn由Zn中數(shù)的互異性可知，滿足上面條件的b是唯一的。歐拉（Euler）定理1.歐拉函數(shù)設(shè)n∈Z且n＞1，將小于n且與n互素的正整數(shù)的個數(shù)稱為n的歐拉函數(shù)，記為ψ(n)。例如：ψ(5)=4（4,3,2,1），ψ(6)=2（5,1）ψ(20)=？歐拉（Euler）定理1.歐拉函數(shù)性質(zhì)（1）如果p為素數(shù)，則ψ(p)=p-1證明：設(shè)p=x1α1x2α2…xkαk，p為素數(shù)，則p=1·p，且所有小于p的正整數(shù)都與p互質(zhì)，所以ψ(p)=p-1。例：ψ(5)=4，ψ(7)=6，ψ(11)=10歐拉（Euler）定理1.歐拉函數(shù)通過算術(shù)基本定理可將任意整數(shù)表示成素數(shù)冪的乘積，而素數(shù)的歐拉函數(shù)值易得。下面將探討如何通過素數(shù)來求任意整數(shù)的歐拉函數(shù)。歐拉（Euler）定理2.簡化剩余類簡化剩余類定義：設(shè)N是模n的一個剩余類，若有a∈N，使得gcd(a,n)=1，則稱N是模n的一個簡化剩余類。如，模4的簡化剩余類為={…,-7,-3,1,5,9,…}和={…,-5,-1,3,7,11,…}。證明題：設(shè)N是模n的一個剩余類，若有a∈N，使得gcd(a,n)=1，則對任意b∈N，gcd(b,n)=1。歐拉（Euler）定理2.簡化剩余類歐拉函數(shù)的等價定義：對于正整數(shù)n，若函數(shù)ψ(n)的值等于模n的所有簡化剩余類的個數(shù)，稱ψ(n)為Euler函數(shù)。例如，ψ(2)=1，ψ(3)=2，ψ(4)=2，ψ(7)=6。若p為素數(shù)，則ψ(p)=p-1。歐拉（Euler）定理2.簡化剩余類容易證明，模n的一個完全剩余系中與n互素的數(shù)的個數(shù)就是其所有簡化剩余類的個數(shù)，即ψ(n)就等于模n的一個完全剩余系中與n互素的數(shù)的個數(shù)。特別地，ψ(n)就是模n的最小非負完全剩余系{0,1,2,…,n-1}中與n互素的數(shù)的個數(shù)。（與定義等同）定義：對于正整數(shù)n，從模n的每個簡化剩余類中各取一個數(shù)xi，構(gòu)成一個集合{x1,x2,…,xψ(n)}，稱為模n的一個簡化剩余系。（即gcd(xi,n)=1）

歐拉（Euler）定理3.完全剩余系的判別定理5：整數(shù)集合N是模n的完全剩余系的充分必要條件是：①N中含有n個整數(shù)②N中任何兩個整數(shù)對模n互不同余。證明：若集合N是模n的完全剩余系，由完全剩余系定義可知結(jié)論①與②成立；反之，滿足結(jié)論①與②的一組數(shù)必分別來自模n的每個不同的剩余類，即N構(gòu)成模n的完全剩余系。歐拉（Euler）定理3.完全剩余系的判別定理6：設(shè)m≥1，a,b是整數(shù)，gcd(a,m)=1，{x1,x2,…,xm}是模m的一個完全剩余系，則{ax1+b,ax2+b,…,axm+b}也是模m的一個完全剩余系。證明：只須證明：若axi+b≠axj+b，則axi+b?axj+b(modm)。亦即證明：若axi+b≡axj+b(modm)，則axi+b=axj+b。事實上，若axi+b≡axj+b(modm)，則axi≡axj(modm)。又gcd(a,m)=1，由此及同余的性質(zhì)得到xi≡xj(modm)，由于{x1,x2,…,xm}是模m的一個完全剩余系，因此xi=xj，故有axi+b=axj+b。因此，定理得證。歐拉（Euler）定理3.完全剩余系的判別定理7：設(shè)m1,m2∈N，A∈Z，gcd(A,m1)=1，又設(shè)X={x1,x2,…,xm1},Y={y1,y2,…,ym2}分別是模m1和m2的完全剩余系，則R={Ax+m1y;x∈X,y∈Y}是模m1·m2的一個完全剩余系。證明：由定理5，只須證明：若x’,x’’∈X,y’,y’’∈Y，且Ax’+m1y’≡Ax’’+m1y’’(modm1m2)，則Ax’+m1y’=Ax’’+m1y’’。由同余性質(zhì)（8）以及Ax’+m1y’≡Ax’’+m1y’’(modm1m2)有Ax’+m1y’≡Ax’’+m1y’’modm1，故Ax’≡Ax’’(modm1)→x’≡x’’(modm1)→x’=x’’因x’=x’’，有m1y’≡m1y’’(modm1m2)→y’≡y’’(modm2)→y’=y’’從而Ax’+m1y’=Ax’’+m1y’’。歐拉（Euler）定理3.完全剩余系的判別推論2：若m1,m2∈N，gcd(m1,m2)=1，則當x1，x2分別通過模m1與模m2的完全剩余系時，則m2x1+m1x2通過模m1m2的完全剩余系。證明：將定理7的證明中的條件(A,m2)=1換成(m1,m2)=1既得結(jié)論。歐拉（Euler）定理4.簡化剩余系的判別定理8：設(shè)m1,m2∈N，gcd(m1,m2)=1，又設(shè)X={x1,x2,…,xψ(m1)},Y={y1,y2,…,yψ(m2)}分別是模m1和m2的簡化剩余系，則H={m2x+m1y|x∈X,y∈Y}是模m1·m2的一個簡化剩余系。證明：由推論2，若以X’與Y’分別表示模m1與m2的完全剩余系，使得X?X’與Y?Y’，則H’={m2x+m1y|x∈X’,y∈Y’}是模m1·m2的完全剩余系。因此，令M={H’中所有與m1·m2互素的整數(shù)}，只需證明集合M=H。顯然，H?H’。若m2x+m1y∈M，則gcd(m2x+m1y,m1m2)=1，所以gcd(m2x+m1y,m1)=1，于是gcd(m2x,m1)=1，故gcd(x,m1)=1，因而x∈X。同理，可得y∈Y，因此m2x+m1y∈H。這說明M?H。歐拉（Euler）定理4.簡化剩余系的判別定理8：設(shè)m1,m2∈N，gcd(m1,m2)=1，又設(shè)X={x1,x2,…,xψ(m1)},Y={y1,y2,…,yψ(m2)}分別是模m1和m2的簡化剩余系，則H={m2x+m1y|x∈X,y∈Y}是模m1·m2的一個簡化剩余系。證明：又若m2x+m1y∈H，則x∈X，y∈Y，即gcd(m1,x)=1，gcd(m2,y)=1。由此及gcd(m1,m2)=1，得到gcd(m2x+m1y,m1)=gcd(m2x,m1)=1以及gcd(m2x+m1y,m2)=gcd(m1y,m2)=1因為m1與m2互素，所以gcd(m2x+m1y,m1m2)=1，于是m2x+m1y∈M。因此H?M。得結(jié)論H=M。歐拉（Euler）定理4.簡化剩余系的判別定理9：設(shè)m1,m2∈N，gcd(m1,m2)=1，則ψ(m1m2)=ψ(m1)ψ(m2)。證明：由定理8知，若x1,x2分別通過m1,m2的簡化剩余系，則m2x1+m1x2通過m1m2的簡化剩余系，即m2x1+m1x2通過ψ(m1m2)個整數(shù)。又由于x1通過ψ(m1)個整數(shù)，x2通過ψ(m2)個整數(shù)，因此m2x1+m1x2通過ψ(m1)ψ(m2)個整數(shù)，故ψ(m1m2)=ψ(m1)ψ(m2)。歐拉（Euler）定理5.ψ(n)的求法定理10：設(shè)n是正整數(shù)，p1,p2,…,pk是n的全部素因數(shù)，則證明：設(shè)n的標準分解式是，由定理9得對任意素數(shù)p，ψ(pα)等于數(shù)列1,2,…,pα中與pα（也就是與p）互素的整數(shù)的個數(shù)，因此證畢。由上知，ψ(n)=1的充要條件是n=1或2。歐拉（Euler）定理6.歐拉定理歐拉定理：設(shè)m是正整數(shù)，且gcd(a,m)=1，則aψ(m)≡1

modm證明：設(shè){x1,x2,…,xψ(m)}是模m的一個簡化剩余系，由于gcd(a,m)=1，故{ax1,ax2,…,axψ(m)}也是模m的簡化剩余系，因此ax1ax2…axψ(m)≡x1x2…xψ(m)modm（模運算的性質(zhì)可得）即aψ(m)x1x2…xψ(m)≡x1x2…xψ(m)modm由于gcd(x1x2…xψ(m),m)=1，所以（乘法消去律）aψ(m)≡1

modm。歐拉（Euler）定理6.歐拉定理歐拉定理的證明是運用整體化思想方法的典范。由于模m的任意兩個簡化剩余系{a1,a2,…,aψ(m)}與{b1,b2,…,bψ(m)}具有整體性質(zhì)，歐拉巧妙運用這個性質(zhì)證得了定理。歐拉（Euler）定理6.歐拉定理推論（1）Fermat（費爾馬）小定理設(shè)m是素數(shù)，a是與m互素的整數(shù)，則am-1≡1modm，從而對任意整數(shù)a有am≡amodm證明：對任意整數(shù)a，若gcd(a,m)=1，則由歐拉定理得到aψ(m)=am-1≡1modm，于是對任意整數(shù)a有am≡amodm若gcd(a,m)>1，則m|a，當然也有am≡0≡amodm故：am≡amodm歐拉（Euler）定理6.歐拉定理推論（2）若gcd(a,m)=1，有aψ(m)≡1modm，因a,m互素，故有aψ(m)-1≡a-1modm，aψ(m)+1≡a

modm；對于m為素數(shù),ψ(m)=m-1,代入有am≡amodm,am-2≡a-1

modm。（3）若m=pq且p和q為素數(shù)，a∈Z，如果gcd(a,m)=p或q，則同樣有aψ(m)+1≡amodm。加解密運算中的幾個常用算法定理：對任意兩個整數(shù)a和b，不妨設(shè)a>b>0，有g(shù)cd(a,b)=gcd(b,amodb)（被除數(shù)與除數(shù)的最大公因子和除數(shù)與余數(shù)的最大公因子相同）證明：對于任意整數(shù)a和b，存在整數(shù)k滿足a=kb+amodb設(shè)d是a與b的任一公因子，故d|a且d|b，所以d|(a-kb)，即d|(amodb)，因此，d是b與amodb的公因子。同理，若d是b與amodb的公因子，則d也是a與b的公因子。所以a與b的全部公因子同b與amodb的全部公因子完全相同，因此他們的最大公因子也相同，即gcd(a,b)=gcd(b,amodb)。1.基本歐幾里得算法（求最大公因子）計算gcd(a,b)，等價于計算gcd(b,r0)，r0=amodb計算gcd(b,r0)，等價于計算gcd(r0,r1)，r1=bmodr0計算gcd(r0,r1)，等價于計算gcd(r1,r2)，r2=bmodr1…如此反復(fù)，由于r0>r1>r2>…，則最終的余數(shù)rn+1=0當余數(shù)為0時，有g(shù)cd(rn,0)=rn因此：gcd(a,b)=gcd(rn,0)=rn1.基本歐幾里得算法（求最大公因子）1.基本歐幾里得算法（求最大公因子）例：求1970和1066的最大公因子。1970=1×1066+904，1066=1×904+162，904=5×162+94，162=1×94+68，94=1×68+26，68=2×26+16，26=1×16+10，16=1×10+6，10=1×6+4，6=1×4+2，4=2×2+0。顯然gcd(2,0)=2，因此gcd(1970,1066)=2。1.基本歐幾里得算法（求最大公因子）這個過程又稱為輾轉(zhuǎn)相除法，表示如下：a=k0b+r0b=k1r0+r1r0=k2r1+r2…rn-2=knrn-1+rnrn-1=kn+1rn+0其中，r0=amodb，r1=bmodr0，ri=ri-2modri-1(i=2,3,…,n)。由于r0>r1>r2>…≥0且他們皆為整數(shù)，因此在經(jīng)過有限步后余數(shù)必為0。當余數(shù)為0時，有g(shù)cd(rn,0)=rn。倒推回來，可得：rn=gcd(rn,0)=gcd(rn-1,rn)=gcd(rn-2,rn-1)=…=gcd(r0,r1)=gcd(b,r0)=gcd(a,b)1.基本歐幾里得算法（求最大公因子）說明：基本歐幾里得算法的假設(shè)是a>b>0，如果a、b中有負整數(shù)，則可通過其絕對值來求最大公因子，若其中一個為0，則最大公因子為非0的那一個，若兩個都為0，則最大公因子無意義。2.擴展歐幾里得算法（求乘法逆元）回顧乘法逆元的定義：設(shè)a,b,n為整數(shù)且n＞1，如果ab≡1modn，則a,b稱為互為模n的乘法逆元，記為b≡a-1modn。如何求乘法逆元？一種方法：由歐拉定理，若整數(shù)a與n互素，那么aψ(n)-1≡a-1modn。如果n是素數(shù)，則ψ(n)=n-1；但如果n不是素數(shù)，則不容易求出ψ(n)。下面介紹另一種常用方法。2.擴展歐幾里得算法（求乘法逆元）由歐幾里得算法可知：gcd(a,b)=rn由整個過程的倒數(shù)第二行可得：rn=rn-2-rn-1kn再由倒數(shù)第三行可得：rn-1=rn-3-rn-2kn-1，代入上式得：gcd(a,b)=(1+knkn-1)rn-2-knrn-3再由倒數(shù)第四行可得：rn-2=rn-4-rn-3kn-2代入上式得：。。。如此下去，最終可將gcd(a,b)表示出a和b的關(guān)于k0到kn的整系數(shù)線性組合，即sa+tb=gcd(a,b)。如果a與b互素，即gcd(a,b)=1，則有1=sa+tb，所以sa≡1modb，因此可求得a的乘法逆元：s≡a-1modb。整理：若r2=0，gcd(a,b)=r1，則：r1=(1+k0k1)b-k1a，s=-k1若r3=0，gcd(a,b)=r2，則：r2=(1+k1k2)a-(k0(1+k1k2)+k2)b，s=(1+k1k2)若r4=0，gcd(a,b)=r3，則：r3=((1+k2k3)+k0(k3+k1(1+k2k3)))b-(k3+k1(1+k2k3))a，s=-(k3+k1(1+k2k3))若r5=0，gcd(a,b)=r4，則：r4=((1+k3k4)+k1(k4+k2(1+k3k4)))a-(k0((1+k3k4)+k1(k4+k2(1+k3k4)))+(k4+k2(1+k3k4)))bs=(1+k3k4)+k1(k4+k2(1+k3k4))。。。例，設(shè)a=127，n=57，求a-1modn127=2×57+1357=4×13+513=2×5+35=1×3+23=1×2+12=2×1+0gcd(127,57)=gcd(1,0)=1例中r5=0，gcd(a,b)=r4=1。k0=2，k1=4，k2=2，k3=1，k4=1s=(1+k3k4)+k1(k4+k2(1+k3k4))=(1+1×1)+4(1+2(1+1×1))=22。驗證：samodn=22×127mod57=2794mod57=12794=49×57+1例，設(shè)a=83，n=37，求a-1modn83=2×37+937=4×9+19=9×1+0gcd(83,37)=gcd(1,0)=1例中r2=0，gcd(a,b)=r1=1。k0=2，k1=4，k2=9s=-k1=-4驗證：samodn=-4×83mod37=-332mod37=1-332=-9×37+1例，設(shè)a=8191，n=1975，求a-1modn8191=4×1975+2911975=6×291+229291=1×229+62229=3×62+4362=1×43+1943=2×19+519=3×5+45=1×4+14=4×1+0gcd(8191,1975)=gcd(1,0)=13.快速指數(shù)算法在RSA等公鑰密碼算法中，經(jīng)常面臨著需要計算大量的底數(shù)和指數(shù)均為大整數(shù)的模冪運算。如果按照模冪運算的含義直接計算，一方面可能由于中間結(jié)果過大而超過計算機允許的整數(shù)取值范圍，一方面工作量過大。3.快速指數(shù)算法從兩個方面處理這個問題。一是利用模運算的性質(zhì)：ammodn=(aumodn×avmodn)modn，m=u+v。二是考慮如何提高指數(shù)運算的有效性，例如通過計算出x,x2,x4,x8,x16，可方便組合出指數(shù)1到31之間的任何一個整數(shù)次冪，并且只需4次乘法運算即可得到答案。3.快速指數(shù)算法求am

modn的快速指數(shù)算法：將m表示成二進制的形式：m=(bkbk-1…b0)2，即因此，有所以：3.快速指數(shù)算法根據(jù)以上原理，可得計算am

modn的快速指數(shù)算法如下：c=0;d=1;fori=kdownto0do{c=2×c;d=(d×d)modn;ifbi=1then{c=c+1;d=(d×a)modn;}}Returnd;其中，變量c表示指數(shù)的變化情況，終值為m變量d表示相對于指數(shù)c的冪模n的變化情況，終值為am

modn3.快速指數(shù)算法例：用快速指數(shù)算法計算20072008mod20092008=(11111011000)2i109876543210bi11111011000c013715316212525150210042008d120072001188113857401152169013968613691773中國剩余定理1.n次同余方程首先給出1元n次同余方程的定義及其解的情況。定義：設(shè)f(x)=anxn+…+a1x+a0是未知數(shù)x的整系數(shù)多項式，稱f(x)≡0modm是關(guān)于未知數(shù)x的模m的一元同余方程，簡稱模m的同余方程。若an?0modm，則稱式f(x)≡0modm為n次同余方程。1.n次同余方程設(shè)a是整數(shù)，當x=a時，方程f(x)=anxn+…+a1x+a0≡0modm成立，則稱a是方程f(x)≡0modm的解。問題：當x=a時，x=a+m，x=a+2m，…等是否是方程的解？分析：an(a+qm)nmodm=(anmodm×(a+qm)nmodm)modm=(anmodm×((a+qm)modm)nmodm)modm=(anmodm×((amodm+qmmodm)modm)nmodm)modm=(anmodm×((amodm+0)modm)nmodm)modm=(anmodm×anmodm)modm=ananmodm1.n次同余方程對于同余方程：f(x)=anxn+…+a1x+a0≡0modm由分析可知，當x=a是方程的解時，x=a+qm(a∈Z)也是方程的解。針對形如式x=a+qm的解，可表示成同余等式：x≡amodm。因此，同余方程的一個解就是模m的一個同余類?？芍?，同余方程的解數(shù)指其關(guān)于模m互不同余的所有解的個數(shù)。1.n次同余方程同余方程的解的個數(shù)：模m的剩余類只有m個，因此，模m的同余方程的解數(shù)不會超過m。在模m的任意取定的一組完全剩余系中，適合同余方程的解的個數(shù)就是同余方程的解數(shù)。特別的，可以通過將整數(shù)x=0,1,…,m-1逐個代入同余方程驗證其是否成立的方法找出其全部解。2.一次同余方程定義：設(shè)a，b是整數(shù)，x是未知數(shù)，則ax≡bmodm,a?0modm稱為模m的一次同余方程。下面分析一次同余方程的解的情況。2.一次同余方程定理：設(shè)a，b是整數(shù)，d=gcd(a,m)，a?0modm，則方程ax≡bmodm有解的充分必要條件是d|b。若方程有解，則恰有d=gcd(a,m)個解。證明：必要性若同余方程有解x≡tmodm，則必定存在整數(shù)y，使得b-ax=my，即ax+my=b。因為d|a，d|m，所以d|b。充分性由于d=gcd(a,m)，根據(jù)最大公因數(shù)的性質(zhì)（2），存在整數(shù)u,v，使得au+mv=d。由于d|b，則有整數(shù)c使得b=cd。于是a(cu)+m(cv)=cd=b，因而方程有解x≡cumodm。（下面探討解的個數(shù)）2.一次同余方程定理：設(shè)a，b是整數(shù)，d=gcd(a,m)，a?0modm，則方程ax≡bmodm有解的充分必要條件是d|b。若方程有解，則恰有d=gcd(a,m)個解。證明：若同余方程ax≡bmodm有解x0，則存在y0，使得x0與y0是不定方程ax+my=b的特解，且其全部整數(shù)解是顯然，此式所確定的x都滿足方程ax≡bmodm。2.一次同余方程定理：設(shè)a，b是整數(shù)，d=gcd(a,m)，a?0modm，則方程ax≡bmodm有解的充分必要條件是d|b。若方程有解，則恰有d=gcd(a,m)個解。證明：由于d=gcd(a,m)，令t=dq+r（q∈Z，r=0,1,2,…,d-1），代入全部整數(shù)解式中，得容易驗證，當r=0,1,2,…,d-1時，相應(yīng)的解對于模m是兩兩互不同余的，所以同余方程ax≡bmodm恰有d個解。2.一次同余方程由定理可知，當d=gcd(a,m)且d|b時同余方程有解，此時求解同余方程ax≡bmodm化歸為求解同余方程由此可知，一次同余方程的求解問題轉(zhuǎn)換成求解形如同余方程ax≡bmodm，gcd(a,m)=1，a?0modm的問題。說明：方程ax≡bmodm和的解數(shù)與模不同，所以兩個方程不是同解方程。對于此同余方程，有四種常用的求解方法。例，求解方程：（1）16x≡18mod22計算d=gcd(a,m)=gcd(16,22)=2，所以d|b，則方程有解。因d=2，所以方程有兩個解。窮舉法：將x=0,1,2,…,21分別代入方程，計算確認，發(fā)現(xiàn)x=8和x=19是方程的解，所以方程的解為：x≡8mod22和x≡19mod22（2）8x≡9mod11（(16/d)x≡(18/d)mod(22/d)）計算gcd(8,11)=1，則方程有一個解。窮舉法：將x=0,1,2,…,10分別代入方程，只有當x=8時是方程的解，所以方程的解為x≡8mod112.一次同余方程（1）窮舉法令未知數(shù)x依次取x=0,1,2,…,m-1并代入方程進行驗證，若有整數(shù)解x=r時方程成立，則x≡rmodm即為方程的解。當模m的數(shù)值很大時，計算了較大。（2）輾轉(zhuǎn)相除法由于gcd(a,m)=1，輾轉(zhuǎn)相除求出適合au+mv=1的整數(shù)u和v，此時，x≡bumodm即為方程的整數(shù)解。（3）公式法由于gcd(a,m)=1，根據(jù)Euler定理可知有aψ(m)≡1modm，其中ψ(m)是歐拉函數(shù)。由原方程可得ax≡b≡aψ(m)bmodm，因gcd(a,m)=1，故x≡aψ(m)-1bmodm，即為方程的解2.一次同余方程（4）分數(shù)法首先，將同余方程寫成的形式，然后在

的分子和分母位置上加上m的適當倍數(shù)（或者分子分母同時乘以一個與m互素的非零整數(shù)），使得通過約分后（或者分子分母同時模m后）所得新分數(shù)的分母的絕對值逐漸變小。如果變形后的新分母為1或-1，分子為r，則此時可得方程的解為x≡rmodm或x≡-rmodm此法在一次同余方程的求解中往往比較有效。2.一次同余方程例，解同余方程8x≡9mod11.解：此時gcd(8,11)=1，同余方程只有一個解。（1）窮舉法將x=0,1,2,…,10分別代入方程，只有當x=8時是方程的解。故x≡8mod11（2）輾轉(zhuǎn)相除法由于11=1×8+3,8=2×3+2,3=1×2+1,經(jīng)逆推計算可得(-4)×8+3×11=1,即8×(-4)×9+11×3×9=9，因此x≡(-4)×9≡8mod11是同余方程的解。2.一次同余方程例解同余方程8x≡9mod11.解此時gcd(8,11)=1，同余方程只有一個解。（3）公式法因為11是素數(shù)，ψ(11)=10，故x≡9×89≡8mod11是同余方程的解。（4）分數(shù)法3.中國剩余定理我國古代的孫子算經(jīng)中的問題：今有物不知其數(shù)，三三數(shù)之剩二，x≡2mod3五五數(shù)之剩三，x≡3mod5七七數(shù)之剩二，x≡2mod7問物幾何？求x？3.中國剩余定理定義：設(shè)n1,n2,…,nk是大于1的正整數(shù)，a1,a2,…,ak是整數(shù)，由k(k≥2)個一元一次同余方程聯(lián)立而成的同余式稱為一元一次同余方程組。設(shè)x=a是同余方程組的解，設(shè)M=[n1,n2,…,nk]（n1到nk的最小公倍數(shù)），則x=a+qM(q∈Z)都是方程組的公共解，記為x≡amodM，因此方程組的解是模M的一個剩余類。3.中國剩余定理中國剩余定理：設(shè)n1,n2,…,nk是兩兩互素的正整數(shù)，那么對任意的整數(shù)a1,a2,…,ak，一次同余方程組x≡aimodni,i=1,2,…,k在同余意義下必有唯一解，且這個解是其中，證明：先證同余方程不會有多個解。設(shè)有兩個解c1和c2，那么對所有ni，都有c1≡c2≡aimodni，故c1-c2≡0modni，ni|(c1-c2)。又因為所有的ni兩兩互素，所以N|(c1-c2)，即c1≡c2modN，也就是c1、c2在modN下同余，即在模N同余意義下是同一個解，因此，同余方程組在不可能有多個解。3.中國剩余定理中國剩余定理：設(shè)n1,n2,…,nk是兩兩互素的正整數(shù)，那么對任意的整數(shù)a1,a2,…,ak，一次同余方程組x≡aimodni,i=1,2,…,k在同余意義下必有唯一解，且這個解是其中，證明：下證為方程的解。3.中國剩余定理證明：ni與Ni互素，因此Ni關(guān)于模ni的逆Ni-1存在。另一方面且若j≠i，則nj|Ni。因此所以（性質(zhì)：若a≡bmodn，d|n，d＞0，則a≡bmodd）是此同余方程組的解。得證3.中國剩余定理例，解同余方程組3.中國剩余定理解：方程組中，n1=3,n2=5,n3=7,n4=11，兩兩互素，滿足中國剩余定理的條件。a1=1,a2=4,a3=2,a4=9。N1=5×7×11,N2=3×7×11,N3=3×5×11,N4=3×5×7下面計算N1,N2,N3,N4的逆。由于N1mod3≡2×1×2≡1，故可取N1-1=1mod3=1；由于N2mod5≡3×2×1≡1，故可取N2-1=1mod5=1；由于N3mod7≡3×5×4≡4，故可取N3-1=2mod7=2；由于N4mod11≡3×5×7≡6，故可取N4-1=2mod3=2；x≡N1N1-1a1+N2N2-1a2+N3N3-1a3+N4N4-1a4≡(5×7×11)×1×1+(3×7×11)×1×(-1)+(3×5×11)×2×2+(3×5×7)×2×(-2)(mod3×5×7×11)≡385-231+660-420≡394mod11553.中國剩余定理練習題：（1）解同余方程：256x≡123mod337（2）有一隊士兵，若三人一組，則余1人；若五人一組，則缺2人；若十一人一組，則余3人。已知士兵人數(shù)不超過170人，問這隊士兵的人數(shù)是多少？模為素數(shù)的二次剩余二次同余方程的一般形式是ax2+bx+c≡0modm，a?0modm設(shè)m的分解式是m=p1α1p2α2…pkαk，可證二次同余方程有解的充要條件是同余方程ax2+bx+c≡0modpiαi，i=1,2,…,k有解。模為素數(shù)的二次剩余利用同余式的性質(zhì)，同余方程ax2+bx+c≡0modpiαi可化歸為求解ax2+bx+c≡0modp，p為素數(shù)的同余方程。（1）如果p=2，根據(jù)剩余類的定義，直接驗證x≡0或1modp。（2）如果gcd(a,p)=p，則p|a，同余方程成為一次方程。綜上，只須考察p>2且gcd(a,p)=1的情形。模為素數(shù)的二次剩余針對方程ax2+bx+c≡0modp，p>2，p為素數(shù)，a,p互素。因gcd(a,p)=1，所以gcd(4a,p)=1，方程等價于4a2x2+4abx+4ac≡0modp，即(2ax+b)2≡b2-4acmodp通過變量替換y≡2ax+bmodp和k=b2-4ac，將方程歸結(jié)為同余方程y2≡kmodp。當k≡0modp時，同余方程只有解y≡0modp，只需考慮p與k互素（p為素數(shù)）的情形。模為素數(shù)的二次剩余定義：對于奇素數(shù)p（大于2的素數(shù)，如3,5,7,11等）和整數(shù)a，gcd(a,p)=1，若同余方程x2≡amodp有解，則稱a是模p的二次剩余，記為a∈QR(P)，否則，稱a是模p的二次非剩余，記為a∈QNR(P)。模為素數(shù)的二次剩余例如：設(shè)二次同余方程x2≡amodp，其中p=7當a=1，x2≡1mod7，求得x≡1mod7，x≡6mod7;當a=2，x2≡2mod7，求得x≡3mod7，x≡4mod7;當a=3，x2≡3mod7，無解;

當a=4，x2≡4mod7，求得x≡2mod7，x≡5mod7;當a=5，x2≡5mod7，無解;當a=6，x2≡6mod7，無解。根據(jù)定義：（1）a=1,2,4是模7的二次剩余，（2）a=3,5,6是模7的二次非剩余。模為素數(shù)的二次剩余進一步討論：當a=8，x2≡8mod7≡(1+7)mod7≡1mod7，解同a=1的情況；當a=9，x2≡9mod7≡(2+7)mod7≡2mod7，解同a=2的情況；。。。顯然，對于同余方程x2≡amodp，若a1是模p的二次剩余（或二次非剩余），則a1+qp(q∈Z)是模p的二次剩余（或二次非剩余）。即所有與a1模p同余的數(shù)都是模p的二次剩余（二次非剩余）。由此可知，模p的一個二次剩余（或二次非剩余）實質(zhì)上就是模p的一個簡化剩余類。模為素數(shù)的二次剩余例如：設(shè)二次同余方程x2≡amodp，其中p=7x2≡1mod7，有解x≡1mod7和x≡6mod7;x2≡2mod7，有解x≡3mod7和x≡4mod7;x2≡3mod7，無解;

x2≡4mod7，有解x≡2mod7和x≡5mod7;x2≡5mod7，無解;x2≡6mod7，無解。模7的二次剩余為1,2,4，則1+7q,2+7q,4+7q（q∈Z）都是模7的二次剩余，也就是簡化剩余類[1]7,[2]7,[4]7都是模7的二次剩余。模為素數(shù)的二次剩余一個結(jié)論：模p的二次剩余的全體和二次非剩余的全體數(shù)量相同，都是(p-1)/2=3個。模為素數(shù)的二次剩余說明：對于二次同余方程x2≡amodp如果有解x≡bmodp，則另一個解x≡-bmodp是不同的解。假設(shè)是同一個解，即b≡-bmodp，即2b≡0modp則上式只有在b=0或p|b時成立，推得p|a，這與定義中的前提假設(shè)矛盾，故b?-bmodp。因此x≡±bmodp是方程的兩個不同的解