1、主要内容同余的定义、性质、剩余类和完全剩余系、欧拉函数、简化剩余系、欧拉定理、费尔马小定理第二章第二章 同余同余*1、同余的概念 :定义 2. 1若 a 和 b 除以 m 所得余数不同，则称 a， b 对模 m 不同余，记作a b (mod m). 设 m为正整数，称为模。若用 m去除两个整数 a 和 b 所得的余数相同，则称 a 和 b 对模 m 同余 , 记作a b (mod m). （ 1）读作 a 同余于 b 模 m。一、同余的概念及基本性质*2、同余的性质：(1) 反身性： a a (mod m).(2) 对称性：若 a b (mod m)，则 b a (mod m). (3) 传递
2、性：若 a b (mod m),b c (mod m),则 a c (mod m).(4) 若 a b (mod m)， c d (mod m) ， 则 a + c b + d (mod m) , a c b d (mod m).同余式可以相加减。* 我喜欢数学E性质 (5) 若 a b (mod m)， c d (mod m) ， 则 ac bd (mod m) . 同余式可以相乘。推论 若 a b (mod m)，则 a k b k (mod m), k 为任意整数 . 同余式的数乘。推广推广*性质 (6)性质 (7) 若 a =a1d, b =b1d, (m, d) =1, a b (m
3、od m)，则 a1 b1 (mod m) .性质 (8) d为为 a， b及及 m的任一正公约数，则的任一正公约数，则若 a b (mod m)， k 为正整数 ， 则 ka kb (mod km) .*性质 (9)若 a b (mod m1), a b (mod m2), m= m1, m2 , 则 a b (mod m) . 性质 (10) 设 d 1， d | m，若 a b (mod m) ， 则 a b (mod d ) .E New若 a b (mod m)，则 (a， m) = (b， m).性质 (11)*弃九法弃九法 正整数四则运算 (含乘方 ) 的快速验算方法例 7 用
4、弃九法 验算 2894734578 =1001865676 是否正确 .弃九法只是运算结果正确的必要条件，而非充分条件 ! 因此只能 判误 .289473 (mod 9), 345780 (mod 9)应有 2894734578 0 (mod 9), 而1001865676 0 (mod 9), 所以计算必有错误 .解 若通过计算， a、 b的和与积分别是 s与 p. 而 r1、 r2、r3、 r4 分别是 a、 b、 s、 p被 9 除所得的余数 , 由 同余的加减乘性质 可知， 如果 r1 +r2与 r3、 r1 r2与 r4关于模 9 不同余，那么计算一定错了 .*二、剩余类与剩余系定理
5、 2.2.1 设 m为正整数，则全部整数可分成 m个集合 ,记作 0， 1， ， m 1，其中 r (0 r m 1)是由一切形如 mq + r (q Z) 的整数所组成的，并且具有下列性质：(1)每一整数必包含在而且仅在上述的一个集合中 .(2)两个整数同在一个集合中的充分必要条件为这两个整数对模 m 同余。*定义 2. 2 设 m为正整数，则全部整数分成的 m个集合 0， 1， ， m 1称为 模 m的剩余类 ,一个 剩余类 中任一数叫做它的同类的数的剩余。*定理 2.2.2 设 m为正整数，则（ 1）在任意取定的 m + 1 个整数中，必有两个数对模 m 同余。（ 2）存在 m 个数两两对模 m不同余。完全剩余系定义 2. 3 设 m 为正整数，则从模 m 的每个剩余类中各取一个数所作成的集合，称为模 m 的一个 完全剩余系 .
