资源描述：
《数学竞赛辅导讲座同余》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数学竞赛辅导讲座：同余知识、方法、技能同余是数论中的重要概念，同余理论是研究整数问题的重要工作之一.本讲介绍同余的基本概念，剩余类和完全剩余系，同余方程，整数模的阶和中国剩余定理.Ⅰ.基本概念定义一：设m是一个给定的正整数.如果两个整数a、b用m除所得的余数相同，则称a、b对模m同余，记为a≡b（modm）；否则，记为a≡b（modm）.例如，15≡7（mod4），－23≡12（mod7）.同余有如下两种等价定义法：定义一*若m
2、a－b，则称a、b对模m同余.定义一**若a=b+mt(t∈Z)，则称a、b对模m同余.同余
3、的基本性质：（1）（2）（3）若①②（4）若特别地，设，则（5）若特别地，又若（c,m）=1，则-12-【证明】因这等价于又因若（a,b）==1（d≠0）及b
4、ac，且（b,c）=1从而有这个性质说明同余式两边的同一非零因数，不能像等式那样“约去”，只有当这非零因数与模互质时，才可“约去”.（6）而（7）设①若c>0，则②d为a、b、m的任一公约数，则（8）若（9）若Ⅱ.剩余类和完全剩余系若按对某一模m的余数进行分类，就可以引入所谓的剩余类和完全剩余系的概念.定义二：设m∈N*，把全体整数按其对模m的余数r（0≤r≤m－
5、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-12-个数组成的一个组称为模m的一个完全剩余系，简称完系.例如，取m=4，则有，k2={…，－6，－2，2，6，10，…}，k3={…，－5，－1，3，7，11，…}.数
6、组0，1，2，3；－8，5，2，－1等等都是模的4的一个完全剩余系.显然，模m的完全剩余系有无穷多个.但最常用的是下面两种：（1）非负数最小完全剩余系：0，1，2，…，m－1；（2）绝对值最小完全剩余系：它随m的奇偶性不同而略有区别.当（对称式）当由定义不难得到如下判别完全剩余系的方法：定理一：m个整数是模m的一个完系≡定理二：设（b,m）=1，c为任意整数.若为一个完系，则也是模m的一个完全剩余系.特别地，任意m个连续整数构成模m的一个完全剩余系.【证明】只需证明：当而这可用反证法得证.下略.设m为一正整数，由于在0，
7、1，…，m－1中与m互质的数的个数是由m惟一确定的一个正整数，因此，可给出如下定义.定义四：m为一正整数，把0，1，…，m－1与m互质的数的个数叫做m的欧拉函数，记为显然，的定义域是正整数N*，前n个值为：当m=p为质数时，设k是模的一个剩余类.若a、b∈k，则于是由性质9知，（a,m）=（b,m）.因此，若（a,m）=1，则k中的任一数均与m互质.这样，又可给出如下定义定义五：如果一个模m的剩余类kr中任一数与m互质，则称kr是与模m互质的剩余类；在与模m互质的每个剩余类中任取一个数（共个）所组成的数组，称为模m的一个
8、简化剩余系.-12-例如，取m=6，在模6的六个剩余类中，是与模6互质的剩余类.数组1，5；7，－7；1，－1；等等都是模6的简化剩余类.由此定义，不难得到：定理三:是模m的简化剩余系定理四：在模m的一个完全剩余系中，取出所有与m互质的数组成的数组，就是一个模m的简化剩余系.这两个定理，前者是简化剩余系的判别方法，后者是它的构造方法.显然，模m的简化剩余系有无穷多个，但常用的是“最小简化剩余系”，即由1，2，…，m－1中与m互质的那些数组成的数组.由定理不难证得简化剩余系的如下性质定理.定理五：设是模m的简化剩余系.若（
9、k,m）=1，则也是模m的简化剩余系.下面介绍两个有关欧拉函数的重要结论.其证明略.定理六：（欧拉定理）若（a,m）=1，则特别地，（费马小定理）若m=p为质数，pa，则定理七：（威尔逊定理）设p素数，则（p－1）！定理八：（欧拉函数值计算公式）令m的标准分解式为，则例如，30=2·3·5，则读者应认识到：由于任何整数都属于模m的某一剩余类，所以，在研究某些整数性质时，选取适当的（模）m，然后在模m的每个剩余类中取一个“代表数”（即组成一个完全剩余系），当弄清了这些代表数的性质后，就可弄清对应的剩余类中所有数的性质，进而
10、弄清全体整数的性质，这就是引入剩余类和完全剩余系的目的.Ⅲ.同余方程设的整系数多项式.类似于多项式和代数方程式的有关定义，我们有-12-定义六：同余式叫做一元n次同余方程.例如，是七次同余方程.定义七：若c使得叫做同余方程的一个解.显然，同余方程的解是一些剩余类，而不仅是一个或n个类.例如，都是二次同余方程的解.1．
