数论算法讲义2章（同余运算）.doc

数论算法 第二章 同余运算第 2 章 同余运算（一） 内容l 同余概念l 性质l 剩余类整数分类l 模幂运算（二） 重点l 同余及其计算（三） 应用：l 密码学l 公钥密码学【例】 RSA公钥算法：准备：选大素数p、q，记npq，(n)(p1)(q1)，再选正整数e，满足（e，(n)）1（mod n）并求d，满足 ed1（mod (n)）加密：明文串P编码为数字M，则密文C （mod n）解密： M （mod n），再将数字M解码得明文串P2.1 同余的概念及基本性质(一) 同余概念【定义2.1.1】给定一个正整数m，两个整数a、b叫做模m同余，如果ab被m整除，或，记作 ；否则叫做模m不同余，记作ab（mod m）【注】由于等价于，所以同余式 等价于 ，故以后总假定模。判断同余的方法一：利用定义【例1】 728291，故291（mod 7）；721276，故276（mod 7）；72823（5），故235（mod 7）；(二) 性质【性质1】（定理1）设m是一个正整数，a、b是两个整数，则ab（mod m）存在整数k，使得abkm。（证）ab（mod m） 存在k，使得 abkm，即abkm【性质2】（定理2）同余是一种等价关系。即（i） 自反性：aa m（ii） 对称性：ab （mod m） ba （mod m）（iii） 传递性：ab mod m且bc （mod m） ac （mod m）（证）（i）m0aa aa m （ii）ab （mod m） mab mba(ab) ba （mod m）（iii）ab （mod m），bc （mod m） mab，mbc m(ab) (bc)ac ac （mod m）【例3】【性质3】（等价定义）（定理3）整数a、b模m同余a、b被m除的余数相同。（证）由欧几里得除法，存在q，r，使得qmr，bm即 ab(q)m(r)或 （r）(ab) (q)m故 m(ab) m(r)但 0rm且m(r) r0故 m(ab) r0，即r【性质4】（定理4）设m为正整数，a、b、c、d为整数，若ab （mod m）， cd （mod m）则（i） acbd （mod m）；（ii） acbd （mod m）。（证）已知ab （mod m）且 cd （mod m） abhm且cdkm ac(bhm)( dkm)bd(hk)m，ac(bhm)( dkm)bd(hdkbhkm)m 由性质1即得结论。一般情形： （mod m）（i1,2,k），则（i） （mod m）（ii） （mod m）【推论1】 ab （mod m） nanb （mod m），其中n为正整数。【推论2】 ab （mod m） （mod m），其中n为正整数。【推论3】 （定理5）xy （mod m）， （mod m）（i1,2,k），则 （mod m）【例6】（例6）2003年5月9日是星期五，问此后的第22003是星期几？ （解） 2200355 mod 75 mod 79 mod 72 mod 7【例】（定理6）设十进制整数n，则3n 39n 9（证）因n mod 3n mod 9【例】（定理7）设整数n的1000进制表示式为n则7（或11，或13）n 7（或11，或13）（证）因n mod 7n mod 11n mod 13例如，判断n1234567能否被7整除：123456781210002+3451000+678而 (12+678)345345不能被7、11、13整除故1234567不能被这3个数整除。【例】（补）设十进制整数n，则11n 112n 24n 4 48n 8 8n 例如，判断n981234576能否被11、2、4、8、16整除。因为（6+5+3+1+9）（7+4+2+8）3，故n不能被11整除因26，故2n476或427+622，故4n845+27+640，故8n因84+45+107+60 mod 16，故16n应用： 求值ab （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） （mod m） （mod m）【性质5】（定理8）消去律：设adbd （mod m）。若（d，m）1，则ab （mod m）。（证）adbd （mod m） mad bd(ab)d而（d，m）1，故m(ab)，即 ab （mod m）【例】（例11）9525 mod 7，且（5，7）1，故195 mod 7【反例】（补）11525 mod 15，即23555 mod 15，但235 mod 15。因为（5，15）51【性质6】（定理9）ab （mod m）且k0，则akbk （mod mk）（证）ab （mod m） ma b mk(ab)kakbk akbk （mod mk）【例】（例 12）195 mod 7，k40，所以7620 mod 28【性质7】（定理10）ab （mod m）且d(a，b，m)，则 mod （证）d(a，b，m) 存在整数，使得 d， bd，md又ab （mod m） 存在整数k，使得bmk d d dk k mod mod 【例】（例13）19050 mod 70，取d10，则195 mod 7说明：性质6、7结合，得设d(a，b，m)，则ab （mod m） mod 或者：设k0，则ab （mod m） akbk （mod mk）【性质8】（定理11）ab （mod m）且dm，则ab mod d（证）ab （mod m） mab又 dm dab即 ab mod d【例】（例14）19050 mod 70，取d7，则19050 mod 7【性质9】（定理12改）ab mod （i1,2,k）的充分必要条件是ab mod （证）ab mod ab ab ab mod 【例】（例15）19050 mod 7，19050 mod 10 以及7，1070，19050 mod 70【例】（补）19050 mod 28，19050 mod 35以及28，35140,19050 mod 140【推论】（例16）p，q为不同的素数，则ab （mod p） 且 ab （mod q） ab mod pq （证）因为 p，qpq【性质10】（定理13）ab （mod m），则（a，m）（b，m）（证）ab （mod m） 存在k，使得abmkmkb（a，m）（m，b）（1.3性质（8）：abqc，q为整数，则（a，b）（b，c）【例】（例17）设m，n，a均为正整数，若na0，1 （mod m）则存在n的素因数p，满足pa0，1 （mod m） （证） 反证法。若存在n的一个素因数p，使得pa0 mod m mpa又p是n的因数 pn pana mna， na0 （mod m），与假设矛盾。（即na0 （mod m）时，对n的每个素因子，都有pa0 （mod m）其次，若对n的每个素因数，都有1 （mod m）， i1,2,t则由性质4的一般情形（附：性质4一般情形： mod m（i1,2,k），则 mod m）1 （mod m）所以na （mod m） （mod m）1 （mod m）与假设矛盾。（即na1 （mod m）时，对n的每个素因子p，不一定都满足pa1 （mod m），但必至少有一个p，使得pa1 （mod m）因此，结论成立。2.2 剩余类及完全剩余系(一) 剩余类和完全剩余系设m为正整数，记非空，至少a【定理2.2.1】（定理1）设m是一个正整数，则（i） 任一整数必包含在某个中，0rm1（ii） ab （mod m）（iii） ab （mod m）（证）利用欧几里德除法和同余的等价性【定义2.2.1】（定义1）叫做模m的a的剩余类。一个剩余类中的任一个数叫做该类的剩余或代表。若是m个整数，且其中任何两个都不在同一个剩余类中，则称为模m的一个完全剩余系。【注】每个剩余类中都包含了无穷多个整数，而完全剩余系则恰好由m个数组成。模m的剩余类共有m个，例如【例1】（例1）设m10，则是模m10的剩余类。模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，9(二) 性质【定理2.2.2】（定理2）整数为m的一个完全剩余系 mod m。（证）由定理2.2.1的（ii）（iii）即得结论。【例2】（例2）m的典型完全剩余系：(i) 最小非负完全剩余系：0，1，m1(ii) 最小正完全剩余系：1，2，m(iii) 最大非正完全剩余系：0，1，(m1)(iv) 最大负完全剩余系：1，2，m(v) 绝对（值）最小完全剩余系m为偶数：m2，(m2)2，(m2)2或： (m2)2，(m2)2，m2，m为奇数：(m1)2，(m3)2，(m1)2【定理2.2.3】（定理3）设a是满足(a，m)1的整数，b为任意整数。若x遍历模m的一个完全剩余系，则axb遍历模m的一个完全剩余系。（证）设为m的一个完全剩余系。由定理2.2.2知， （mod m） （0ijm1）又(a，m)1，故 （mod m）从而 （mod m）由定理2.2.2，是模m的一个完全剩余系。【例3】（例3）设m10，原剩余系为0，1，9。当a7，b5时，新的剩余系为：5，12，17，68 当a3，b6时，新的剩余系为：6，9，12，33 【定理2.2.4】（定理4）设是两个互素的正整数，若分别遍历的完全剩余系，则遍历模的完全剩余系。（证）当分别遍历个整数时，则遍历模个整数。问题转化为：证明个整数模两两不同余。用反证法：若存在和满足 mod 则由2.1节性质8或性质9知 mod 即 mod 而（m1,m2）1，故由同余的性质知 mod 同理可证， mod 。【例4】（例4）设p、q是两个不同的素数，npq，则对任意整数c，存在唯一的一对数x和y，满足xpyc （mod n）， 0xp，0yq（证）首先知p、q互素。再由定理2.2.4，当x、y分别遍历模p、q的完全剩余系时，qxpy遍历模npq的完全剩余系。故存在唯一的一对整数x、y，满足上式。2.3 简化剩余系与欧拉函数(一) 欧拉函数（1） 定义【定义2.3.1】（定义1）设n为正整数，则1,2,n中与n互素的整数的个数，记作(n)，叫做欧拉（Euler）函数。【例1】（例1）设n10，则1,2,10中与10互素的数为 1,2,7,9，故(10)4【例】（补）(1)1，(2)1，(3)2，(4)2，(6)2，即1,2,6中与6互素的数为1，5(20)8，即1,2,20中与20互素的数为1,3,7,9,11,13,17,19（2） 性质【性质1】（补）设p为素数，则(p)p1。 （证）由定义2.3.1，显然。【性质2】（补）设p为素数，且整数1，则()（证）1,2, 中与p 不互素的数共有个，这些数是p，2p，3p，4p，由此即得结论。【性质3】（推论）设整数npq，其中p，q为不同的素数，则(n)(pq)(p)(q)(p1)(q1)（证）设整数a满足1an，若(a，n)d1，则必有sp或dtq （因为n的因数只有1，p，q，pqn）即必有 pd或qd，从而有pa或qa这说明与n不互素的数a必为asp或atq.这样的 a为p，2p，3p，4p，(q1)p，qp和q，2q，3q，4q，(p1)q，pq共有pq1个 (n)(pq)pq(pq1)(p1)(q1) (p)(q)【例】（补）(143)(1113)(11)(13)1012120 【性质4】（补）设整数n，其中p，q为不同的素数，则(n)()()()（证）在1n中与n不互素的数必为sp或tq形式的数，即能被p或q整除的数：p，2p，3p，4p，(1)p，pn（有个）和q，2q，3q，4q，(1)q，qn（有个）其中能同时被p和q整除的数有q，2pq，3pq，n （有个） (n)n【推论】（补）设整数n有标准分解式，则(n)（证）用归纳法。【例】(100)(2252)10040(360)(23325)36096【性质5】（定理6）欧拉函数是乘性函数（或称积性函数）。即若正整数m，n互素，则(mn)(m)(n)。（证）记m、n的标准分解式分别为，n则(mn)(m)(n)【例】（补）设m33，n32，求(3332)。（解）(33，32)1，故(3332)(33)(32) 3332160【例】（补）欧拉函数不是完全积性函数（即对任何正整数m，n，都有(mn)(m)(n)）。反例：设m36，n16，则(36)12，(16)8，(36)(16)96但 (3616)(576)(2532)576192又设m12，n20，则(12)4，(20)8，(12)(20)32但 (1220) (240)(2435)24064【例13】（例13）设npq，p,q均为素数，则可由n和(n)得到p,q（解）由npq和(n)npq1即得关于p、q的方程组由韦达定理知，p、q是方程0的两个根。【性质6】设(m，n)d，则(mn)(m)(n)（证）设n，由(n)知 【例】设m220511，n2102357，则mn220210462003711，(220, 210)10而 所以两边同乘以46240得(46240) (220) (210) 【例】设m36，n16，则 (36，16)4(36)12，(16)8，(4)2故 (3616)(36)(16)4(4)12842192【例】求(20 000)。（解）20 000100200，且(100，200)100(100)40，(200)80故 (20 000)(100)(200)100(100)100(200)100808 000【推论】若ab，则(ab)a(b)。因为ab，故(a,b)a，从而由性质知(ab)(a)(b)a(b)【性质7】若ab，则(a)(b)。（证）设a，b（将两者相同的素因子排在前面），则1（i1,2,k）且kt，并有(a)a(b)b从而 整数【性质8】（定理8）设n为正整数，则n或n（证）对n个数C1，2，n按照与n的最大公因数分类，记 x1xn，(x, n)d， dn即（在1n之间与n的最大公因子都是d的数构成的C的子集） xdk1k，(k, )1 中元素个数又因为C中每个整数恰好只属于一个类，所以，构成集合C的一个划分，即C从而 或 而当d遍历n的所有正因数时，nd也遍历n的所有正因数。即【例14】（例14）设n50，求。（解）d1，2，5，10，25，501,3,7,9,，47,49，202,4,6,8,12,14,46,48，205,15,35,45，410,20,30,40，4 25 ，1 50 ，1 +1+1+4+4+20+205050(二) 简化剩余系【定义2.3.2】（定义2）一个模m的剩余类叫做简化剩余类（或互素剩余类、既约剩余类、不可约剩余类），如果该类中存在一个与m互素的剩余。注：本定义与剩余的选取无关。【例】m=20，=【定理2.3.1】（定理1）设、是同一剩余类中的两个剩余，则与m互素的充分必要条件是与m互素。（证）由题设知 km再由最大公因子性质知（，m）（，m） （，m）1 （，m）1【定义2.3.3】（定义3）设m为正整数，在模m的所有不同简化剩余类中，从每个类任取一个数组成的整数集合，叫做模m的一个简化剩余系（或称为缩系、互素剩余系、既约剩余系、不可约剩余系）。【例】（补）模6的简化剩余系为1，5 模20的简化剩余系为1,3,7,9,11,13,17,19【定理2.3.2】（补）m的简化剩余系的元素个数为。（证）显然。【例2】（例2）模m的典型简化剩余系：(i) 最小非负简化剩余系：0，1，m1中与m互素的所有整数(ii) 最小正简化剩余系：1，2，m中与m互素的所有整数(iii) 最大非正简化剩余系：0，1，(m1) 中与m互素的所有整数(iv) 最大负简化剩余系：1，2，m中与m互素的所有整数(v) 绝对（值）最小简化剩余系m为偶数时指m2，(m2)2，(m2)2或： (m2)2，(m2)2，m2中与m互素的所有整数m为奇数时指(m1)2，(m3)2，(m1)2中与m互素的所有整数【例】（补）模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的典型简化剩余系为（8）：(i) 最小非负简化剩余系：1，2，4，7，8，11，13，14 (ii) 最小正简化剩余系：1，2，4，7，8，11，13，14(iii) 最大非正简化剩余系：1,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】（例6）素数p的简化剩余系为 1，2，p1，即p1【定理2.3.3】（定理2）设整数，均与m互素，且两两模m不同余，则它们构成模m的一个简化剩余系。（证）由题意知，是来自模m的不同简化剩余类的剩余，故是m的一个简化剩余系。【定理2.3.4】（补）设整数，均与m互素，若它们构成模m的一个简化剩余系，则这些必两两模m不同余。（证）由题意知，是来自模m的不同简化剩余类的剩余，而不同剩余类中的数必互不同余。【推论】（补）设整数，均与m互素，则它们构成模m的简化剩余系的充分必要条件是这些两两模m不同余。【定理2.3.5】（定理3）设m为正整数，a是满足(a，m)1的整数。那么，若x遍历模m的一个简化剩余系，则ax也遍历模m的一个简化剩余系。（证）首先，由(a，m)1及(x，m)1知(ax，m)1，即ax是简化剩余类的剩余。其次，若 （mod m），则必有 （mod m）（否则，由 （mod m）及(a，m)1可得 （mod m），矛盾）因此x遍历模m的一个简化剩余系时，ax遍历个数，且它们两两m不同余。由定理2.3.3知ax也遍历模m的一个简化剩余系。【例7】（例7）已知1，7，11，13，17，19，23，29是模30的简化剩余系，(7，30)1，则7，19，17，1，29，13，11，23也是模30的简化剩余系。【例8】设m7，a1，2，3，4，5，6，则ax为： x 123456112345622461353362514441526355316426654321【定理2.3.6】（补）当x遍历m的简化剩余系时，xkm也遍历m的简化剩余系。（证）首先，由(x，m)1知(xkm，m)1，即二者互素。其次，当 mod m，必有 kmkm （mod m）【推论】（补）设m为正整数，a是满足(a，m)1的整数，则当x遍历m的简化剩余系时，max也遍历m的简化剩余系。【定理2.3.7】（定理4）设m为正整数，a是满足(a，m)1的整数。则存在整数（1m）使得a1 （mod m）（证）（构造性证明）由(a，m)1知存在整数s，t，使得satm(a，m)1即sa1(t)m因此，所求s。【例10】（例10）设m737，a635，求，满足aa1 （mod m）（解）利用广义欧几里得除法，可找到s224，t193，使得(224) 6351937371 a224513 mod 737即 635(224) 1 mod 737【定理2.3.8】（定理5）设，是两个互素的正整数，若分别遍历模，的简化剩余系，则遍历模的简化剩余系。（证）先证属于模的某个简化剩余类，即证（，）1事实上，由（，）1及（，）1和（，）1知（，）（，）（，）1（，）（，）（，）1 （，）1其次，证明：当 mod ， mod 时，有 mod 事实上，完全剩余系包含简化剩余系，故完全剩余系的性质适用于简化剩余系。【应用】利用小的数的简化剩余系构造大的数的简化剩余系。【例】（补）设m77711，利用7和11的简化剩余系构造77的简化剩余系。（解）取7的最小正简化剩余系为 x1，2，3，4，5，6 取11的最小正简化剩余系 y1，2，3，10则77的一个简化剩余系为11x7y即 18，25，32，39，46，53，60，67，74，81（x1）29，36，43，50，57，64，71，78，85，92（x2）40，47，54，61，68，75，82，89，96，103（x3）51，58，65，72，79，86，93，100，107，114（x4）62，69，76，83，90，97，104，111，118，125（x5）73，80，87，94，101，108，115，122，129，136（x6）或简化剩余系为（取最小非负简化剩余系）11x7y mod 7718，25，32，39，46，53，60，67，74， 4 （x1）29，36，43，50，57，64，71， 1， 8，15 （x2）40，47，54，61，68，75， 5，12，19，26 （x3）51，58，65，72， 2， 9，16，23，30，37 （x4）62，69，76， 6，13，20，27，34，41，48 （x5）73， 3，10，17，24，31，38，45，52，63 （x6）即 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，39，40，41，43，45，46，47，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， -4， -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，38(三) 整数a模p的逆（1） 定义【定义2.3.4】将定理2.3.7中满足条件的叫作a（对模m）的逆，记为。即 a1 mod m实质上，a与互为逆元素。【例】对任何模数m1而言，至少有两个数有逆。即1， m1（mod m）（或1）（2） 性质【性质1】若a可逆，则（a，m）=1。（证）a可逆，则a的逆存在，且满足a1 （mod m）即存在整数k，使得a=1km= km1再由最大公因子的性质知（a，m）=（m，1）=1而 （a，m）=1 （a，m）=1且（，m）=1【推论】a是模m的逆的充分必要条件是（a，m）=1。【性质2】不唯一。即若存在，则km都是a的逆，其中k为任意整数。（证）只需直接验证：已知是a的逆，即a1 （mod m）那么，对任意整数k，有a(km) a akma01 （mod m）【例】设m7，a2，直接计算有，2(3)1 mod 7，241 mod 7，2111 mod 7，2181 mod 7，即对模7而言，整数47k都是2的逆（kz）【性质3】若b和c都是a的逆，则有bc （mod m）。（证）已知ab1 （mod m）， ac1 （mod m） 从而 abac （mod m）而(a,m)1，故由消去律知 bc （mod m）。【推论1】设整数a有逆，则整数b是a的逆的充分必要条件是b （mod m）。即b+km（kz）。（证）只要验证当b （mod m）时，b也是a的逆即可。显然。【例】设m50，3模50的逆为17，那么，只要b17 mod 50。如b，33，67，都是3的逆。反之，2017 mod 50，则20不是3的逆。【推论2】在模m的一个简化剩余系中，a的逆是唯一的。【例】设m7，选模7的最小正简化剩余系1，2，6，则a2的逆4且唯一。【性质4】（1）a。（2）（证）直接验证即可。【推论】。【例】设m55，求8和24模55的逆。（解）首先可以观察出2模55的逆为 28所以 7 mod 553739（3） 计算的方法【方法1】利用简化剩余类的性质枚举求逆例 m11，a5，则515， 5210， 534， 553，568， 591 9 mod 11【方法2】利用辗转相除法（即定理2.3.7的结论） 【方法3】利用有关性质（求大的数的逆）【方法4】利用欧拉函数和欧拉定理的结论（见后）2.4 欧拉定理 费马小定理(一) 欧拉定理【定理2.4.1】（Euler定理）（定理1）设m是大于1的整数，若整数a满足(a，m)1，则有1 （mod m）（证）设为m的最小正简化剩余系，则当(a，m)1时，也为模m的一个简化剩余系。故是模m的最小正剩余的某个排列。所以 （mod m）即 （mod m）又由(，m)1知，(，m)1，故有1 （mod m）【例1】（例1）设m7，a2，则(2，7)1 ，(7)6 模7的最小正简化剩余系为：1，2，3，4，5，6，则212，224，236，241，253，265 mod 7各等式两边相乘，有 mod 7即 mod 7而（，7）1，所以结论成立。【例3】（例3）设m11，a2，则(2，7)1 ，(11)10，故1 mod 11【例4】（例4）设m23，23a，则(a，23)1 ，(23)22，故1 mod 23（欧拉定理的）另一表示形式：设m是大于1的整数，若整数a满足(a，m)1，则有a （mod m）(二) 费马定理【定理2.4.2】（Fermat定理）（定理2）设p为素数，a为任意正整数，则a （mod p）（证）(1) ，则有0 （mod p） 0 （mod p）即 a （mod p）(2) pa，必有(a,p)1，由定理2.4.11 （mod p）两边同乘以a，得 a （mod p）【例】设p11，a2，则(11)10，故2 mod 11设p23，a10，则(23)22，故10 mod 23【推论】设m1，则m为素数的必要条件是：对某个ma的整数a，有1 （mod m）应用：用于否定一个整数为素数。意义：是判断一个正整数为素数的概率算法的理论基础。【例】设m20，a2，则 248 mod 20又 3 mod 30 20和30都是合数。又 1 mod 15，既不能肯定15是素数，也不能肯定15是合数。一般情况下要进行多次判断，例如：4 mod 15，所以15是合数。【例5】（例5）设p、q是两个不同的奇素数，npq，a是与n互素的整数。令整数e满足1e(n)且(e，(n)1，存在正整数d，使得d1 mod (n)， 1d(n)而且，对于整数c（ （mod n）（1cn），有a （mod n）（证）因(e，(n)1 ，故e的逆d存在，满足d1 mod (n)即存在正整数k，使ed1k(n)由定理2.4.1知 1 （mod p），所以 aa （mod p）同理可得 a （mod q）从而 a （mod n）即 a （mod n）【例6】（补）设p、q是两个不同的奇素数，npq，且设整数e、d满足d1 mod (n)， 1d(n)那么，对于整数c（ （mod n）（1cn），有a（mod n）。其中为任意整数。（证）设(a，n)d若d1，由例5知结论成立。若dn，则na，即 a0（mod n），从而c0（mod n）0a（mod n）若1dn ，不失一般性，设1an ，则必有akp（1kq）或akq（1kp）设akq，此时必有（a，p）1，那么有aa（mod p）和0a（mod q）所以 a （mod n）即 a （mod n）同理可证当akp时的情况。(三) 求的方法方法四、由Euler定理知 （mod m）而当mp为素数时， （mod m）(四) 威尔逊（Wilson）定理判断素数的方法之一【定理2.4.3】（Wilson定理）（定理3+补）p为素数(p1)!1 （mod p）（证）必要性：当p2时，显然成立（即1！1 mod 2）。设p3，由于1ap1时，(a，p)1，故a的逆（mod p）存在且1,2,p1中任一数的逆恰好也在中1,2,p1中。又 a （mod p） 1 （mod p）即 a1或 a11 （mod p）时其逆为本身。所以，(p2)这p3个数两两互相为逆。那么，(p2)(p1)1(p1) 1 （mod p）充分性：用反证法。已知 (p1)!1 （mod p），由同余性质知 (p1)! (1) (p1)!1c1 （*）若pab为合数，则p，从而由上式知 c1又 1ap（且1bp），那么，必有 (p1)!c (c1)c1 矛盾。故p为素数。【例】设p7，则 241，351 （mod 7）即4，5，2，3（mod 7）以及1，6（mod 7），从而有 6(24)(35)661 mod 7又设p11，则261， 341， 591， 781（mod 11） 10(26)(34) (59) (78)6101（mod 7）2.5 模重复平方计算法目的：快速计算a （mod m） （1）(一) 问题常规思路，递归地计算（1）式： （mod m）运算量：n1次乘法。(二) 模重复平方计算法原理表n为二进制n，即n其中 0，1，i0,1,k。则 （mod m）运算量：乘法次数(1+2+ k)+k（计算最多需要i次乘法）。最少运算量：乘法次数k+k2k（利用计算）(三) 模重复平方计算法（0） 令a1，表n为二进制n（1） 如果1，计算 ab （mod m），否则，令 a计算 （mod m）（2） 如果1，计算 （mod m），否则，令 计算 （mod m）（k ）如果1，计算 （mod m），否则，令 计算 （mod m）（k1）如果1，计算 （mod m），否则，令 最后，a（mod m）特点：由n的低位到高位计算(四) 方法二思路借鉴多项式求值的秦九韶算法：计算多项式P(x)的值。常规计算的乘法运算量为Ln(n1)21n(n1)2快速算法：P(x)运算量：n次乘法，n次加法。例如，P(x)计算 P(5)特殊多项式：系数0，1P(x)计算特殊值：P(2) 23思路：运算变换加法乘法， 乘法乘方例 (五) 理论基础r(ab) （mod m）(a （mod m）)(b （mod m）) （mod m）基本乘方：bb， 用1次乘法， 用2次乘法， 用3次乘法， 用k次乘法一般乘方：b， 用4次乘法， 用6次乘法 用17次乘法更一般情形：为计算，表n为二进制n，则n从而 所以 （mod n）(六) 算法：求 表n为二进制nx0；y1;for k downto 0 do x2*x; yy*y （mod m）;if 1 then x; yy*b; return y特点：由n的高位到低位计算【例1】计算 mod 561（31117），计算过程各变量的值如下表i98765432101000110000x1248173570140280560y749157526160241298166671又如n77 i65432101001101x1249193877y749157526559196268【例2】 （2次平方，1次乘法）， （3次平方，2次乘法），（从n的二进制分解角度，63211次平方，3次乘法）（从算法角度，6次平方，3次乘法）， （实质结果，不算0的情形且嵌套起来。即计算a的64次方项时利用好a的2、4、8、16、32次方项） （6次平方，2次乘法）， （从算法角度，9次平方，2次乘法） （实质结果，即不算0的情形且嵌套起来）2.6 一次不定方程2. 6. 1 二元一次（不定）方程(一) 二元一次（不定）方程的整数解【定义2.6.1】二元一次（不定）方程是指n （1）其中、n是给定的整数（0），x,y是变数（或变量）【例】二元一次（不定）方程5x+8y24直观求解：穷举并利用整除性原方程变形5x24-8y，即x(24-8y)/5令y=0，2，3，计算得解(x,y)=， (8,-2)，(0,3)，(-8,8) ，(-16