中国剩余定理及其应用 上海交通大学数学科学学院章璞 4.1整数版中国剩余定理 《周鹿算经》（约成书于公元前1世纪）、《九章算术》（约成书于1世纪）、和《孙子算 经》（约成书于4、5世纪）是中国古代三大数学名作，其作者都已无从考证.《孙子算经》中 物不知其数 题：“今有物不知其数 数之剩 五五数之剩 ,七七数之剩二，问 物几何”答日：“二十三”.《孙子算经》不仅提供了答案，而且还给出了解法 这个问题的一般形式是求同余方程组 x三a1(modm) =a2 (mod m2) () (x三an(mod ma) 的最小正整数解，其中m1,…,mm是两两互素的整数，a1,…,@n∈2.求解这个同余方稻 组是件不平凡的事情.下面是一般的解法.解法的思路是对每个1≤i≤先解特殊情形 x=1(modm),x=0(modm》,Vj≠i.然后再将这些特解适当拼凑起来而得一般的 解.熟悉Lagrange插值公式的读者会发现这两个问题解法的思路是完全一样的. 因为m,卫m)=1故存在 ne(TIm)z 使得 s+=1,1≤i≤n 即 r=1 (mod mi); r=0(modm,j≠i 令 T=a1Th+··+anTn 于是对任一我们有 r-a=a(-1+Πa=a(-1)0(modm
1 •Iê{½n9ŸA^ ˛°œåÆÍÆâÆÆ Ÿ‚ 4.1 Íá•Iê{½n 5±é²6(§÷u˙c1V)!5 Ÿé‚6(§÷u1V)!⁄5öfé ²6(§÷u4!5V)¥•IìnåÍƶä, Ÿäˆ—ÆÃly.5öfé²6• k/‘ÿŸÍ0òKµ/8k‘ÿŸÍ,nnÍÉê, ÍÉên,‘‘ÍÉê,Ø ‘A¤.0âµ/õn0.5öfé²6ÿ=J¯ âY, ÖÑâ— ){. ˘áØKòÑ/™¥¶”{êß| x ≡ a1 (mod m1) x ≡ a2 (mod m2) . . . x ≡ an (mod mn) (∗) ÅÍ), Ÿ•m1, · · · , mn¥¸¸pÉÍ,a1, · · · , an ∈ Z. ¶)˘á”{êß |¥áÿ²ÖØú. e°¥òÑ){.){g¥¥Èzá1 ≤ i ≤ nk)Aœú/: x ≡ 1 (mod mi), x ≡ 0 (mod mj ), ∀ j 6= i.,2Ú˘ A)·©nÂ5 òÑ ).ŸGLagrangeä˙™÷ˆ¨uy˘¸áØK){g¥¥ ò. œè(mi , Q j6=i mj ) = 1,3 si ∈ miZ, ri ∈ ( Y j6=i mj )Z (1) ¶ si + ri = 1, 1 ≤ i ≤ n. (2) = ri ≡ 1 (mod mi); ri ≡ 0 (mod mj ), ∀ j 6= i. - r = a1r1 + · · · + anrn. (3) u¥È?òi·Çk r − ai = ai(ri − 1) + Y j6=i aj rj ≡ ai(ri − 1) ≡ 0 (mod mi),
2 也就是说r是同余方程组()的一个整数解.设x是()的任一整数解则r-r三0(modm,)1≤ i≤n,即x-r能被任一m,整除.因为m1,…,mn两两互素，故x-r能被m1…mn整除.于是 得到(*)的全部整数解为 r+tm1.,,mm.Vt∈Z. (4) 我们用剩余类环的语言重新表述一下上述问题和解答.设m1,·,m是两两互素的整 数.不难看出 T:Zm1mt-→Zm⊕…⊕Znm （你，…， 是环的单同态（注意上述每个的意义不同，指在不同的剩余类环中的元），而同余方程组()有 整数解恰好是说π是满同态，即π是环同构。 具体到“物不知其数”一题，即要解同余方程组 r=2 (mod 3) r三3(mod5) x=2(mod7), 即m1=3,m2=5,mg=7:@1=2a2=3.ag=2.因为(3,5×7=35)=1，(5,3×7= 21)=1,(亿，3×5=15)=1故由辗转相除法可知 1=3×(-23)+2×35 {1=5×(-4)+1×21 1=7×(-2)+1×15 所以得到一组 1=2×35=70,2=1×21=21,r3=1×15=15. 于是得到特解 r=2×70+3×21+2×15=233 从而“物不知其数”一题的整数解集为233+105Z.而最小正整数解为233-2×105=23. 这个算法被程大位(1533-1606，珠算家：今黄山市电溪人)在《算法统宗》(1593)一书中用歌 诀给出 三人同行七十稀， 五树梅花什一支 七子团圆月正半。 除百零五便得知
2 è“¥`r¥”{êß|(∗)òáÍ). x¥(∗)?òÍ).Kx−r ≡ 0 (mod mi), 1 ≤ i ≤ n, =x − rU?òmiÿ. œèm1, · · · , mn¸¸pÉ,x − rUm1 · · · mnÿ. u¥ (∗) ‹Í)è r + tm1 · · · mn, ∀ t ∈ Z. (4) ·Ç^ê{aÇäÛ#L„òe˛„ØK⁄)â.m1, · · · , mn¥¸¸pÉ Í. ÿJw— π : Zm1···mn −→ Zm1 ⊕ · · · ⊕ Zmn r¯ 7→ (¯r, · · · , r¯) ¥Ç¸”(5ø˛„zár¯ø¬ÿ”,ç3ÿ”ê{aÇ•). ”{êß|(∗)k Í)T–¥`π¥˜”,=π¥Ç”. ‰N/‘ÿŸÍ0òK, =á)”{êß| x ≡ 2 (mod 3) x ≡ 3 (mod 5) x ≡ 2 (mod 7), =m1 = 3, m2 = 5, m3 = 7; a1 = 2, a2 = 3, a3 = 2. œè(3, 5 × 7 = 35) = 1, (5, 3 × 7 = 21) = 1, (7, 3 × 5 = 15) = 1 dŒ=Éÿ{å 1 = 3 × (−23) + 2 × 35 1 = 5 × (−4) + 1 × 21 1 = 7 × (−2) + 1 × 15 §±ò| r1 = 2 × 35 = 70, r2 = 1 × 21 = 21, r3 = 1 × 15 = 15. u¥A) r = 2 × 70 + 3 × 21 + 2 × 15 = 233. l /‘ÿŸÍ0òKÍ)8è233 + 105Z, ÅÍ)è233 − 2 × 105 = 23. ˘áé{ßå†(1533-1606, æé[; 8ëϽÙM<)35é{⁄m6(1593) ò÷•^y ¸â— n<”1‘õD, ‰rsˆò|. ‘fÏ å, ÿz" B.
其中“三人“指m=3“七十稀”指1二70，“五树”指 2=5“甘一支”指2=2 “七子”指m=7,“月正半”指=15.而最后一句是指由此得到的解，=233模105便得 到最小正整数解。 当然可以取另外一组 3满足(1)和(2而得到相同的最小正整数解.程大位取(1,2，r3) (70,21,15),大约是为了歌诀的琅琅上口 4.2环论版中国剩余定理 现在我们将上述问愿和解法推广到一般的环上。它被国际数学界称为中国剩余定 理(Chinese Remainder Theorem..简称CRT). 以下的环是指有单位元的非零环环R的理想和J称为互素，如果I+J=R当R=Z时 存在唯一的正整数m和n使得I=mZ,J=nZ.此时I和，J互素当且仅当m和n互素. 定理4.1（中国剩余定理）设1，，1，均为有单位元的非零环的理想并且两两互素， 则有环同构 r:R/In…nIn)≌r/h⊕…⊕R/In r+hn…nn→r+h,…,r+1n) 证因为山n…n1m,Vi,所以x是定义合理的，并且容易看出x是单同态.故只 要证x为满射：即对任意一组a1,…,an∈R,要找到r∈R使得(r+山1，…，r+1n)=(a1+ I1.,.,a。+I).即 r+h=a1+,在/1 r+=a2+2,在2/2 r+1n=an+In,在Rn/n 换言之，对任意一组a1,…,an∈R,要找到 x-a1∈11 2-d2 EI2 () I-an EIn 在中的解所以这条定理关健之处与上述整数版中国剩余定理完全相同，而且下面解法的 要点也完全相同， 因为 R=R2=(1+2)(+1s)=+h3+21+23c+23R
3 Ÿ•/n<0çm1 = 3,/‘õD0çr1 = 70,/ ‰0çm2 = 5,/ˆò|0çr2 = 21, /‘f0çm3 = 7,/å0çr3 = 15. ÅòÈ¥çdd)r = 233 105B ÅÍ). ,,å±, ò|r1, r2, r3˜v(1)⁄(2) É”ÅÍ). ßå†(r1, r2, r3) = (70, 21, 15), å¥è y¸FF˛ù. 4.2 Çÿá•Iê{½n y3·ÇÚ˛„ØK⁄){Ì2òÑDz. ßISÍÆ.°è•Iê{½ n(Chinese Remainder Theorem.{°CRT). ±eÇ¥çk¸†ö"Ç. ÇRnéI⁄J°èpÉ,XJI+J = R.R = Zû 3çòÍm⁄n¶I = mZ, J = nZ. dûI⁄JpÉÖ=m⁄npÉ. ½n4.1 (•Iê{½n) I1, · · · , In˛èk¸†ö"ÇRnéøÖ¸¸pÉ. KkÇ” π : R/(I1 ∩ · · · ∩ In) ∼= R/I1 ⊕ · · · ⊕ R/In r + I1 ∩ · · · ∩ In 7→ (r + I1, · · · , r + In). y œèI1 ∩ · · · ∩ In ⊆ Ii , ∀ i, §±π¥½¬‹n,øÖN¥w—π¥¸”.ê áyπè˜:=È?øò|a1, · · · , an ∈ R,áÈr ∈ R¶(r + I1, · · · , r + In) = (a1 + I1, · · · , an + In), = r + I1 = a1 + I1, 3 R1/I1, r + I2 = a2 + I2, 3 R2/I2, . . . r + In = an + In, 3 Rn/In. ÜÛÉ, È?øò|a1, · · · , an ∈ R,áÈ x − a1 ∈ I1 x − a2 ∈ I2 . . . x − an ∈ In (∗∗) 3R•).§±˘^½n'ÖÉ?ܲ„Íá•Iê{½n É”, Öe°){ á:è É”. œè R = R 2 = (I1 + I2)(I1 + I3) = I 2 1 + I1I3 + I2I1 + I2I3 ⊆ I1 + I2I3 ⊆ R
由此即得1+23=R再将1+23与1+1相乘，类似上面的讨论即得1+2山4=R 重复这一过程最后得到+2…1n=R完全类似地我们得到 4+Π马=i=1…,n 由此即知存在 e。reΠ， 使得 1=所+n,i=1,…,n 于是对任一我们有 r-1∈I. ne1,j≠i 令 r=a1n+…+anrn 则对任一我们有 r-a=a,:-)+Πa ∈a(r,-1)+1 e 也就是说，r是(*)的一个解.证毕 4.3在“秘密共享”中的应用 中国剩余定理是“秘密共享”问题经常使用的数学模型.假设有一秘密（通常称为主 秘钥).要求n个人联手才能解开，而任何n一1个人联手都解不开主秘钥.这里“解不开”的 感思是指在现有的计算条件下，要解开主秘钥需要很长时间，例如上万年 将主秘钥数字化以后设为自然数S.取定n个互素的大数m1,…,m:使得S小于这n个 数的积并且大于其中任意n-1个数的积，并将这n个数公开.用每个m去除S得到a4,0≤ a1≤m一1，i=1,…,n.这个计算过程是快的.将这个数a:给第i个人，也就是说地（他）享有 复 任何n-1个人联手，例如已知a1,…,a-1,虽然也可得到r=a1+…+an-1- 而且S也网样满足S=T+tm1…m-1,其中1∈Z.但由于S>m1…ma-1,S不能够被 唯一地恢复（这与n个人联手的情形不同，国为那时S<m1…mn,故S能够被唯一地恢复）】 因为mn很大，要从区间(m …m-l,m1 …mn-1mn)中逐一尝试得到主秘钥S,要花很长时
4 dd=I1 + I2I3 = R.2ÚI1 + I2I3ÜI1 + I4ɶ,aq˛°?ÿ=I1 + I2I3I4 = R. E˘òLßÅI1 + I2 · · · In = R. aq/·Ç Ii + Y j6=i Ij = R, i = 1, · · · , n. dd=3 si ∈ Ii , ri ∈ Y j6=i Ij , ¶ 1 = si + ri , i = 1, · · · , n. u¥È?òi·Çk ri − 1 ∈ Ii , ri ∈ Ij , ∀ j 6= i. - r = a1r1 + · · · + anrn. KÈ?òi·Çk r − ai = ai(ri − 1) + Y j6=i aj rj ∈ ai(ri − 1) + Ii ∈ Ii . è“¥`, r¥(∗∗)òá). y.. 4.3 3/ìóê0•A^∗ •Iê{½n¥/ìóê0ØK²~¶^ÍÆ .. bkòìó(œ~°èà ì).á¶ná m1 · · · mn−1, SÿU çò/°E(˘Üná<ÈÃú/ÿ”,œè@ûS < m1 · · · mn,SU çò/°E). œèmnÈå,ál´m(m1 · · · mn−1, m1 · · · mn−1mn)•Åò}£ÃìS,ásÈû
间，从计算的角度可以确保在一定的时问内这是办不到的.同样的道理，四为不知道，要从 区间(0，m,一1)逐一尝试a的所有可能值，得到相应的r再得到S,在一定的时间内也是办 不到的 4.4欧拉函数 设n=m.…r是正整数n的标准素分解，即m,…,p,是两两不同的素数，m1,·,m,均 为正整数.令1，=mZ,1≤i≤r则1，…，1，是z的两两互素的理想，且1nn山，=nZ因 此由定理41立即得到 推论4.3设n=…pr是正整数n的标准素分解则有环同构 T:2n兰乙⊕…⊕Zn,x0=(亿，…，i,1ez (注意上述每个的意义不同，指在不同的剩余类环中的元) 由此立即得到 U(Zn)兰U(亿)⊕…⊕U(亿pr), 从而 U(Za1=U(亿p‖…lU(亿p-l. 用p()表示欧拉(Euler)函数，即(m)是区间l,川中与n互素的整数的个数.则U() n).根据定义(p)恰是区间1，卫]中不能被p整除的整数的个数.而区间1，p]中能 祓p整除的整数恰好形如gp,其中g=1,2,…,pm-1,因此p(pm)=pm-pm-1=pm-1(p-1). 这就证明了 推论4.4设n=严是正整数n的标准素分解，()是欧拉函数则 回=L以--=n几a-之 习题 1.今有物不知其数，二二数之剩一，三三数之剩二，五五数之剩三，问物至少几何？ 2.设1，J是环的两个理想.定义环同态f:R-→/1×R/1,f)=(r+1,r+ ),r∈R证明 (句Kcf=InJ.特别地，f是单同态当且仅当InJ={0 ()∫是满同态当且仅当1+J=R. 3设m1,,m是两两互素的整数.设n∈(m)z且满足n1(modm小.证
5 m,lOé›å±(3ò½ûmS˘¥çÿ. ”n,œèÿan,ál ´m(0, mn − 1)Åò}£an§kåUä, ÉAr2S,3ò½ûmSè¥ç ÿ. 4.4 Ó.ºÍ∗ n = p m1 1 · · · p mr r ¥ÍnIOÉ©), =p1, · · · , pr¥¸¸ÿ”ÉÍ, m1, · · · , mr˛ èÍ. -Ii = p mi i Z, 1 ≤ i ≤ r.KI1, · · · , Ir¥Z¸¸pÉné,ÖI1∩· · ·∩Ir = nZ.œ dd½n4.1·= Ìÿ4.3 n = p m1 1 · · · p mr r ¥ÍnIOÉ©).KkÇ” π : Zn ∼= Zp m1 1 ⊕ · · · ⊕ Zp mr r , π( ¯l) = (¯l, · · · , ¯l), ∀ l ∈ Z. (5ø˛„zá¯lø¬ÿ”,ç3ÿ”ê{aÇ•.) dd·= U(Zn) ∼= U(Zp m1 1 ) ⊕ · · · ⊕ U(Zp mr r ), l |U(Zn)| = |U(Zp m1 1 )| · · · |U(Zp mr r )|. ^ϕ(n)L´Ó.(Euler) ºÍ, =ϕ(n)¥´m[1, n]•ÜnpÉÍáÍ. K|U(Zn)| = ϕ(n). 䂽¬ϕ(p m)T¥´m[1, pm]•ÿUpÿÍáÍ. ´m[1, pm]•U pÿÍT–/Xqp, Ÿ•q = 1, 2, · · · , pm−1 , œdϕ(p m) = p m−p m−1 = p m−1 (p−1). ˘“y² Ìÿ4.4 n = p m1 1 · · · p mr r ¥ÍnIOÉ©), ϕ(n)¥Ó.ºÍ.K ϕ(n) = Y 1≤i≤r p mi−1 i (pi − 1) = n Y 1≤i≤r (1 − 1 pi ). SK 1. 8k‘ÿŸÍ,ÍÉêò,nnÍÉê, ÍÉên,Ø‘ñA¤? 2. I, J¥ÇR¸áné. ½¬Ç”f : R −→ R/I × R/J, f(r) = (r + I, r + J), ∀ r ∈ R.y² (i) Kerf = I ∩ J. AO/, f¥¸”Ö=I ∩ J = {0}. (ii) f¥˜”Ö=I + J = R. 3. m1, · · · , mn¥¸¸pÉÍ. ri ∈ ( Q j6=i mj )ZÖ˜vri ≡ 1 (mod mi). y ²
6 ()在Zm…m中有 而=0，i≠为所=元，1=n+…+万n ()环同构 T:2m4mn兰Zm,⊕…甲Zm →(6，…，) 给出Zm1m的理想()与2nm,之间的环同构， 4.设m1,…,mn是两两互素的整数利用剩余类环的自同构群是1阶群的事实（参见本 章第二节习题14)证明环亿1m.和环乙m:⊕…⊕乙mn之间只有唯一的同构映射（这也从 个侧面说明中国利余定理为什么很有名)
6 (i) 3Zm1···mn•k r¯ir¯j = ¯0, ∀ i 6= j; ¯rir¯i = ¯ri , ∀ i; ¯1 = ¯r1 + · · · + ¯rn. (ii) Ç” π : Zm1···mn ∼= Zm1 ⊕ · · · ⊕ Zmn r¯ 7→ (¯r, · · · , r¯) â—Zm1···mnnéhr¯iiÜZmiÉmÇ”. 4. m1, · · · , mn¥¸¸pÉÍ.|^ê{aÇg”+¥1 +Ø¢(ÎÑ Ÿ1!SK14) y²ÇZm1···mn⁄ÇZm1 ⊕ · · · ⊕ ZmnÉmêkçò”N(˘èlò á˝°`²•Iê{½nèüoÈk¶)