第3章同余课件.pptVIP

第三章 同 余 §3.1 同余的基本性质 作业： . 已知99? ，求?与? §3.2 剩余系与完全剩余系 §3. 简化剩余系 * * 初等数论 初等数论 美丽有两种 一是深刻又动人的方程一是你泛着倦意淡淡的笑容 定义1 给定正整数m，如果整数a与b之差被m整除，则称a与b对于模m同余，或称a与b同余，模m，记为 a ? b (mod m)， 此时也称b是a对模m的同余。 如果整数a与b之差不能被m整除，则称a与b对于模m不同余，或称a与b不同余，模m，记为 a b (mod m) 《初等数论》 ———————————————————————————————————————— 定理1 下面的三个叙述是等价的： (ⅰ) a ? b (mod m)； (ⅱ) 存在整数q，使得a = b ? qm； (ⅲ) 存在整数q1，q2，使得a = q1m ? r，b = q2m ? r，0 ? r m。 定理2 同余具有下面的性质： (ⅰ) a ? a (mod m)； (ⅱ) a ? b (mod m) ? b ? a (mod m)； (ⅲ) a ? b，b ? c (mod m) ? a ? c (mod m)。 《初等数论》 ———————————————————————————————————————— 定理3 设a，b，c，d是整数，并且 a ? b (mod m)，c ? d (mod m)， (1) 则： (ⅰ) a ? c ? b ? d (mod m)； (ⅱ) ac ? bd (mod m)。 证明： (ⅰ) 由式(1)及定义1可知 m?a ? b，m?c ? d， 因此： m?(a ? c) ? (b ? d)，此即结论(ⅰ)； (ⅱ) 由式(1)及定理1可知，存在整数q1与q2使得 a = b ? q1m，c = d ? q2m， 因此 ac = bd ? (q1q2m ? q1d ? q2b)m， 再利用定理1，推出结论(ⅱ)。 证毕。 《初等数论》 ———————————————————————————————————————— 定理4 设ai，bi（0 ? i ? n）以及x，y都是整数，并且x ? y (mod m)，ai ? bi (mod m)，0 ? i ? n， 则 (mod m)。 (2) 定理5 下面的结论成立： (ⅰ)a ? b(mod m)，d?m，d 0 ? a ? b (mod d)； (ⅱ) a ? b (mod m)，k 0，k?N ? ak ? bk (mod mk)； (ⅲ) a ? b (mod mi )，1 ? i ? k ? a? b (mod [m1, m2, ?, mk])； (ⅳ) a ? b (mod m) ? (a, m) =(b,m)； (ⅴ) ac?bc(mod m)，(c, m) = 1 ? a ? b (mod m)。 《初等数论》 ———————————————————————————————————————— 例1 设N = 是整数N的十进制表示，即N = an10n ? an?110n?1 ? ? ? a110?a0 ，则 (I) (3)9|N ? (3)9 ； (II) 11|N ? 11 ； 例2 求(25733 ? 46)26被50除的余数。 解 利用定理4有 (