《数论算法》 第二章 同余运算
第 2 章 同余运算
内容 1. 同余概念 2. 性质 3. 剩余类→整数分类 4. 模幂运算 5. 一次不定方程 同余及其计算 要点
应用：
? 密码学
? 公钥密码学
【例】 RSA公钥算法：
准备：选大素数p、q，记n＝pq，φ(n)＝(p－1)(q－1)，再选正整数e，满足
（e，φ(n)）≡1（mod n）
并求d，满足 ed＝1（mod φ(n)）
加密：明文串P编码为数字M，则密文C≡Me （mod n） 解密： M≡Cd（mod n），再将数字M解码得明文串P
2.1 同余的概念及基本性质
(一) 同余概念
【定义2.1.1】给定一个正整数m，两个整数a、b叫做模m同余，如果a－b被m整除，即m|a?b，记作a≡b（mod m）；否则叫做模m不同余，记作ab（mod m）
【注】 ∵ m|a?b??m|a?b
1/57
《数论算法》 第二章 同余运算
∴ a≡b（mod m）?a≡b（mod －m）
假定：模m?1。
判断同余的方法一：利用定义
【例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）； (二) 性质
【性质1】设m是一个正整数，a、b是两个整数，则a≡b（mod m）?存在整数k，使得a＝b＋km。
（证）a≡b（mod m） ? m|a?b
? 存在k，使得 a－b＝km，即a＝b＋km
【性质2】同余是一种等价关系。即 （i） 自反性：a≡a（mod m）
（ii） 对称性：a≡b（mod m）? b≡a（mod m） （iii） 传递性：a≡b（mod m）且b≡c（mod m）
a≡c（mod m） （证）（i）m│0＝a－a
?
? a≡a（mod m）
（ii）a≡b（mod m）? m│a－b ? m│b－a＝－(a－b) ? b≡a（mod m）
（iii）a≡b（mod m），b≡c（mod m）? m│a－b，m│b－c
? m│(a－b)＋ (b－c)＝a－c ? a≡c（mod m）
【例3】
2/57
《数论算法》 第二章 同余运算
【性质3】（等价定义）整数a、b模m同余?a、b被m除的余数相同。
（证）由欧几里得除法，存在q，r，q?，r?，使得
a＝qm＋r，b＝q?m＋r?
即 a－b＝(q－q?)m＋(r－r?) 或 （r－r?）＝(a－b)－(q－q?)m 故 m│(a－b) 故 m│(a－b)
? m│(r－r?)
? r－r?＝0
? r－r?＝0，即r＝r?
但 0?│r－r?│＜m且m│(r－r?)
【性质4】设m为正整数，a、b、c、d为整数，若
a≡b（mod m）， c≡d（mod m）
则
（i） a＋c≡b＋d（mod m）； （ii） ac≡bd（mod m）。
（证）已知a≡b（mod m）且 c≡d（mod m）
? 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即得结论。
一般情形：ai?bi （mod m）（i＝1, 2, …, k），则 （i）
?ai??bi（mod m）
i?1ki?1ki?1i?1kk（ii）
?ai??bi（mod m）
【推论1】a≡b（mod m）? na≡nb（mod m），其中n为正整数。
3/57