约4430字 数学奥赛辅导 第三讲 同余
　　知识、方法、技能
　　同余是数论中的重要概念，同余理论是研究整数问题的重要工作之一.本讲介绍同余的基本概念，剩余类和完全剩余系，同余方程，整数模的阶和中国剩余定理.
　　Ⅰ.基本概念
　　定义一：设m是一个给定的正整数.如果两个整数a、b用m除所得的余数相同，则称a、b对模m同余，记为a≡b（modm）；否则，记为a≡b（modm）.
　　例如，15≡7（mod4），－23≡12（mod7）.
　　同余有如下两种等价定义法：
　　定义一* 若m|a－b，则称a、b对模m同余.
　　定义一**若a=b+mt(t∈Z)，则称a、b对模m同余.
　　同余的基本性质：
　　（1） 
　　（2） 
　　
　　（3）若 
　　① 
　　② 
　　（4）若 特别地，设 ，则 
　　（5）若 特别地，又若（）=1，则 
　　【证明】因 这等价于 又因若（a,b）= =1（d≠0）及b|ac，且（b,c）=1 
　　从而有 
　　这个性质说明同余式两边的同一非零因数，不能像等式那样“约去”，只有当这非零因数与模互质时，才可“约去”.
　　（6） 而 
　　（7）设 
　　①若c>0，则 
　　②d为a、b、m的任一公约数，则 
　　（8）若 
　　（9）若 
　　Ⅱ.剩余类和完全剩余系
　　若按对某一模m的余数进行分类，就可以引入所谓的剩余类和完全剩余系的概念.
　　定义二：设m∈N*，把全体整数按其对模m的余数r（0≤r≤m－1）归于一类，记为kr，每一类kr（r=0,1,…,m－1）均称模m的剩余类（又叫同余类）.同一类中任一数称为该类中另一数的剩余.
　　剩余类kr是数集 ,它是一个公差为m的（双边无穷）等差数列.
　　根据定义，剩余类具有如下性质：
　　（1） 
　　（2）对任一数n∈Z，有惟一的 ；
　　（3）对任意的a,b∈Z，a,b 
　　定义三：设 是模m的（全部）剩余类.从每个kr中任取一个数ar,这m个数 组成的一个组称为模m的一个完全剩余系，简称完系.
　　例如，取m=4，则有 ，k2={…，－6，－2，2，6，10，…}，k3={…，－5，－1，3，7，11，…}.数组0，1，2，3；－8，5，2，－1等等都是模的4的一个完全剩余系.
　　显然，模m的完全剩余系有无穷多个.但最常用的是下面两种：
　　（1）非负数最小完全剩余系：0，1，2，…，m－1；