《第三讲-同余系列竞赛》由会员分享，可在线阅读，更多相关《第三讲-同余系列竞赛（11页珍藏版）》请在金锄头文库上搜索。
1、 Http:/www.fhedu.c【高中数学奥赛金牌之路精华教案】数学奥赛辅导 第三讲 同余知识、方法、技能同余是数论中的重要概念，同余理论是研究整数问题的重要工作之一.本讲介绍同余的基本概念，剩余类和完全剩余系，同余方程，整数模的阶和中国剩余定理.基本概念定义一：设m是一个给定的正整数.如果两个整数a、b用m除所得的余数相同，则称a、b对模m同余，记为ab（modm）；否则，记为ab（modm）.例如，157（mod4），2312（mod7）.同余有如下两种等价定义法：定义一* 若m|ab，则称a、b对模m同余.定义一*若a=b+mt(tZ)，则称a、b对模m同余.同余的基本性质：（1）（
2、2） （3）若（4）若特别地，设，则（5）若特别地，又若（c,m）=1，则【证明】因这等价于又因若（a,b）=1（d0）及b|ac，且（b,c）=1从而有这个性质说明同余式两边的同一非零因数，不能像等式那样“约去”，只有当这非零因数与模互质时，才可“约去”.（6）而（7）设若c0，则d为a、b、m的任一公约数，则（8）若（9）若.剩余类和完全剩余系若按对某一模m的余数进行分类，就可以引入所谓的剩余类和完全剩余系的概念.定义二：设mN*，把全体整数按其对模m的余数r（0rm1）归于一类，记为kr，每一类kr（r=0,1,m1）均称模m的剩余类（又叫同余类）.同一类中任一数称为该类中另一数的剩余.
3、剩余类kr是数集,它是一个公差为m的（双边无穷）等差数列.根据定义，剩余类具有如下性质：（1）（2）对任一数nZ，有惟一的；（3）对任意的a,bZ，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，m1；（2）绝对值最小完全剩余系：它随m的奇偶性不同而略有区别.当（对称式）当由定
4、义不难得到如下判别完全剩余系的方法：定理一：m个整数是模m的一个完系定理二：设（b,m）=1，c为任意整数.若为一个完系，则也是模m的一个完全剩余系.特别地，任意m个连续整数构成模m的一个完全剩余系.【证明】只需证明：当而这可用反证法得证.下略.设m为一正整数，由于在0，1，m1中与m互质的数的个数是由m惟一确定的一个正整数，因此，可给出如下定义.定义四：m为一正整数，把0，1，m1与m互质的数的个数叫做m的欧拉函数，记为显然，的定义域是正整数N*，前n个值为：当m=p为质数时，设k是模的一个剩余类.若a、bk，则于是由性质9知，（a,m）=（b,m）.因此，若（a,m）=1，则k中的任一数均
5、与m互质.这样，又可给出如下定义.定义五：如果一个模m的剩余类kr中任一数与m互质，则称kr是与模m互质的剩余类；在与模m互质的每个剩余类中任取一个数（共个）所组成的数组，称为模m的一个简化剩余系.例如，取m=6，在模6的六个剩余类中，是与模6互质的剩余类.数组1，5；7，7；1，1；等等都是模6的简化剩余类.由此定义，不难得到：定理三:是模m的简化剩余系定理四：在模m的一个完全剩余系中，取出所有与m互质的数组成的数组，就是一个模m的简化剩余系.这两个定理，前者是简化剩余系的判别方法，后者是它的构造方法.显然，模m的简化剩余系有无穷多个，但常用的是“最小简化剩余系”，即由1，2，m1中与m互质
6、的那些数组成的数组.由定理不难证得简化剩余系的如下性质定理.定理五：设是模m的简化剩余系.若（k,m）=1，则也是模m的简化剩余系.下面介绍两个有关欧拉函数的重要结论.其证明略.定理六：（欧拉定理）若（a,m）=1，则特别地，（费马小定理）若m=p为质数，p a，则定理七：（威尔逊定理）设p素数，则（p1）！定理八：（欧拉函数值计算公式）令m的标准分解式为 ，则 例如，30=235，则读者应认识到：由于任何整数都属于模m的某一剩余类，所以，在研究某些整数性质时，选取适当的（模）m，然后在模m的每个剩余类中取一个“代表数”（即组成一个完全剩余系），当弄清了这些代表数的性质后，就可弄清对应的剩余类
7、中所有数的性质，进而弄清全体整数的性质，这就是引入剩余类和完全剩余系的目的.同余方程设的整系数多项式.类似于多项式和代数方程式的有关定义，我们有定义六：同余式叫做一元n次同余方程.例如，是七次同余方程.定义七：若c使得叫做同余方程的一个解.显然，同余方程的解是一些剩余类，而不仅是一个或n个类.例如，都是二次同余方程的解.1一次同余方程（其中m a）称为一次同余方程.关于它的解，有如下共知的结论：定理九：若（a,m）=1，则有一个解.定理十：若（a,m）=d1，d b，则无解，其中.定理十一：若（a,m）=d1，d|b，则有d个解.并且，若的一个解为则d个解为：，其中 下面介绍一次同余方程 （*
8、）的解法.【解法1】因（a,m）=1，则存在二数s,t，使得as+mt=1，即，由此有为（*）的解.【解法2】先把（*）变形成仅只是形式上的记号），然后用与m互质的数陆续乘右端的分子分母，直至把分母绝对值变成1（通过分子分母各对模m取余数）而得到解.【解法3】得用欧拉定理.因从而有解 2一次同余方程组定义八：若数r同时满足n个同余方程：叫做这n个同余方程组成的同余方程组的解.定理十二：对同余方程组 记若d ，则此同余方程组无解；若，则此同余方程组有对模M的一类剩余解.模m的阶和中国剩余定理（1）模m的阶定义九：设m1是一个固定的整数，a是与m互素的整数，则存在整数k，1km，使得.我们将具有这
9、一性质的最小正整数（仍记为k）称为a模m的阶.a模m的阶具有如下性质：设的阶，是任意整数，则的充要条件是.特别地，的充分必要条件是k|u.【简证】充分性显然.必要性.设用带余除法，及k的定义知，必须r=0，所以设模m的阶为k，则数列模m是周期的，且最小正周期是k，而k个数模m互不同余.设模m的阶整除欧拉函数特别地，若m是素数p，则a模p的阶整除p1.（2）中国剩余定理（即孙子定理）设是两两互质的正整数，记M=则同余方程组 有且只有解 （）其中 （）【证明】由知，因此每一个同余方程（i=1，2，n）都有解，于是必存在所以对模故（）是（）的解.若是适合（）的任意两个解，则故因此，（）是（）的惟一解
10、.赛题精讲例1：数1978n与1978m的最末三位数相等，试求正整数m和n，使得n+m取最小值，这里 （第20届IMO试题）【解】由已知1000=8125，所以 因，且（1978m，125）=1，则由式知1978nm1（mod125）又直接验证知，1978的各次方幂的个位数字是以8、4、2、6循环出现的，所以只有nm为4的倍数时，式才能成立，因而可令nm=4k.由于. n+m=（ nm）+2m=4k+2m，因而只需确定出k和m的最小值.先确定k的最小值：因为19784=（7925+3）4341（mod5），19784341（mod25）.故可令19784=5t+1，而5 t，从而01978nm
11、1=19784k1=（5k+1）k1+，显然，使上式成立的k的最小值为25.再确定m的最小值：因19782（mod8），则由式知， 由于式显然对m=1，2不成立，从而m的最小值为3.故合于题设条件的n+m的最小值为106.【评述】比例中我们用了这样一个结论：1978的各次方幂的个位数字是以8，4，2，6循环出现，即，当r=1，2，3，4时，这种现象在数学上称为“模同期现象”.一般地，我们有如下定义：整数列各项除以m（m2，mN*）后的余数组成数列.若是一个周期数列，则称是关于模m的周期数列，简称模m周期数列.满足（或（modm）的最小正整数T称为它的周期.例如，（1）是模10周期数列，周期为4
12、；（2）自然数列n是一个模m（m2，mN*）周期数列，周期为m；（3）任何一个整数等差数列都是一个模m（m2，mN*）周期数列，周期为m.例2：设a是方程的最大正根，求证：17可以整除a1788与a1988.其中x表示不超过x的最大整数. （第29届IMO预选题）【证明】根据如下符号表可知，若设三根依次为，则x113f(x)符号+另一方面，由韦达定理知，为了估计、，先一般考察an，为此定义：直接计算可知：又因当时，由此知，命题变为证明：能被17整除.现考察在模17的意义下的情况：可见，在模17意义下，是16为周期的模周期数列，即由于1788故命题得证.例3：求八个整数满足：对每个整数k（1985k1985，而n=6时，H=10431985.故n1=1，n2=3，n8=37为所求.例4：设n为正整数，整数k与n互质，且0k1.证明：
