第三讲同余理论（精）

《第三讲同余理论（精）》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章同余理论2.1同余的概念和基本性质【定义2.1.1】给定一个正整数m，两个整数a、b叫做模m同余，如果a－b被m整除，或，记作；否则叫做模m不同余，记作a≠b（（modm））【注】由于等价于，所以同余式等价于，故以后总假定模。【例1】7│28＝29－1，故29≡1（mod7）；7│21＝27－6，故27≡6（mod7）；7│28＝23－（－5），故23≡－5（mod7）；同余运算的相关性质：【性质1】设m是一个正整数，a、b是两个整数，则a≡b（modm）存在整数k，使得a＝b＋km。（证）a≡b（modm）存在k，使得a－b＝km，即a＝

2、b＋km【性质2】同余是一种等价关系。即自反性：a≡a（modm）对称性：a≡b（modm）b≡a（modm）传递性：a≡b（modm）且b≡c（modm）a≡c（modm）（证）（i）m│0＝a－aa≡a（modm）（ii）a≡b（modm）m│a－bm│b－a＝－(a－b)b≡a（modm）（iii）a≡b（modm），b≡c（modm）m│a－b，m│b－cm│(a－b)＋(b－c)＝a－ca≡c（modm）【性质3】（等价定义）整数a、b模m同余a、b被m除的余数相同。（证）由欧几里得除法，存在q，r，，，使得＝qm＋r，b＝m＋即a－b

3、＝(q－)m＋(r－)或（r－）＝(a－b)－(q－)m故m│(a－b)m│(r－)但0≤│r－│＜m且m│(r－)r－＝0故m│(a－b)r－＝0，即r＝【性质4】设m为正整数，a、b、c、d为整数，若a≡b（modm），c≡d（modm）则（i）a＋c≡b＋d（modm）；（ii）ac≡bd（modm）。（证）已知a≡b（modm）且c≡d（modm）a＝b＋hm且c＝d＋kma＋c＝(b＋hm)＋(d＋km)＝b＋d＋(h＋k)m，ac＝(b＋hm)(d＋km)＝bd＋(hd＋kb＋hkm)m由性质1即得结论。一般情形：（modm）（i＝1

4、,2,…,k），则（i）（modm）（ii）（modm）【推论1】a≡b（modm）na≡nb（modm），其中n为正整数。【推论2】a≡b（modm）（modm），其中n为正整数。【推论3】x≡y（modm），（modm）（i＝1,2,…,k），则≡（modm）【例6】2003年5月9日是星期五，问此后的第22003天是星期几？（解）22003＋5≡＋5(mod7）≡＋5(mod7））≡9(mod7）≡2(mod7）【例7】设十进制整数n＝，则3│n3│9│n9│（证）因n＝≡(mod3)n＝≡(mod9)【例8】设整数n的1000进制表示式为

5、n＝则7（或11，或13）│n7（或11，或13）│－（证）因n＝≡mod7n≡mod11n≡mod13例如，判断n＝12345678能否被7(或11，或13)整除：12345678＝12×10002+345×1000+678而(12+678)－345＝345不能被7、11、13整除故1234567不能被这3个数整除。【例9】设十进制整数n＝，则11│n11│－2│n2│4│n4│4│8│n8│8││n│例如，判断n＝981234576能否被11、2、4、8、16整除。因为（6+5+3+1+9）－（7+4+2+8）＝3，故n不能被11整除因2│6

6、，故2│n4├76或4├2×7+6＝22，故4├n8│4×5+2×7+6＝40，故8│n因8×4+4×5+10×7+6≡0mod16，故16│n【性质5】消去律：设ad≡bd（modm）。若（d，m）＝1，则a≡b（modm）。（证）ad≡bd（modm）m│ad－bd＝(a－b)d而（d，m）＝1，故m│(a－b)，即a≡b（modm）【例10】95≡25(mod7)，且（5，7）＝1，故19≡5(mod7)【反例11】115≡25(mod15)，即23×5≡5×5(mod15)，但23≠5(mod15)。因为（5，15）＝5＞1【性质6】a≡

7、b（modm）且k＞0，则ak≡bk（modmk）（证）a≡b（modm）m│a－bmk│(a－b)k＝ak－bkak≡bk（modmk）【例12】19≡5(mod7)，k＝4＞0，所以76≡20(mod28)【性质7】a≡b（modm）且d│m，则a≡bmodd（证）a≡b（modm）m│a－b又d│md│a－b即a≡bmodd另有一些性质，这里就不再一一列举，有兴趣的同学可参阅相关参考书。2.2剩余类和完全剩余系设m为正整数，记＝非空，至少a∈【定理2.2.1】设m是一个正整数，则（i）任一整数必包含在某个中，0≤r≤m－1（ii）＝a≡b（

8、modm）（iii）＝φa≠b（modm）【定义2.2.1】叫做模m的a的剩余类。一个剩余类中的任一个数叫做该类的剩余或代表。若是m个整