《数论算法》教案 第3章 同余及其运算.pdf

第3章 同全双其运算1.同余概念2.性质内容 3.剩余类一整数分类4.模幕运算5.一次不定方程要点 同余及其计算应用：密码学公钥密码学【例】RSA公钥算法：准备：选大素数 p、q,记 n=pq,(p(n)=(pl)(q1),再 选正整数e,满足(e,(p(n)=1(mod n)并求 d,满足 ed=l(mod(p(n)加密：明文串P编码为数字M,则密文。三AT(mod n)解密：M三C(modn),再将数字M解码得明文串P3.1 同余的概念及基本性质(-)同余概念【定义3.1.1给定一个正整数m,两个整数a、b叫做模 m同余,如果a-b被m整除，即加，记作a=b(mod m)；否则叫做模m不同余,记作aRb(mod m)【注】ma-b-m a-b a=b(mod m)a=b(mod m)假定：模mel。判断同余的方法一：利用定义【例 1】7|28=29-1,故 29三 1(mod 7)；7 21=27-6,故 27三6(mod 7)；7 28=23-(-5),故 23三一5(mod 7)；(-)性质【性质D设m是一个正整数，a、b是两个整数，则a三b(mod m)=存在整数k,使得a=b+km。(证)a=b(mod m)=ma-b=存在 k,使得 ab=km,即 a=b+km【性质2】同余是一种等价关系。即(i)自反性：a=a(mod m)(ii)对称性：a=b(mod m)n b=a(mod m)(iii)传递性：a=b(mod m)且 b三c(mod m)=a=c(mod m)(证)(i)m|0=aa=a=a(mod m)(ii)a=b(mod m)n m|a-b n m|b_a=(ab)=b=a(mod m)(iii)a=b(mod m),b三c(mod m)=m|ab,m|bc=m|(ab)+(bc)=ac n a=c(mod m)【例3】【性质3】(等价定义)整数a、b模m同余=a、b被m 除的余数相同。(证)由欧几里得除法，存在q,r,r,使得a=qm+r,b=gm+r即 ab=(qr)m+(rrf)或(r/)=(ab)(q故 m|(ab)a=b+hm 且 c=d+km=a+c=(b+hm)+(d+km)=(b+d)+(h+k)m,ac=(b+hm)(d+km)=bd+(hd+kb+hkm)m=由性质1即得结论。一般情形：尸(mod m)(i=l5 2,.9 k),贝！Jk kE%三W(mod m)i=i i=ik k(ii)口三 n，1(modm)i=l i=l【推论 1】a=b(mod m)=na=nb(mod m),其中 n 为正整数。【推论 2】a=b(mod m)=an=bn(mod m),其中 n为正整数。【推论 3】x三y(mod m),%三%(mod m)(i=l,2,k),贝(Ja+axx+a2x2+a kxk=b xy+b2y2+-+bkyk(mod m)应用：求值a+b(mod m)=(a(mod m)+(b(mod m)(mod m)ab(mod m)=(a(mod m)(b(mod m)(mod m)na(mod m)=n(a(mod m)(mod m)an(mod m)=(a(mod m)n(mod m)例6 2003年5月9日是星期五，问此后的第2.3天是 星期几？(解)22003+5(mod 7)=(22003(mod 7)+5(mod 7)(mod 7)=(23)667 2 2(mod 7)+5)(mod 7)三(8667(mod 7)-4(mod 7)(mod 7)+5)(mod 7)=(8(mod 7)667(mod 7)-4)(mod 7)+5)(mod 7)三(I667(mod 7)-4)(mod 7)+5)(mod 7)=(1*4(mod 7)+5)(mod 7)=9(mod 7)=2(mod 7)所以，此后的第223天是星期二。【例】设十进制整数Wo、。，贝!J3|n=3|。左+左_1+1+09|n 9|左+左-(证)因n=ak10k+-+a1lO+ao=ak+ak_1+-+a1+ao(mod3)n=ak10k+110 0=ak+ak_1+ar+a0(mod 9)【例】设整数n的1000进制表示式为11=410004 H-JOOO+o则 7(或 11,或 13)|n O7(或 11,或 13)|(0+2+,.)(1+3+,一)(证)因n=1000”+,FJOOO+q0三。左(一 1)+。1(一1)1+!(-1)+0(mod 7)11 三1-1)+i(-1)】+i(-l)+4o(mod 11)n三 a 卜(-1)，+k-i(-1)i+i(-1)+Q 0(mod 13)例如，判断n=1234567能否被7整除：12345678=12x10002+345x1000+678而(12+678)345=345 不能被 7、11、13 整除故1234567不能被这3个数整除。【例】设十进制整数n=(a/i%为)。，则11 I H=11 I(o+2+)一(1+3+)2 n O 2 a。4 n O 4(%。)。O 4|2%+081 n o 8|(2io)io 0 8|42+2i+a()2n o 2 T.aio例如，判断n=981234576能否被11、2、4、8、16整除。因为(6+5+3+1+9)-(7+4+2+8)=3,故 n 不能被 11整除因 2|6,故2|n4|76 或 4|2X7+6=20,故 4|n8|4X5+2X7+6=40,故 8|n因 8X4+4X5+10X7+6三0(mod 16),故 16|n【性质5】消去律：设ad三bd(mod m)o若(d,m)=b贝IJa=b(mod m)o(证)ad=bd(mod m)=m|adbd=(ab)d而(d,m)=1,故 m|(ab),即 a=b(mod m)【例】95三25(mod 7),且(5,7)=1,故 19三5(mod 7)【反例】115三25(mod 15),即 23X5三5X5(mod 15),但 23盘5(mod 15)o因为(5,15)=51【性质6】a=b(mod m)且k0,贝！Jak=bk(mod mk)(证)a=b(mod m)n m|a-b=mk|(ab)k=akbk n ak=bk(mod mk)【例】19=5(mod 7),k=40,所以76三20(mod 28)【性质 7】a=b(mod m)且 d|(a,b,m),贝(Ja _b z,mx一=一(mod)d d d(证)d|(a,b,m)=存在整数优使得a=dar,b=d，m=dmr又a三b(modm)=存在整数k,使得 a=b+mk=d=Abf+dmk=a=b+m kn ar=br(mod mf)a _b z,m.=z 一=一(mod)d d d【例】190 三 50(mod 70),取 d=10,贝！J19三5(mod 7)说明：性质6、7结合，得设 d|(a,b,m),贝(ja三b(mod m)(modm7)a b_=_d d或者：设 k0,贝！J a三b(mod m)Oak三bk(mod mk)【性质8】a=b(mod m)且d|m,贝!J a=b(mod d)(证)a=b(mod m)n m|ab又 d|m=d|ab即 a=b(mod d)【例】190三50 mod 70,取d=7,则190三50(mod 7)【性质9】a=b(mod)(i=l,2,k)的充分必要条 件是 a三b(mod(证)a=b(mod mi)=mt|ab=Ni，加2,，帆a=b(mod 叫啊广七叫)【例】190=50(mod 7),190=50(mod 10)以及7,10=70,=190三50(mod 70)【例】190三50(mod 28),190三50(mod 35)以及28,35=140,n 190三50(mod 140)【推论】p,q为不同的素数，则a=b(mod p)且 a=b(mod q)a=b(mod pq)(证)由为p,q=pq【性质10】a=b(mod m),贝lj(a,m)=(b,m)(证)a=b(mod m)n 存在 k,使得 a=b+mk=mk+b=(a,m)=(m,b)(1.3 性质(8):a=bq+c,q 为整数,则(a,b)=(b9 c)【例】设m,n,a均为正整数，若1(mod m)则存在n的素因数p,满足1(mod m)(证)反证法。若存在n的一个素因数p,使得p三0(mod m)=mpa又P是n的因数 n p|n n pana=m|na=na=0(modm),与假设矛盾。(即na0(mod m)时，对n的每个素因子p,都有p壬0(mod m)其次，若对n=Pi2的每个素因数Pi，都有p；三 1(mod m),i=l,2,则由性质4的一般情形(附：性质4 一般情形：%三演modk km(i=l,2,k),贝4口,三 口方,mod m)i=l i=lP；P：，P：=1(mod m)所以na 三(P1P2 p J(mod m)=PiP2-Pt(mod m)=1(mod m)与假设矛盾。(即El(mod m)时，对n的每个素因子p,不一定都满足p三1(mod m),但必至少有一个p,使得paWl(mod m)因此，结论成立。3.2剩余类及完全剩余余3.2.1剩余类和完全剩余系设 m 为正整数，记C”=k|cZ,a=c mod mQ非空，至少aQ【定理3.2.1设m是一个正整数，则(i)任一整数必包含在某个C,中，OWrWm-l(ii)Ca=Cb a=b(mod m)(iii)CaCb=(I)aEb(mod m)(证)利用欧几里德除法和同余的等价性例如，设 m=14,则一 9,5,19eC5；7=35(mod 14),则C7=C35=,一7,7,21,7三9(mod 14),故C7 c9=。【定义3.2.1 Ca叫做模m的a的剩余类。一个剩余类中 的任一个数叫做该类的剩余或代表。若，0J吁1是m个 整数，且其中任何两个都不在同一个剩余类中，则称,0/时1为模m的一个完全剩余系。【注】每个剩余类中都包含了无穷多个整数，而完全剩余 系则恰好由m个数组成。模m的剩余类共有m个，例如例1设m=10,则。=+104|左gZ是模m=10的剩余类。模10的剩余系举例：(1)0,1,2,，9(2)1,2,3,，10(3)0,1,2,，9(4)0,3,6,9,，27(5)10,11,22,33,44,，99(6)20,1,-18,13,64,-55,-94,一3,18,93.2.2 剩余类的性质【定理3.2.2整数小1，,r吁i为m的一个完全剩余系 O rirj(mod m)o(证)由定理321的(ii)(iii)即得结论。【例2】m的典型完全剩余系：(i)最小非负完全剩余系：0,1,，m-1(ii)最小正完全剩余系：1,2,m(iii)最大非正完全剩余系：0,1,，(m1)(iv)最大负完全剩余系：一1,2,，m(v)绝对(值)最小完全剩余系m 为偶数：一m/2,(m2)/2,，(m2)/2 或：一(m2)/2,，(m2)/2,m/2,m 为奇数：(m1)/2,(m3)/2,(m1)/2【定理323】设a是满足(a,m)=l的整数，b为任意整 数。若x遍历模m的一个完全剩余系，则ax+b遍历模m 的一个完全剩余系。1个数2ax+b之间不同余设0“”科._1为m的一个完全剩余系。由定理 3.2.2 知，j(mod m)(OWiVjWm-1)又(a,m)=l,故 ar产 ar j(mod m)从而 ar-+b ar-+b(mod m)1 J由定理 3.22 ar+b 9 arr+b 9 ar,是模 m 的一个完全剩余系。【例3】设m=10,原剩余系为0,1,，9o当a=7,b=5时,新的剩余系为：5,12,17,68当a=3,b=6时，新的剩余系为：6,9,12,，33【定理3.2.4】设加1，加2是两个互素的正整数，若 x2分别遍历叫,m2的完全剩余系，则叫“1+m1x2遍历模帆1帆2的完全剩余系。1个数2m2x1+帆/2之间不同余(证)当工2分别遍历人，机2个整数时，%+%“2则 遍历模加1加2个整数。问题转化为：证明川得2个整数62%1+加述2模加162 两两不同余。用反证法：若存在1，/和月，2满足m2x1+m1x2=m2y1+nzxj2(mod 人叫)则由3.1节性质8或性质9知m1x1+m1x2=m2y1+ntley2(mod m1)即 m1x1=m1y1(mod m1)而(mi,m2)=1,故由同余的性质三月(mod m1)同理可证，x2=y2(mod m2)o【例4】设p、q是两个不同的素数，n=pq,则对任意整 数c,存在唯一的一对数x和y,满足qx+py三c(mod n),OWxVp,OWyVq(证)首先知p q互素。再由定理3.2.4,当x、y分别遍历模p、q的完全剩余系 时，qx+py遍历模n=pq的完全剩余系。故存在唯一的一 对整数x、y,满足上式。3.3既约剩余余3.3.1 既约剩余系【定义3.3.2 一个模m的剩余类叫做既约剩余类（或立 素剩余类、既约剩余类、不可约剩余类）,如果该类中存在一 个与m互素的剩余。注：本定义与剩余的选取无关。【例】m=20,C3=C23【定理3.3.1】设G是同一剩余类中的两个剩余，则，1 与m互素的充分必要条件是，2与m互素。（证）由题设知rx=r2+km再由最大公因子性质知（。，m）=（r2，m）:.5，m）=1=（r2,m）=1【定义333】设m为正整数，在模m的所有不同既约剩 余类中，从每个类任取一个数组成的整数集合，叫做模m的 一个既约剩余系（缩系、互素剩余系、既约剩余系、不可约 剩余系）。【例】模6的既约剩余系为1,5模20的既约剩余系为1,3,7,%11,13,17,19【定理3.3.21m的既约剩余系的元素个数为夕（帆）。（证）显然。【例2】模m的典型既约剩余系：（i）最小非负既约剩余系：0,1,m1中与m互 素的所有整数(ii)最小正既约剩余系：1,2,，m中与m互素的所 有整数(iii)最大非正既约剩余系：0,1,(m1)中与m互素的所有整数(iv)最大负既约剩余系：一1,2,m中与m互素的所有整数(v)绝对(值)最小既约剩余系m 为偶数时指一m/2,(m2)/2,(m2)/2 或：一(m2)/2,，(m-2)/2,m/2 中 与m互素的所有整数m 为奇数时指一(m1)/2,(m3)/2,(m1)/2中与m互素的所有整数【例】模14的典型既约剩余系为(14)=6)：(i)最小非负既约剩余系：1,3,5,9,11,13(ii)最小正既约剩余系：1,3,5,9,11,13(iii)最大非正既约剩余系：一1,3,5,9,11,13(iv)最大负既约剩余系：一1,3,5,9,11,-13(v)绝对(值)最小既约剩余系：一5,-3,-1,1,3,5模15的典型既约剩余系为(415)=8)：(i)最小非负既约剩余系：1,2,4,7,8,11,13,14(ii)最小正既约剩余系：1,2,4,7,8,11,13,14(iii)最大非正既约剩余系：19 2,4,7,8,11,13,14(iv)最大负既约剩余系：一1,一2,一4,7,8,11,13,-14(v)绝对(值)最小既约剩余系：一7,4,2,1,1,2,4,7【例6】素数p的既约剩余系为1,2,p-L即 o(p)=pl【定理3.3.3】设整数o，r2,均与m互素，且两两模m不同余，则它们构成模m的一个既约剩余系。(证)由题意知，1，弓(山)是来自模m的不同既 约剩余类的剩余，故是m的一个既约剩余系。【定理3.3.4】设整数，0的)均与m互素，若它们 构成模m的一个既约剩余系，则这些弓必两两模m不同余。(证)由题意知a，r2,。是来自模m的不同既约剩 余类的剩余，而不同剩余类中的数必互不同余。【推论】设整数6,%，均与m互素，则它们构成 模m的既约剩余系的充分必要条件是这些勺两两模m不同 余。【定理3.3.5设m为正整数，a是满足(a,m)=l的整数。那么，若x遍历模m的一个既约剩余系，则ax也遍历模m 的一个既约剩余系。(证)首先，由(a,m)=l 及(x,m)=l 知(ax,m)=l,即ax是既约剩余类的剩余。其次，若(modm),则必有工1工%2(mod m)(否贝4,由Qjq=ax2(mod m)及(a,m)=1 可得工=x2(mod m),矛盾)因此x遍历模m的一个既约剩余系时，ax遍历缶)个 数,且它们两两m不同余。由定理3.3.3知ax也遍历模m 的一个既约剩余系。【例 7】已知 x=l,7,11,13,17,19,23,29 是模 30 的既约剩余系，(7,30)=1,则x=7,19,17,1,29,13,11,23也是模30的既约剩余系。【例 8】设 m=7,a=l,2,3,4,5,6,则 ax 为:X a123456112345622461353362514441526355316426654321【定理3.3.6当x遍历m的既约剩余系时，xkm也遍 历m的既约剩余系。(证)首先，由(x,m)=l知(xkm,m)=l,即二者互 素。其次，当%mod m,必有 xr km x2 km(mod m)【推论】设m为正整数，a是满足(a,m)=l的整数，则 当x遍历m的既约剩余系时，max也遍历m的既约剩余 系。【定理3.3.7设m为正整数，a是满足(a,m)=l的整数。则存在整数屋(IgaVm)使得aaf=(mod m)(证)(构造性证明)由m)=l知存在整数s,t,使得sa+tm=(a,m)=l即 sa1=(t)msa=l(mod m)因此，所求屋=s。【例10】设m=737,a=635,求满足 aar=l(mod m)(解)利用广义欧几里得除法，可找到s=-224,t=193,使得(-224)-635+193-737=1:.三一224三513(mod 737)即 635-(-224)三 1(mod 737)【定理338】设加J加2是两个互素的正整数，若干，必 分别遍历模帆1，加2的既约剩余系，则加2%1+加1X2遍历模 m1m1的既约剩余系。1个数2m2xt+帆1%2之间互素3m2x1+加产2之间不同余先证机2%1+帆/2属于模加1加2的某个既约剩余类，即证(加2%1+必1“2，叫叫)=1事实上，由(加1，加2)=1及(加J/)=1和(加2,x2)=1 知(m2x1+m1x2,m1)=(m2x1,m1)=(x1,zn1)=l(m2x1+m1x2,m2)=(m1x2,m2)=(x2,m2)=l:.+m.x19 m.m.)=1/1 J./1/其次，证明：当巧mod m1,x2 y2 mod 叫时,有m2x1+m1x2m2y1+mxy2(mod 叫叫)事实上，完全剩余系包含既约剩余系，故完全剩余系的性质 适用于既约剩余系。【应用】利用小的数的既约剩余系构造大的数的既约剩余 系。【例】设m=77=711,利用7和11的既约剩余系构造77 的既约剩余系。（解）取7的最小正既约剩余系为x=l,2,3,4,5,6取11的最小正既约剩余系 则77的一个既约剩余系为llx+7y,10y=l 9 2,3 9即18,29,40,51,62,73,25,36,47,58,69,80,32,43,54,65,76,39,50,61,72,83,87,94,46,57,68,79,90,101,53,64,75,86,97,60,71,82,93,67,78,89,74,85,96,81(x=l)92(x=2)103(x=3)100,107,114(x=4)104,111,118,125(x=5)108,115,122,129,136(x=6)或既约剩余系为（取最小非负既约剩余系）llx+7y（mod 77）18,25,32,39,46,53,60,67,74,4(x=l)29,36,43,50,57,64,71,1,8,15(x=2)40,47,54,61,68,75,5,12,19,26(x=3)51,58,65,72,2,9,16,23,30,37(x=4)62,69,76,6,13,20,27,34,41,48(x三 5)73,3,10,17,24,31,38,45,52,63(x=6)即 913,26,39,2,15,27,40,3,16,29,41,4,17,30,43,5,18,31,45,6,19,32,46,8,20,34,47,9,10,12,23,24,25,36,37,38,48,50,51,52,53,54,57,58,59,60,61,62,64,65,67,68,69,71,72,73,74,75,76若选绝对值最小既约剩余系，则为-38,-37,-36,-34,-32,-31,-30,-29,-27,-26,-25,-24,-23,-20,-19,-18,-17,-16,-15,-13,-12,-10,-9,8,6,-5,-49 3,-2,1,1,2,3,4,5,6,8,9,10,12,13,15,16,17,18,19,20,23,24,25,26,27,29,30,31,32,34,36,37,38即1,2,+3,+4,+5.+6+8,9,10,12,13,15,16,17,18,19,20,土23,24,25,26,27,29,30,31,32,34,36,37,383.3.2 整数a模m的逆(1)定义【定义334】设血是一个正整数，是一个整数。若存在 整数，使得aar=1(mod m)成立，则叫做模m亘逆元，屋叫做的模加逆元(简称 逆),记作a(mod/n)或一，实质上，“与互为逆元素。由定理3.3.7知，当(a,帆)=1时，逆元a_1(moda)是存在的。【例】对任何模数加1而言，至少有两个数有逆。即1-1=1,(m 1)1=m 1(mod m)(或(1)1 三-1)（2）性质【性质1】若可逆，贝!J（，祇）=lo（证）Q可逆，则”的逆T存在，且满足aal=1（mod m）即存在整数k,使得aar=l+km=km+l再由最大公因子的性质知（qT,m）=（m,1）=1而（a。1,m）=1（a,m）=1 且（一、m）=1【推论】a是模m的逆的充分必要条件是（a,m）=1。【性质2不唯一。即若T存在，贝！JT+km都是a 的逆，其中k为任意整数。（证）只需直接验证：已知qT是a的逆，即aa1=1（mod m）那么，对任意整数k,有矶t+km）=aax+akm三aa，+0=1（mod m）【例】设m=7,a=2,直接计算有.2（一3）三 1 mod 7,2 4 三 1 mod 7,241=1 mod 7,2*18=1 mod 7,即对模7而言，整数4+74都是2的逆aez)【性质3若b和c都是a的逆，则有b=c(mod m)o(证)已知 ab三 1(mod m),ac=l(mod m)从而 ab=ac(mod m)而(a,m)=L 故由消去律知 b=c(mod m)o【推论1】设整数a有逆I则整数b是a的逆的充分必 要条件是b=ax(mod m)o即 b=aT+km(kz)。(证)只要验证当三t(mod m)时，b也是a的逆 即可。显然。【例】设m=50,3模50的逆为17,那么，只要b 三 17 mod 50 o如力=，-33,67,都是3的逆。反之，2017(mod 50),贝！J 20不是3的逆。【推论2】在模m的一个既约剩余系中，的逆a是唯一 的。【例】设m=7,选模7的最小正既约剩余系1,2,，6,则a=2的逆2T=4且唯一。【性质4】(1)一1尸三心（火2做厂三%（证）直接验证。推论（“尸三（t。【例】设m=55,求8和24模55的逆。（解）观察：2T=28（mod 55）:.8-1=（23）三（2 1）=283=7（mod 55）241=（23 3）1=（23）1 3T=7 37=39（3）计算t的方法【方法1】利用既约剩余类的性质枚举求逆例 m=ll,a=5,则51=5,5-2=10,5-3=4,5-5=3,5-6=8,5-9=1:.5T三9（mod 11）【方法2】利用辗转相除法（即定理3.3.7的结论）【方法3】利用有关性质（求大的数的逆）【方法4】利用欧拉函数和欧拉定理的结论（见后）3.4欧拉定理和赛马小定理3.4.1 欧拉定理【定理3.4.1（Euler定理）设m是大于1的整数，若整 数a满足（a,m）=l,则有心）三 1（modm）（证）设，1/2/。为m的最小正既约剩余系，则由 定理3.3.5知,当m）=l时,也为模m的一个既约剩余系。故不在，M。）（modm）是模m的最小正剩余4力，。（环的某个排列。所以心。的）三5。（刈（mod m）即心叫C）三。W）（mod m）又由亿，m）=l知，亿，2。（加），m）=L故有四）三 1（modm）【例 1】设 m=7,a=2,则（2,7）=1,.=6模7的最小正既约剩余系为：1,2,3,4,5,6,贝I24=2,2*2=4,2*3=6,2-4=1,2 5三3,2 6三5 mod 7各等式两边相乘，有（2.1）（2 2）（23）（24）（25）（26）三246135 mod 7即 261.23456三123456 mod 7而（123456,7）=1,所以结论成立。【例 3】设 m=lL a=2,则(2,7)=1,(11)=10,故2“三 1 mod 11例 4设 m=23,231a,则(a,23)=1,.(23)=22,故222 三 1 mod 23(欧拉定理的)另一表示形式：设m是大于1的整数，若整数a满足(a,m)=L则有。(旭)+1 三a(mod m)3.4.2 费马小定理【定理342】(Fermat定理)设p为素数，a为任意正整 数，则ap=a(mod p)(证)(1)pa 9 则有a 三。(mod p)ap=0(mod p)即 ap=a(mod p)(2)pta,必有(a,p)=l,由定理 3.4.1ap l=l(mod p)两边同乘以a,得 ap=a(mod p)【例】设p=U,a=2,则0(11)=10,故2n=2(mod 11)设 p=23,a=10,则0(23)=22,故1()23 三I。(mod 23)【推论】设ml,则m为素数的必要条件是:对某个mla 的整数a,有aml=1(mod m)应用：用于否定一个整数为素数。意义：是判断一个正整数为素数的概率算法的理论基础。【例】设m=20,a=2,则219=2(26丫 三 2 43=2 26 三24三8(mod 20)又 3?9=32仅)9 三 9(一 3)9=-9(-3)3=9-(-3)=3(mod30)20和30都是合数。又 1产三(_4三1(mod 15),既不能肯定15是素数，也不能肯定15是合数。一般情况下要进行多次判断，例如：2三22(24丫三4(mod 15),所以15是合数。【例5】设p、q是两个不同的奇素数，n=pq,a是与n 互素的整数。令整数e满足IVeVRii)且(e,e(n)=L存 在正整数d,使得ed=1(mod(n)，ld(n)而且，对于整数c三优(mod n)(lcn),有c三a(mod n)(证)因(e,(n)=l,故e的逆d存在，满足ed=1(mod e(n)即存在正整数k,使ed=l+k(ii)由定理3.4.1知 a“)三1(modp),所以三/+神三/+娇0三打偌。储)夕三a(modp)同理可得 三a(modq)从而 aed=2i(mod n)即 cd=ue=a(mod n)【例6】设p、q是两个不同的奇素数，n=pq,且设整数 e、d满足ed=1(mod(n),ld(n)那么，对于整数c三陵(mod n)(lWc(p1)=-1(mod p)充分性：用反证法。已知(p 1)!=1(mod p),由同余性质知 p|(pT)!_(T)=(p_l)!+l=c+l若p=ab为合数，则a|p,从而d c+i又IVaVp(且IVbVp),那么，必有 a|(p-l)!=c:.a|(c+l)c=l矛盾。故P为素数。意义：精确判断素数的一个理论方法。【例】设 p=7,则 2-4=1,3-5=1(mod 7)即 2T 三4,3T 三5,4T 三2,5T 三3(mod 7)以及 1一1三1,6T三6(mod 7),从而有:.126三 1(24)(35)6三6三一1(mod 7)又设p=U,贝!J2-6=1,3-4=1,5 9 三 1,7-8=1(mod 11):.1-210三 1(26)(34)(5-9)(78)6三 10三一 1(mod 11)3.5 模重复平方计算法目的：快速计算a=bn(mod m)(1)问题：常规思路，递归地计算(1)式：力三(&T(mod 机)力)(mod m)运算量：nl次乘法。3.5.1 模重复平方计算法原理表为二进制=(敢敢T%0),即=%+%2+m2 22 H-f nk_t 2 J+nk 2k其中 w.e0,1,i=0J,k。贝！J办三办殉02yl.22y.(办21户犷上(mod m)运算量：乘法次数S1+2+-+k)+k=:(计 算最多需要i次乘法)。最少运算量：乘法次数Wk+k=2k(利用计算皿)3.5.2 模重复平方计算法(0)令a=L表n为二进制n=Fig+2+2kl+nk 2(1)如果0=1,计算 0 三ab(mod m),否则，令 o=a计算 bt=b2(mod m)(2)如果i=l,计算 ax=ajbx(mod m),否则，令%=0计算 b2=b1(mod m)(k)如果敢_1=L计算 做_1三做_24-1(modm),否则，令 ak_x=ak_2计算 bk=b；_(mod m)(k+1)如果敢=1,计算 ak=ak_1bk(mod m),否则，令 ak=ak_1最后，a=bn=ak(mod m)特点：由n的低位到高位计算(-)方法二思路借鉴多项式求值的秦九韶算法：计算多项式P(x)=anxn+-+a1x+aQ 的值。常规计算的乘法运算量为L=n+(nl)+.+2+l=n(n1)/2 快速算法：P(x)=(%+an_x)x+2)x+ajx+0 运算量：n次乘法，n次加法。例如，P(x)=3x4+4x3+8x2+15x+2=(3x+4)x+8)x+15)x+2计算 p(5)=(3-5+4)5+8)5+15)5+2特殊多项式:系数出 0,1P(x)=x4+x2+x+l=(x+0)x+l)x+l)x+1计算特殊值：P(2)=24+22+2+l=(2+0)2+l)2+l)2+l=23思路：运算变换加法f乘法，乘法f乘方例/=/=64+22+2+1=(2.。0)2 小弓 b(-)理论基础I三(ab)(mod m)三(a(mod m)(b(mod m)(mod m)基本乘方：方2=bxb,用1次乘法b11=b4=b2b2=(b2J,用 2 次乘法/=环=冷力4=/)2人 用3次乘法.b2k=Z2 1=(你)2,用k次乘法一般乘方：b1=b4xb2xb=(b2 bf b 9 用 4 次乘法/、/工=(.阴2 =(2.1)2.办.11,用6次乘法81。=力8192*力1。24*力512 乂8256 乂心 用17次乘法 更一般情形:为计算表n为二进制n=(/j/oh，则从而所以n=nk2k+-+w222+2+0k k=i2=”，=0 产0i n_&左 2，+i2”H-f2 22+i 2+o=b2 nk!)21nI b22n2b2n1bt=而，(产卜Dmy0。=(耻 b：i)b*./2、/I bna三立bl)三立b mod n(modn)严o 1产0,(三)算法：求表为二进制=(nknk_1-n1nQx=0；y=l;for i=k downto 0do x=2*x;y=y*y(mod m);if ni=then x+;y=y*b;)return y特点：由n的高位到低位计算【例。计算756 mOd 561(=3x11x17),计算过程各 变量的值如下表19876543210ni1000110000X1248173570140280560y|7 49 157 526 160 241 298 166 67 1又如 n=77=(1001101)2i6543210ni1001101X1249193877y749157526559196268【例 2】b5=*2=版2%y=()21)2 Z(2次平方，1次乘法)，.11 _,(1。11)2 _=(2 1时方(3次平方，2次乘法)，。77=,(1001101)2=b64.08/4 (从口的二进制分解角 度，6+3+2=11次平方，3次乘法)=除)3,1)。-b-1 b(从算法角(I、)7 7度，6次平方，3次乘法)，=(a)8 a)2.)*a(实质结果，不算4=0的情 形且嵌套起来。即计算a的64次方项时利用好a 的2、4、8、16、32次方项)方1=方(111)2-(2炉1%1、2 2 Vb)次平方，2次乘法)，.560 _(1000110000)2=.512.32.16=(A)?I)2.1)2力)2方)2 1)2.1)2.1(从算法角度，9次平方，2次乘法)=10)16万丫小丫(实质结果，即不算%=0的情形且嵌套起来）3.6 一次不定方程3.6.1 二元一次（不定）方程（-）二元一次（不定）方程的整数解【定义361】二元一次（不定）方程是指ax+a2y=n（1）其中a.a2 n是给定的整数（由2邦），乂,丫是变数（或变 量）【例】二元一次（不定）方程5x+8y=24直观求解：穷举并利用整除性方程变形 5x=248y,即 x=（248y）/5令y=0,土 1,2,3,.,计算得解（x,y）,（8,-2）,（0,3）,（-8,8）,（-16,13）,-（-）有解的条件【定理3.6.11二元一次（不定）方程（1）有解的充分必 要条件为（证）必要性：设（1,42）=/，由整除的性质知，对任 何整数X,y,都有一瓦工+2）。已知方程（1）=有解,故d|n。充分性：由d=（%，4）知，存在整数s,使得axs+a2t=d而已知d|n,上式两边同时乘以乜得(axs)+(a2t)=d 即(n=n7亦即方程（1）有解s,y t o dd（三）（/,2）=1时的解首先由有解的条件知，此时方程（1）一定有解。【定理362】设（%,2）=1，贝U（1）的全部解可表示为。x=xQ+a2t 9）=凡一卬；t=0,1,2,（3）其中X。，y0为方程（1）的一组（特）解，t为任意整数。（证）已知X0和y0满足方程（1）arx+a2y=n,将（3）式中的x、y直接代入方程中得%（X。+a21）+a2（y0一t）=ax x0+a2y0=n说明：根据X和y的对称性，方程（1）的解也可以表为x=x-a2t 9 y=y（）+/；t=0,l,2,（30（四）（%,见）1时的解【定理3.6.3设信1/2）=（11,则（1）的解与不定方程a.nx+v=一d d d的解相同。（证）因为/+。2）=X+J=1 2 d d d【定理3.6.4设（%,2）=dL若方程（1）有解，且其一组特解为X。，y0,则它的所有解为a2x=xQ+-ft d,t=0,1,2,.（4）（证）由定理3.6.2和363即得。【注】当（4,电）=41时，不能用公式（3）求方程（1）的所有解，否则会漏掉某些解。故须先将方程（1）化为等价 方程，再按公式（3）求解：x=x0+t,y=y0-t；t=0,l,2,.d d最后由定理3.6.3知它是方程（1）的所有解。（五）例【例1】求不定方程10 x7y=17的全部整数解.（解）（10,-7）=1,所以方程有解。观察：Xo=l,y0=1是一组特解，故全部解为例2求方程18x+24y=9的全部整数解.（解）因（18,24）=6,而6$9,故方程无解。【例3】求方程6x+10y=22的全部整数解.（解）（6,10）=2,2|22,所以方程有解。化原方程为:x+?y=?2 2 2即 3x+5y=ll观察可得 x=2,y0=L故原方程的全部解为x=2+5t,a t=0,1,2,ly=i-3t即即,y)=,(13,10),(一8,7),(3,4),(2,1),(7,-2),(12,-5),.注意：原方程的解不能表示为x=2+10ty=