初等数论 第三章(1) 同余、剩余类
本章基本内容

同余：基本概念、性质、应用
剩余系、完全剩余系：定义、性质
简化剩余系、欧拉函数：定义、算法
欧拉定理、费马定理：内容、证明、应用

RSA体制：算法、正确性证明
2


本章所介绍的同余这一特殊语言在数论中极为有 用，它是由历史上最著名的数学家之一卡尔·弗 里德里希·高斯（Kar Friedrich Gauss）于19世纪 初提出的.
i 0 n
证 因 为 1 0 0 0 与-1 对 模 7 ( 或 1 1 , 或 1 3 ) 同 余 , 故 由 定 理 知 7(或11 或13)与 ( 1)i ai 对 模 7(或11或13)同 余 . 由 性 质 ， 7(或11或13)整 除 a
i 0 n
当 且 仅 当 7(或11或13)整 除 ( 1)i ai .
II 弃九法(验算整数计算结果的方法) 假 设 我 们 由 普 通 乘 法 的 运 算 方 法 求 出 整 数 a, b 的 乘 积 是 P, 并 令 a an10n an110n1 a0 ,0 ai 10， b bm10m bm110m1 b0 ,0 b j 10， P cl 10l + cl -110l -1 + + c0 ,0 ck 10， n m l 我 们 说 ： 如 果 ai b j ck (mod 9), 那 么 所 求 得 的 i =0 j 0 k =0 n m 乘 积 是 错 误 的. 因 为 定 理 2 及 性 质, ab ai b j (mod 9), i =0 j 0 l n m l P ck (mod 9). 若 ai b j ck (mod 9), 则 ab P k =0 i =0 j 0 k =0 (mod 9). 故 ab 不 是 P.
18
应用 检查因数的一些方法 A. 一整数能被3(9)整除的必要且充分条件是它的十进位 数 码 的 和 能 被 3 ( 9 ) 整 除. 证 显然我们只须讨论任一整数 a就够了.按照通常方法,把 a 写 成 十 进 位 数 的 形 式 ; 即 a an10n an110n1 a0 ,0 ai 10 因 1 0 1 ( m o d 3 ) , 故 定 理 得 a an an1 a0 (mod 3).由 性 质 知 3 a当 且 仅 当 3 ai .同 法 可 得 9 a当 且 仅 当 9 ai .
14
性 质 同 余 式 ca cb (mo d m) (7) 等 价 于 a b (mo d m / (c, m)). 特 别 地 , 当 (c, m) 1时 , 同 余 式 ( 7 ) 等 价 于 a b (mo d m), 即 同 余 式 两 边 可 约 去 c. 证 同 余 式 ( 7 ) 即 m c (a b), 这 等 价 于 m c (a b). (c, m ) ( c, m ) 由 定 理 及 ( m / (c, m), c / (c, m) ) = 1 知 , 这等价于 m (a b). (c, m )
i 0 i 0 n n
19
应用 检查因数的一些方法 B . 设 正 整 数 a an1000n an11000n1 a0 ,0 ai 1000 则 7 ( 或 1 1 , 或 1 3 ) 整 除 a的 必 要 且 充 分 的 条 件 是 7(或11或13) 整 除 ( a0 + a2 + ) - ( a1+ a3 + ) = ( 1)i ai

4
定 义 给 定 一 个 正 整 数 m, 把 它 叫 做 模. 如 果 用 m 去 除 任 意 两 个 整 数 a 与 b 所 得 的 余 数 相 同, 我 们 就 说 a , b 对 模 m 同 余 , 记 作 a b (mod m). 如 果 余 数 不 同, 我 们 就 说 a , b 对 模 m 不 同 余 , 记 作 a b (mod m).
11
定 理2 若 A1 k B1 k (mod m), xi yi (mod m), i 1,2,, k , 则

1 ,, k
k 1 A1 k x1 xk

1 ,, k
k 1 B1 k y1 yk (mod m).
特 别 地 , 若 ai bi (mod m), i 0,1,, n,则 an x n an1 x n1 a0 bn x n bn1 x n1 b0 (mod m).
例 7 2 ( m o d 5 ) , 7 1 2 ( m o d 5 ) , 7 9 (mo d 5)
5
同余在日常生活中的应用


钟表对于小时是模12或24的，对于分钟和秒是模60的
日历对于星期是模7的，对于月份是模12的


电水表通常是模1000的
里程表通常是模100000的
6
m a 可 记 为 a 0 (mod m),所 以 , 所 有 的 偶 数 可 以 表 为 a 0 (mod 2 ).由 于 奇 数 a 满 足 2 a 1,所 以 , 所 有 的 奇 数 可 以 表 为 a 1 (mod 2 ). 对 给 定 的 整 数 b 和 模 m , 所有同余于b 模m的数就是算术数列 b km , k 0, 1, 2,.

同余的语言使得人们能用类似处理等式的方式来 处理整除关系. 在引入同余之前，人们研究整除关 系所用的记号笨拙而且难用. 而引入方便的记号 对加速数论的发展起到了帮助作用.
3
§1 同余的概念及其基本性质

今天（2015年4月8日）是星期三，问明年的
今天是星期几？（2016年4月8日） 明年的今天（2016年4月8日）是星期五
10
同余可以相乘, 若 a1 b1 (mod m), a2 b2 (mod m), 则 a1a2 b1b2 (mod m), 特 别 地 , 若 a b (m od m),则 ak bk (mod m). 证 由 定 理 1, a1 b1 t1m, a2 b2 t2 m.因 此 a1a2 b1b2 (b1t2 b2t1 t1t2 m) m. 故 a1a2 b1b2 (m od m).
8
定 理 1 整 数 a , b 对 模 m同 余 的 充 要 条 件 是 m a b , 即 a b mt , t 是 整 数 . 证 设 a q1m r1 , b q2 m r2 ,0 r1 m,0 r2 m, 若 a b (mo d m),则 r1 r2 , 因 此 a b (q1 q2 )m. 反 之 ， 若 m a b ,则 m m(q1 q2 ) (r1 r2 ) , 因 此 , m r1 r2 . 但 r1 r2 m ,故 r1 r2 . 定 理 1 表 明 同 余 又 可 定 义 如 下 : 若 m a b, 则 a , b 对 模 m同 余 .
13
若 a b (mod mi ), i 1,2,, k ,则 a b (mod [ m1 , m2 ,, mk ]). 证 由 定 理 1, mi a b , i 1,2,, k , 再 由 第 一 章 §3 定 理 , 即 得 [ m1 , m2 ,, mk ] a b ,故 由 定 理1 即 证 得 . 若 a b (mod m), d m , d 0,则 a b (mod d ). 若 a b (mod m), 则( a, m) (b, m) ,因 而 若 d 能 整 除 m 及 a, b 二 数 之 一 , 则 d 必 能 整 除 a, b 中 另 一 个 .
15
性 质 若 m 1,(a, m) 1,则 存 在 c 使 得 ca 1 (mod m),我 们 把 c 称 为 是 a 对 模 m 的 逆 ， 记 作 a 1 b (mod m)或 a 1. 证 由 定 理 知 , 存 在 x0 , y0 , 使 得 ax0 my0 1. 取 c x0 既 满 足 要 求 . 由 此 提 供 一 种 求 a 1 (m od m)有 效 的 方 法 , 这是Euclid算法的又一重要应用.
16
例 求 模 p 11 所 有 元 的 逆 元 . 解 由 1 ( - 1 0 ) + 1 1 = 1 得 1 1 ( 10) 1 (mod 11) 由 2 ( - 5 ) + 1 1 = 1 得 2 1 ( 5) 6 (mod 11); 同样计算得： a a1 1 2 3 4 5 6 7 8 9 10 1 6 4 3 9 2 8 7 5 10
17
显 然 , a 对 模 m的 逆 c 不 是 惟 一 的 . 当 c 是 a 对 模 m 的 逆 时 , 任 一 c ' c (mod m)也 一 定 是 a 对 模 m 的 逆;由 性 质 知 ， a 对 模 m 的 任 意 两 个 逆 c1 , c2必 有 c1 c2 (mod m). 此 外 , 显 见 ( a 1 , m ) = 1 及 ( a 1 ) 1 a (mod m)
9
同余可以相加减 (i ) 若 a1 b1 (mod m), a2 b2 (mod m), 则 a1 a2 b1 b2 (mod m). ( i i ) 若 a b c (mod m),则 a c- b (mod m) . 证 由 定 理 1, a1 b1 mt1 , a2 b2 mt2 ,因 此 a1 a2 b1 b2 m(t1 t2 ),即 得 (i ). 由(i ) c - b c (b) (a b) (b) a (mod m).