数论算法讲义2章(同余运算).doc

《数论算法讲义2章(同余运算).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章同余运算（一）内容l同余概念l性质l剩余类→整数分类l模幂运算（二）重点l同余及其计算（三）应用：l密码学l公钥密码学【例】RSA公钥算法：准备：选大素数p、q，记n＝pq，φ(n)＝(p－1)(q－1)，再选正整数e，满足（e，φ(n)）≡1（modn）并求d，满足ed＝1（modφ(n)）加密：明文串P编码为数字M，则密文C≡（modn）解密：M≡（modn），再将数字M解码得明文串P2.1同余的概念及基本性质(一)同余概念【定义2.1.1】给定一个正整数m，两个整数a、b叫做模m同余，如果a－b被m

2、整除，或，记作；否则叫做模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】（定理1）设m是一个正整数，a、b是两个整数，则a≡b（modm）存在整数k，使得a＝b＋km。（证）a≡b（modm）存在k，使得a－b＝km，即a＝b＋km【性质2】（定理2）同余是一种等价关系。即（i）

3、自反性：a≡am（ii）对称性：a≡b（modm）b≡a（modm）（iii）传递性：a≡bmodm且b≡c（modm）a≡c（modm）（证）（i）m│0＝a－aa≡am（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】【性质3】（等价定义）（定理3）整数a、b模m同余a、b被m除的余数相同。（证）由欧几里得除法，存在q，r，，，使得＝qm＋r，b＝m＋

4、即a－b＝(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】（定理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＋hk

5、m)m由性质1即得结论。一般情形：（modm）（i＝1,2,…,k），则（i）（modm）（ii）（modm）【推论1】a≡b（modm）na≡nb（modm），其中n为正整数。【推论2】a≡b（modm）（modm），其中n为正整数。【推论3】（定理5）x≡y（modm），（modm）（i＝1,2,…,k），则≡（modm）【例6】（例6）2003年5月9日是星期五，问此后的第22003是星期几？（解）22003＋5≡＋5mod7≡＋5mod7≡9mod7≡2mod7【例】（定理6）设十进制整数n＝，则3│n

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

7、76能否被11、2、4、8、16整除。因为（6+5+3+1+9）－（7+4+2+8）＝3，故n不能被11整除因2│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应用：求值a＋b（modm）＝（（a（modm））＋（b（modm）））（modm）ab（modm）＝（（a（modm））（b（modm）））（modm）na（modm）＝n(a（modm）)（modm）（modm）＝（modm）【性质5】（定理8）消去律

8、：设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）【例】（例11）95≡25mod7，且（5，7）＝1，故19≡5mod7【反例】（补）115≡25mod15，即23×5≡5×5mod15，但23≠5mod15。因为（5，15）＝5＞1【性质6】（定理9）a