第3章同余 3.1同余的概念及性质定义3.1.1设m≠0，a,b∈Z。若m|a－b，就称a与b模m同余，记为a≡b mod m，称b是a对模m的剩余；否则称a与b模m不同余，记为ab mod m。 因为m|a－b等价于－m|a－b，所以以后总假定模m>0。 在定义3.1.1中，如果0≤b0，则ad≡(bd) mod (md)。 证明由m|a－b，md|ad－bd即得。证毕。 一般地，由ac≡bc mod m不能推出a≡b mod m。例如，3·6≡8·6 mod 10，但38 mod 10。但有如下性质。 定理3.1.7设ca≡cb mod m，(c,m)=1，则有a≡b mod m。 证明由m|ca－cb=c(a－b)，(c,m)=1可得m|a－b。证毕。 定理3.1.8若(a,m)=1，则存在c使得ca≡1 mod m。称c是a对模m的逆元，记作a－1 mod m或a－1。 证明由定理1.2.4及(a,m)=1可知，存在x,y∈Z，使得ax+my=1。取c=x即得。证毕。 可见，由广义Euclid算法不仅可以求出(a,m)，而且当(a,m)=1时，还可以求出a－1 mod m。 定理3.1.9a≡b mod mi，其中mi∈N(i=1,2，…,k)，当且仅当a≡b mod ［m1m2…mk］。 证明 必要性: 由a≡b mod mi，得mi|a－b(i=1,2,…,k)，所以［m1m2…mk］|a－b，a≡b mod ［m1m2…mk］。 充分性: 由mi|［m1m2…mk］(1≤i≤k) 即得。证毕。 例3.1.12019年2月4日是星期一。从该天数起，第22018天是星期几？ 解因为21≡2 mod 7，22≡4 mod 7，23≡1 mod 7, 即2在模7下求幂时，得到的结果以23为周期。因2018=3·672+2，所以22018=23672·22≡4 mod 7，即第22018天是星期五。 例3.1.2求3406的个位数。 解31≡3 mod 10，32≡9≡-1 mod 10，34≡1 mod 10。而406=4·101+2，所以3406=(34)101·32≡9 mod 10，即个位数是9。3.2剩余类与剩余系由定理3.1.2知，同余是一种等价关系，因此全体整数可按照给定的模m是否同余，划分为若干个两两不相交的集合，使得在同一集合中的任意两个数模m同余，不同集合中的任意两个数模m不同余，这样得到的集合就是模m的同余类。 设m∈N，对任意的a∈Z，定义集合［a］m={c|c∈Z,c≡a mod m}。如果模m是清晰的，可将它简记为［a］。 ［a］有以下性质。 定理3.2.1 (1) ［a］=［b］a≡b mod m。 (2) 对任意的a,b∈Z，或者［a］=［b］，或者［a］∩［b］=。 证明 (1) 先证明“”。a∈［a］=［b］，所以a≡b mod m。 再证明“”。对c∈［a］，得c≡a mod m。由a≡b mod m，得c≡b mod m，所以c∈［b］，即［a］［b］。同理［b］［a］，所以［a］=［b］。 (2) 若［a］≠［b］，则必有［a］∩［b］=，否则存在c∈［a］∩［b］。c∈［a］且c∈［b］，所以c≡a mod m，c≡b mod m，可得a≡b mod m。由(1)，［a］=［b］，矛盾。证毕。 定义3.2.1［a］称为模m下a的剩余类。 定理3.2.2对m∈N，有且仅有m个模m的剩余类［0］,［1］,［2］,…,［m－1］。 证明由定理3.2.1的(2)，［0］,［1］,［2］,…,［m－1］互不相交。对任意的c∈Z，由定理1.2.1，存在q、r，使得c=qm+r，其中0≤r2时，02,12,22，…,(m－1)2一定不是模m的完全剩余系。 4. 设r1,r2,…,rm和r′1,r′2,…,r′m分别是模m的两个完全剩余系。证明: 当m是偶数时，r1+r′1,r2+r′2,…,rm+r′m一定不是模m的完全剩余系。 5. 设m≥3，r1,r2,…,rs是所有小于m2且和m互素的正整数。证明: －rs,…,－r2,－r1,r1,r2,…,rs及r1,r2,…,rs,(m－rs),…,(m－r2),(m－r1)都是模m的简化剩余系。由此推出: 当m≥3时，2|φ(m)。 6. 设(m,n)=1。证明: mφ(n)+nφ(m)≡1 mod mn。 7. 设素数p>2，a>1。证明: (1) ap+1的素因子q必是a+1的因子，或是q≡1 mod 2p。 (2) 形如2kp+1的素数有无穷多个。 8. 设p是奇素数。证明: (1) 22·42…(p－1)2≡(－1)p+12 mod p。 (2) p－12!2≡(－1)p+12 mod p。 (3) (p－1)!!≡(－1)p－12p－2!! mod p。第4章第4章同 余 方 程 4.1同余方程的基本概念设m,n∈N，多项式f(x)=anxn+…+a2x2+a1x+a0，其中ai∈Z(i=0,1,2,…，n)，则 f(x)≡0 mod m(4.1.1)称为模m的同余方程。若m an，则称式(4.1.1)的次数为n，记为deg f=n。 若x=c使式(4.1.1)成立，则称之为式(4.1.1)的解。此时与c模m同余的任一整数也是它的解。不同的解的个数称为它的解数。 显然，式(4.1.1)的解及其解数只需要在模m的一个完全剩余系中考虑。 例4.1.1求方程4x2+27x-12≡0 mod 15的解。 解在多项式求值时，取完全剩余系为绝对最小完全剩余系时，将使计算简化。在模15的绝对最小完全剩余系-7,-6,…,-1,0,1,…,6,7中直接演算，可知x=-6,3是解，解数是2。 例4.1.2求4x2+27x-9≡0 mod 15的解。 解直接演算知该方程无解。 因为4x2+27x-9≡x2+3x-6 mod 15，所以4x2+27x-9≡0 mod 15与x2+3x-6≡0 mod 15的解和解数相同，但因x2+3x-6的系数小，直接演算更为简单。一般地有以下定理。 定理4.1.1 (1) 若f(x)≡g(x) mod m，则式(4.1.1)的解和解数与g(x)≡0 mod m相同，称这两个同余方程模m等价。 (2) 若(a,m)=1，则式(4.1.1)的解和解数与方程af(x)≡0 mod m相同。特别地，当(an,m)=1时，取a≡a-1n mod m，可使式(4.1.1)的首项系数变为1。 证明简单，略去。 类似地，有同余方程组的概念。 记m1,m2,…,mk∈N,f1(x),f2(x),…fk(x)都为整系数多项式，则f1(x)≡0 mod m1 f2(x)≡0 mod m2  fk(x)≡0 mod mk(4.1.2)称为同余方程组。 若x=c满足式(4.1.2)，则称之为式(4.1.2)的解，此时与c模m=［m1m2…mk］同余的任意整数也是它的解。显然，式(4.1.2)的解及解数只需在模m的一个完全剩余系中考虑。 网络空间安全数学基础第4章同余方程4.2一次同余方程若m a，则方程ax≡b mod m(4.2.1)称为一次同余方程。 若式(4.2.1)有解，设为x0，则存在q∈Z，使得ax0=b+qm。可得(a,m)|b(4.2.2)即式(4.2.2)是式(4.2.1)有解的必要条件。 例如，在4x≡2 mod 8中，(4,8)=4 2，该方程一定无解。在3x≡2 mod 8中，(3,8)=1|2，该方程可能有解，在模8的绝对最小剩余系-3，-2，-1，0，1，2，3，4中逐一验证，知x=-2是解，解数为1。在6x≡2 mod 8中，(6,8)=2|2，在模8的绝对最小剩余系中逐一验证，知-1和3是解，解数是2。可见式(4.2.1)可能无解，也可能有解，有解时解数可能为1，也可能大于1。 定理4.2.1给出了式(4.2.2)(也是式(4.2.1))有解的充分条件。 定理4.2.1设m a，d=(a,m)，同余方程(4.2.1)有解的充要条件是d|b。在有解时，它的解数为d。又设x0是adx≡bd mod md(4.2.3)的一个解，则式(4.2.1)的d个解是x0+mdt( mod m)，其中t为0,1,2,…,d-1。 证明充分性由以下构造方法给出。 第1步: 由d|b，得bd是整数，构造方程(4.2.3)，显然ad,md=1。由定理3.6.1的推论，式(4.2.3)有解: x0≡bdad-1 mod md第2步: 方程ax≡b mod m的全部解为x0+tmd，其中t∈Z，这是因为ax0+tmd=ax0+tmad≡ax0 mod m又由于adx0≡bd mod md得ax0≡b mod m。所以ax0+tmd≡b mod m下面在全部解中求出模m不同余的解。 设x1=x0+t1md，x2=x0+t2md则x1-x2=(t1-t2)md所以m|x1-x2当且仅当d|t1-t2。即x1x2 mod m当且仅当t1t2 mod d。所以t遍历模d的一个完全剩余系(可取为最小非负完全剩余系0,1,2,…，d-1)就可得ax≡b mod m的全部解，即全部解有d个。 证毕。 推论设(a,m)=1，则方程ax≡b mod m有唯一解x≡baφ(m)-1 mod m。 证明由(a,m)=1|b及定理3.6.1的推论得解。解的唯一性由(a,m)=1得。 例4.2.1解方程20x≡15 mod 135。 解d=(20,135)=5，5|15，所以方程有5个解。构造方程4x≡3 mod 27，得解为3·4φ(27)-1≡21 mod 27。所以方程的5个解为21+t·27(t=0,1,2,3,4)，即21,48,75,102,129。 4.3一次同余方程组和中国剩余定理中国剩余定理有两个用途: (1) 已知某个数关于一些两两互素的数的同余类，就可重构这个数。 (2) 可将大数用小数表示，大数的运算可通过小数实现。 例4.3.1Z10中每个数都可从这个数关于2和5(10的两个互素的因子)的同余类重构。例如，已知x关于2和5的同余类分别是［0］和［3］，即x mod 2=0，x mod 15=3。可知x是偶数且被5除后余数是3，所以可得8是满足这一关系的唯一的x。 例4.3.2假设只能处理5以内的数，则要考虑15以内的数，可将15分解为两个小素数的乘积，15=3·5，将1～15的数列表表示，表的行号为0~2，列号为0~4，将1～15填入表中，使得其所在行号为该数除3得到的余数，列号为该数除5得到的余数，如表4.3.1所示。例如12 mod 3＝0，12 mod 5=2，所以12应填在第0行、第2列。表4.3.11～15的数行号列号0123400612391101713425112814用(0, 2)表示12。现在就可处理15以内的数了。 例如,求12·13(mod 15)，13在第1行、第3列，将13表示为(1, 3)，由0·1≡0 mod 3,2·3≡1 mod 5得12·13(mod 15)的小数表示是(0, 1)，这个位置上的数是6，所以12·13(mod 15)≡6。又因0+1≡1 mod 3,2+3≡0 mod 5，所以12+13的小数表示是(1, 0)，这个位置上的数是10，所以12+13≡10 mod 15。 以上两例是中国剩余定理的直观应用。下面具体介绍该定理的内容。 中国剩余定理最早见于《孙子算经》的“物不知数”问题: 今有物不知其数，三三数之有二，五五数之有三，七七数之有二，问物有多少？ 这一问题用方程组表示为x≡2 mod 3 x≡3 mod 5 x≡2 mod 7下面给出解的构造过程。首先将3个余数写成和的形式: 2+3+2。为满足第一个方程，即模3后，后两项消失，将后两项各乘以3，得2+3·3+2·3。为满足第二个方程，即模5后，第一、三项消失，将第一、三项各乘以5，得2·5+3·3+2·3·5。同理，给前两项各乘以7，得2·5·7+3·3·7+2·3·5。 然而，将结果代入第一方程，得到2·5·7，为消去5·7，将结果的第一项再乘以(5·7)-1 mod 3，得2·5·7(5·7)-1 mod 3+3·3·7+2·3·5。类似地，将第二项乘以(3·7)-1 mod 5，将第三项乘以(3·5)-1 mod 7，结果为2·5·7·(5·7)-1 mod 3+3·3·7·(3·7)-1 mod 5 +2·3·5·(3·5)-1 mod 7＝233又因为233+k·3·5·7=233+105k，k为任意整数时都满足方程组，可取k=-2，得到小于105(=3·5·7)的唯一解23，所以方程组的唯一解构造如下: (2·5·7·(5·7)-1 mod 3+3·3·7·(3·7)-1 mod 5 +2·3·5·(3·5)-1 mod 7) mod (3·5·7)把这种构造法推广到一般形式，就是中国剩余定理。 定理4.3.1(中国剩余定理)设m1,m2,…,mk是两两互素的正整数，M＝∏ki=1mi，则一次同余方程组x mod m1≡a1 x mod m2≡a2  x mod mk≡ak(4.3.1)对模M有唯一解: x≡Mm1e1a1+Mm2e2a2+…Mmkekakmod M(4.3.2)其中，ei满足Mmiei≡1 mod mi(i=1,2,…,k)证明设Mi=Mmi=∏l=1 l≠iml(i=1,2,…,k)由Mi的定义知Mi与mi是互素的，因此Mi在模mi下有唯一的乘法逆元，即满足Mmiei≡1 mod mi的ei是唯一的。 下面证明对任意i∈{1,2,…,k}，上述x满足x mod mi≡ai。注意到当j≠i时，mi|Mj，即Mj≡0 mod mi，所以(Mj×ej mod mj)mod mi≡((Mj mod mj)×(ej mod mj)mod mi))mod mi≡0而 (Mi×(ei mod mi))mod mi≡(Mi×ei) mod mi≡1 所以x mod mi≡ai。 下面证明方程组的解是唯一的。 设x′是方程组的另一解，即x′≡ai mod mi(i=1,2,…,k)。由x≡ai mod mi得x′-x≡0 mod mi，即mi|(x′-x)。再根据mi两两互素，有M|(x′-x)，即x′-x≡0 mod M，所以x′ mod M=x mod M。证毕。 中国剩余定理提供了一个非常有用的特性，即在模MM=∏ki=1mi下可将大数A用一组小数(a1,a2,…,ak)表达，且大数的运算可通过小数实现，表示为A(a1,a2,…,ak)其中，ai=A mod mi(i=1,2,…,k)。 有以下推论。 推论如果A(a1,a2,…,ak)，B(b1,b2,…,bk)那么(A+B) mod M((a1+b1) mod m1,…,(ak+bk) mod mk) (A-B) mod M((a1-b1) mod m1,…,(ak-bk) mod mk) (A×B) mod M((a1×b1) mod m1,…,(ak×bk) mod mk)证明可由模运算的性质直接得出。 证毕。 定理4.3.2设m1,m2,…,mk，M，e1,e2,…,ek与定理4.3.1相同。x=Mm1e1x1+Mm2e2x2+…Mmkekxk(4.3.3)则当xi遍历模mi(i=1,2,…,k)的完全(简化)剩余系时，x遍历模M的完全(简化)剩余系。 证明先证明完全剩余系的情况。当xi遍历模mi的完全剩余系时，xi有mi个取值(1≤i≤k)，因此x有M个取值。下面证明这M个取值模M两两不同余。设x′=Mm1e1x′1+Mm2e2x′2+…+Mmkekx′k若x≡x′mod M，则x≡x′mod mi，从而得xi≡x′i mod mi(1≤i≤k)。 再证明简化剩余系的情况。 由于简化剩余系中的元素是由完全剩余系中与模数互素的元素构成的，所以只要证明(x,M)=1当且仅当(xi,mi)=1(1≤i≤k)。由(x,M)=1得(x,mi)=1(1≤i≤k)。否则，若d=(x,mi)≠1，则d|x，d|mi得d|M。d是x、M的公因子，与(x,M)=1矛盾。 由(xi,mi)=1及式(4.3.3)得x mod mi≡xi，xi∈［x］mi。由定理3.3.1得(xi,mi)=(x,mi)，所以(xi,mi)=1。反之，若(xi,mi)=1(1≤i≤k)，则x mod mi≡xi，得(x,mi)=(xi,mi)=1，(x,M)=1。证毕。 例4.3.3表4.3.1的构造。 设1≤x≤15，求x≡a mod 3,x≡b mod 5，将x填入表的a行、b列。表建立完成后，数x由它的行号a和列号b表示为(a,b)。由(a,b)及中国剩余定理可按如下的方法恢复x: x≡(a·5·(5-1 mod 3)+(b·3·(3-1 mod 5)mod 15 =(a·5·2+b·3·2)mod 15 ≡［10a+6b］mod 15例如，12 mod 3≡0,12 mod 5≡2; 13 mod 3≡1,13 mod 5≡3。所以12位于表中第0行、第2列，13位于表中第1行、第3列。反之，若求表中第0行、第2列的数，将a=0,b=2代入x≡(10a+6b) mod 15，得x=12。 已知x表示为(a,b)，x的运算可用(a,b)实现。设x1=(a1,b1),x2=(a2,b2)，则x1+x2=(a1+a2,b1+b2),x1·x2=(a1·a2,b1·b2)例如: 12=(0,2)，13=(1,3) 12+13=(0,2)+(1,3)=(1,0),12·13=(0,2)·(1,3)=(0,1)所以12+13为10，12·13为6。 例4.3.4由以下方程组求x: x≡1 mod 2 x≡2 mod 3 x≡3 mod 5 x≡5 mod 7解M=2·3·5·7=210,M1=105,M2=70,M3=42,M4=30。 易得e1≡M-11 mod 2=1 e2≡M-12 mod 3=1 e3≡M-13 mod 5=3 e4≡M-14 mod 7=4所以，x≡(105×1×1+70×1×2+42×3×3+30×4×5)mod 210 ≡173 mod 210例4.3.5为将973 mod 1813由模数分别为37和49的两个数表示，可取x=973，M=1813，m1=37,m2=49由a1≡973 mod m1=11，a2≡973 mod m2=42，得x在模37和模49下的表达式为(11,42)。若要求973 mod 1813+678 mod 1813，可先求出678(678 mod 37,678 mod 49)=(12,41)从而可将以上加法表达为((11+12) mod 37,(42+41) mod 49)=(23,34)例4.3.6解方程19x≡556 mod 1155。 解这是一次同余式，可按4.2节的方法求解。但因模数1155较大，可按中国剩余定理将方程变成模数较小的同余方程组。由1155=3·5·7·11及定理1.1.9，该方程与以下方程组等价: 19x≡556 mod 3 19x≡556 mod 5 19x≡556 mod 7 19x≡556 mod 11(1)x≡1 mod 3 x≡4 mod 5 5x≡3 mod 7 8x≡6 mod 11(2)x≡1 mod 3 x≡4 mod 5 x≡2 mod 7 x≡9 mod 11由定理4.3.1即得x≡394 mod 1155。其中第(1)步由定理4.1.1的(2)得出，第(2)步由一元同余式解出5x≡3 mod 7及8x≡6 mod 11得出。注意，第(1)步中得出的方程组不是定理4.3.1中的形式，不能直接应用定理4.3.1。 例4.3.7解同余方程组x≡3 mod 7 6x≡10 mod 8解解出一次同余式6x≡10 mod 8的解为x≡3,7(mod 8)，方程组等价于以下两个方程组: x≡3 mod 7 x≡3 mod 8及x≡3 mod 7 x≡7 mod 8由定理4.3.1得x≡3,31(mod 56)。 注: x≡3,7(mod 8)表示x≡3 mod 8，x≡7 mod 8。以后常用这种简单记法。 例4.3.8在例3.6.1的RSA加密算法中，按照中国剩余定理，可将解密过程简化如下: 解密者已知p、q，计算dp≡d mod (p-1)，dq≡d mod (q-1) ap≡cdp mod p，aq≡cd mod q然后建立以下方程组: x≡ap mod p x≡aq mod q由中国剩余定理求出x mod (pq)即为明文a。这是因为dp=d+kφ(p)，其中k∈N。ap≡cdp mod p≡cd(aφ(p))k mod p≡cd mod p ≡(a mod n)mod p≡a mod p同理，aq≡a mod q，因此方程组x≡ap mod p x≡aq mod q中的x即为a。 cd mod n的运行时间是O(logd·log2n)，若d与n同阶，运行时间为O(log3n)。改进后算法的加速比是log3n2(logn/2)3=4中国剩余定理也用于解高次同余方程(即degf≥2)，解法和解数由定理4.3.3给出。 定理4.3.3设m=m1m2…mk，其中mi(1≤i≤k)是两两互素的正整数，则同余方程f(x)≡0 mod m(4.3.4)与同余方程组f(x)≡0 mod m1 f(x)≡0 mod m2  f(x)≡0 mod mk(4.3.5)等价。设T是式(4.3.4)的解数，Ti是f(x)≡0 mod mi(1≤i≤k)的解数，则T=T1T2…Tk。 证明设x0是式(4.3.4)的解，即f(x0)=0 mod m，由定理3.1.5得f(x)≡0 mod mi(1≤i≤k)，即x0也是式(4.3.5)的解。 反之，设x0是式(4.3.5)的解，即f(x)≡0 mod mi(1≤i≤k)，由定理3.1.9得f(x0)≡0 mod ［m1,m2,…,mk］≡0 mod m，即x0也是式(4.3.4)的解。 设f(x)≡0 mod mi的解是bi(1≤i≤k)，建立以下方程组:x≡b1 mod m1 x≡b2 mod m2  x≡bk mod mk(4.3.6)由中国剩余定理得x0≡mm1e1b1+mm2e2b2+…+mmkekbkmod m(4.3.7)由x0≡bi mod mi得f(x0)≡f(bi)≡0 mod mi，即x0是式(4.3.5)的解，因此也是式(4.3.4)的解。 若bi(1≤i≤k)遍历f(x)≡0 mod mi的所有解，则x0遍历f(x)≡0 mod m的所有解，因此T=T1T2…Tk。 证毕。 定理4.3.3的证明过程也给出了解高次同余方程(4.3.4)的过程: 将m分解成两两互素的数的乘积，建立方程组(4.3.5)，解出该方程组，得一次同余方程组(4.3.6)，由中国剩余定理求出的式(4.3.7)即为原方程(4.3.4)的解。通常，可先将m分解成标准分解式: m=pα11pα22…pαss，取mi=pαii(1≤i≤k)，因此一般的高次同余方程的求解就归结为模为素数幂的同余方程的求解。 4.4模为素数的高次同余方程本节考虑以下同余方程: f(x)=anxn+…+a2x2+a1x+a0=0 mod p(4.4.1)其中,p为素数，a0∈Z(i=1,2,…,n),p an。 首先考虑多项式的Euclid除法，有以下结论。 定理4.4.1设f(x)=anxn+…+a2x2+a1x+a0，g(x)=xm+…+b2x2+b1x+b0，其中ai(1≤i≤n)，bj(1≤j≤m-1)∈Z，则存在唯一的整系数多项式q(x)和r(x)，使得f(x)=q(x)g(x)+r(x)，满足deg r