第三讲同余理论.doc

第二章 同余理论2.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】设m是一个正整数，a、b是两个整数，则ab（mod m）存在整数k，使得abkm。（证）ab（mod m） 存在k，使得 abkm，即abkm【性质2】同余是一种等价关系。即自反性：aa（mod m）对称性：ab（mod m） ba （mod m）传递性：ab（mod m）且bc （mod m） ac （mod m）（证）（i）m0aa aa（mod 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】（等价定义）整数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】设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】xy （mod m）， （mod m）（i1,2,k），则 （mod m）【例6】2003年5月9日是星期五，问此后的第22003天是星期几？（解） 2200355 (mod 7）5 (mod 7）9 (mod 7）2 (mod 7）【例7】设十进制整数n，则3n 39n 9（证）因n (mod 3)n (mod 9)【例8】设整数n的1000进制表示式为n则7（或11，或13）n 7（或11，或13）（证）因n mod 7n mod 11n mod 13例如，判断n12345678能否被7(或11，或13)整除：123456781210002+3451000+678而 (12+678)345345不能被7、11、13整除故1234567不能被这3个数整除。【例9】设十进制整数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【性质5】消去律：设adbd （mod m）。若（d，m）1，则ab （mod m）。（证）adbd （mod m） mad bd(ab)d而（d，m）1，故m(ab)，即 ab （mod m）【例10】9525 (mod 7)，且（5，7）1，故195(mod 7)【反例11】11525 (mod 15)，即23555(mod 15)，但235(mod 15)。因为（5，15）51【性质6】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】ab （mod m）且dm，则ab mod d（证）ab （mod m） mab又 dm dab即 ab mod d另有一些性质，这里就不再一一列举，有兴趣的同学可参阅相关参考书。2.2剩余类和完全剩余系设m为正整数，记非空，至少a【定理2.2.1】设m是一个正整数，则（i） 任一整数必包含在某个中，0rm1（ii） ab （mod m）（iii） ab （mod m）【定义2.2.1】叫做模m的a的剩余类。一个剩余类中的任一个数叫做该类的剩余或代表。若是m个整数，且其中任何两个都不在同一个剩余类中，则称为模m的一个完全剩余系。【注】每个剩余类中都包含了无穷多个整数，而完全剩余系则恰好由m个数组成。模m的剩余类共有m个，例如【例13】设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】整数为m的一个完全剩余系 mod m。其中（0ijm1）【例14】m的典型完全剩余系：最小非负完全剩余系：0，1，m1最小正完全剩余系：1，2，m最大非正完全剩余系：0，1，(m1)最大负完全剩余系：1，2，m【定理2.2.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的一个完全剩余系。【例15】（例3）设m10，原剩余系为0，1，9。当a7，b5时，新的剩余系为：5，12，17，68 当a3，b6时，新的剩余系为：6，9，12，33 【定理2.2.4】设是两个互素的正整数，若分别遍历的完全剩余系，则遍历模的完全剩余系。（证）当分别遍历个整数时，遍历个整数。问题转化为：证明个整数模两两不同余。用反证法：若存在和满足 mod 则由2.1节性质7知 mod 即 mod 而（m1,m2）1，故由同余的性质知 mod 同理可证， mod 。【例16】设p、q是两个不同的素数，npq，则对任意整数c，存在唯一的一对数x和y，满足qxpyc （mod n）， 0xp，0yq（证）首先知p、q互素。再由定理2.2.4，当x、y分别遍历模p、q的完全剩余系时，qxpy遍历模npq的完全剩余系。故存在唯一的一对整数x、y，满足上式。2.3简化剩余系和欧拉函数【定义2.3.1】（定义1）设n为正整数，则1,2,n中与n互素的整数的个数，记作(n)，叫做欧拉（Euler）函数。【例17】（例1）设n10，则1,2,10中与10互素的数为 1,2,7,9，故(10)4【例18】(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欧拉函数的若干性质：【性质1】设p为素数，则(p)p1。 【性质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)【例19】(143)(1113)(11)(13)1012120 【性质4】设整数n，其中p，q为不同的素数，则(n)()()()证明：略【推论】设整数n有标准分解式，则(n)【例20】(100)(2252)10040(360)(23325)36096【性质5】欧拉函数是乘性函数（或称积性函数）。即若正整数m，n互素，则(mn)(m)(n)。（证）记m、n的标准分解式分别为，n则(mn)(m)(n)【例21】设m33，n32，求(3332)。（解）(33，32)1，故(3332)(33)(32) 3332160【定义2.3.2】一个模m的剩余类叫做简化剩余类（或互素剩余类、既约剩余类、不可约剩余类），如果该类中存在一个与m互素的剩余。注：本定义与剩余的选取无关。比如：对于 m=20而言，都是20的简化剩余类，却不是【定理2.3.1】设、是同一剩余类中的两个剩余，则与m互素的充分必要条件是与m互素。（证）由题设知 km再由最大公因子性质知（，m）（，m） （，m）1 （，m）1【定义2.3.3】设m为正整数，在模m的所有不同简化剩余类中，从每个类任取一个数组成的整数集合，叫做模m的一个简化剩余系（或称为缩系、互素剩余系、既约剩余系、不可约剩余系）。【例22】模6的简化剩余系为1，5模20的简化剩余系为1,3,7,9,11,13,17,19【定理2.3.2】m的简化剩余系的元素个数为【例23】素数p的简化剩余系为 1，2，p1，即p1【定理2.3.3】设整数，均与m互素，且两两模m不同余，则它们构成模m的一个简化剩余系。【定理2.3.4】设整数，均与m互素，若它们构成模m的一个简化剩余系，则这些必两两模m不同余。（证）由题意知，是来自模m的不同简化剩余类的剩余，而不同剩余类中的数必互不同余。【推论】设整数，均与m互素，则它们构成模m的简化剩余系的充分必要条件是这些两两模m不同余。【定理2.3.5】设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的一个简化剩余系。【例24】（例7）已知1，7，11，13，17，19，23，29是模30的简化剩余系，(7，30)1，则7，49，77，91，119，133，161，203也是模30的简化剩余系。【定理2.3.6】设m为正整数，a是满足(a，m)1的整数。则存在整数（1m）使得1 （mod m）（证）（构造性证明）由(a，m)1知存在整数s，t，使得satm(a，m)1即sa1(t)m因此，所求s。【例25】设m737，a635，求，满足aa1 （mod m）（解）利用广义欧几里得除法，可找到s224，t193，使得(224) 6351937371 a224513 （mod 737）即 635(224) 1 （mod 737）【定义2.3.4】将定理2.3.7中满足条件的叫作a（对模m）的逆，记为。即 1 mod m实质上，a与互为逆元素。【例26】对任何模数m1而言，至少有两个数有逆。即1， m1（mod m）（或1）关于模逆元的性质：【性质1】若a模m可逆，则（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）【例27】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的逆即可。显然。反之，2017 mod 50，则20不是3的逆。【推论2】在模m的一个简化剩余系中，a的逆是唯一的。【例28】m7，选模7的最小正简化剩余系1，2，6，则a2的逆4且唯一。性质4】（1）a。（2）（证）直接验证即可。【推论】。【例】设m55，求8和24模55的逆。（解）首先可以观察出2模55的逆为 28所以 7 mod 553739计算的方法【方法1】利用简化剩余类的性质枚举求逆例 m11，a5，则515， 5210， 534， 553，568， 591 9 mod 11【方法2】利用辗转相除法【方法3】利用欧拉函数和欧拉定理的结论2.4欧拉定理与费马小定理【定理2.4.1】（Euler定理）设m是大于1的整数，若整数a满足(a，m)1，则有1 （mod m）（证）设为m的最小正简化剩余系，则当(a，m)1时，也为模m的一个简化剩余系。故是模m的最小正剩余的某个排列。所以 （mod m）即 （mod m）又由