（讲座一）1 2011 年协作体夏令营系列讲座(一 ) 初等数论中的同余问题 复旦附中 万军 同余的概念和性质： 设m 为非零整数，如果整数,a b 满足|mab，则称a 和b 对模m 同余，记为(mod)abm；否则称a 和b 对模m 不同余，记为(mod)abm． 注意到，||mabmab ，故(mod)(mod())abmabm，所以我们总是可以假定m 为正整数． 对于固定的模，同余有很多性质： 1）同余是一种等价关系，即有 ①自反性：(mod)aam； ②对称性：若(mod)abm，则(mod)bam； ③传递性：若(mod)abm，(mod)bcm，则(mod)acm． 2）加法、减法、乘法和乘方运算： 若(mod)abm，(mod)cdm，*nN 则(mod)acbdm，(mod)acbdm (mod)acbdm， (m od)nnabm． 3）除法运算： (mod)acbcm，则(mod)( ,)mabc m． 特别地，若( ,)1c m，则(mod)abm． 4）同余组： (mod)1, 2,,kabmkn同时成立的充要条件是12(m od[,,,])nabmmm 剩余类与完全剩余系： 设m 为一个给定的正整数，则全体整数可以分成m 个集，记为011,,,mKKK， 其中{|(m od)} ,0,1,,1rKxxrmrm，则称011,,,mKKK为模m 的剩余类． 模m 的剩余类有下列性质： 1）每个整数必属于且仅属于模m 的一个剩余类中； 2）两个整数同在一个剩余类中的充要条件是这两个整数模m 同余． 事实上，,i jZ，0≤ ij≤1m ，有10,mijrrKKKZ 如果m 个整数011,,,maaa中不存在两个数属于同一剩余类，则称011,,,maaa为模m 的一个完全剩余系（或称完系）． 最常用的剩余系0,1,,1m 称为模m 的非负最小完全剩余系． 此外也常用到绝对值最小完全剩余系，它们是： 当 m 为奇数时，11,,1, 0,1,,22mm 当 m 为偶数时，,,1, 0,1,,122mm或1,,1, 0,1,,22mm 完全剩余系有下列性质： 1）m 个整数011,,,maaa作为模m 的一个完全剩余系的充要条件是它们两两模m 不同余； 2）若011,,,maaa是模m 的一个完全剩余系，( ,)1,a mbZ， 那么011,,,maab aabaab也是模m 的一个完全剩余系； 也常这样描述：设m 是正整数，( ,)1,a mbZ，若x 通过模m 的一个完全剩余系， 则axb也通过模m 的一个完全剩余系． 3）若12,mm 是互质的两个正整数，而12,xx 分别通过12,mm 的一个完全剩余系， 则2112m xm x通过...
