第二讲-同余(数论复赛辅导)

包头市数学联赛辅导 复赛数论初步选讲-北重三中 樊增平第二讲 同余一.基础知识1.定义1. 设是正整数，若用去除整数，所得的余数相同，则称与关于模同余，记作，否则称与关于模不同余，记作.例如：， 等等。当时，则称是对模的最小非负剩余。对于固定的模，通常有下面的性质：性质1. 的充要条件是也即。性质2.同余关系满足以下规律：（1）（反身性）；（2）（对称性）若，则；（3）（传递性）若，则；（4）（同余式相加）若，则；（5）（同余式相乘）若，则；注意： 反复利用（4）（5），可以对多于两个的（模相同的）同余式建立加、减和乘法的运算公式 ； 特别地，由（5）易推出：若，为整数且，则； 同余式的消去律一般并不成立，即从未必能推出，可是我们却有以下结果：若，则.由此可以推出：（6）若，则有，即在与互素时，可以在原同余式两边约去而不改变模.（7）若，则；（8）若，则；（9）若，则，特别地，若两两互素时，则有；性质3.若，则；性质4.设是系数全为整数的多项式，若，则。这一性质在计算时特别有用：在计算大数字的式子时，可以改变成与它同余的小数字，使计算大大地简化。整数集合可以按模来分类，确切地说，若和模同余，则和属同一类，否则不属于同一类，每一个这样的类称为模的一个同余类。由带余除法，任一整数必恰与0,1,，中的一个模同余，而0,1,，这个数彼此模不同余，因此模共有个不同的同余类， 例如，模2的同余类共有两个，即通常说的偶数类与奇数类，这两类中的数分别具有形式和（为任意整数）.2. 定义2 （剩余类）设是正整数，把全体整数按对模的余数分成类，相应的个集合记为：，其中每一个称为模的一个剩余类（也称同余类），.3. 定义3.（完全剩余系）设为模的全部剩余类，从每个中任取一个元素，得个数组成的数组，叫做模的一个完全剩余系.例如：关于模7，下面的每一组数都是一个完全剩余系：0，1，2，3，4，5，6；-7，8，16，3，-10，40，20；-3，-2，-1，0，1，2，3。最常用的完全剩余系是最小非负完全剩余系和绝对值最小完全剩余系.模的最小非负完全剩余系是：0，1，2，,;当为奇数时，绝对值最小的完全剩余系是：；当为偶数时，绝对值最小的完全剩余系有两个：；。4.定义4.（简化剩余系）在模的完全剩余系中，由所有与互素的数组成的数组叫做模的简化剩余系，也称既约剩余系.注意：简化剩余系不是完全剩余系，只是完全剩余系的一部分.例如：0、1、2、3、4、5、6、7、8、9是模10的一个完全剩余系，1、3、7、9是模10的一个简化剩余系，且满足.5. 欧拉(Euler)函数个整数0,1，中与互素的数的个数，称之为的欧拉函数，记为.定理1：若是素数，则.定理2：若，则.定理3：若的标准分解式是，则的计算公式是： .例如：； .6.几条常用的性质（1），其中；（2）每一个整数只包含于中的一个里；（3）对于任意，则的充要条件是.（4）个整数构成模的一个完全剩余系任意两数模不同余；（5）若是模的一个完全剩余系，且，则也是模的一个完全剩余系；（6）简化剩余系中数的个数为 ；（7）若是模的一个简化剩余系，且则也是模的一个简化剩余系（其中是欧拉函数）.【例题分析】1试求被50除所得的余数。解：由于是关于的整系数多项式，而，于是知 又注意到，故又 ，所以 注意到，因而29就是所求的余数.说明：在上述过程中，我们已经看到的作用。一般而言，知道一个整数的多少次幂关于模同余于是非常有用的。事实上，若，则对大的指数利用带余除法定理，可得，于是有，这里余数是一个比小得多的数，这样一来，计算的问题，就转化成了计算余数次幂的问题，从而使计算简单化。2设，若今天是星期一，计算第天后是星期几？解；星期几的问题是被7除求余数的问题.由于，于是，因而。为了把指数的指数写成的形式，还需取6为模来计算。为此我们有：，进而有：， ，依次类推有：，所以 .从而 ，所以星期一后的第天将是星期五.3数列满足：证明：（1）对任意为正整数； (2)对任意为完全平方数。证明：（1）由题设得且严格单调递增.将条件式变形得：两边平方整理得-得由式及可知，对任意为正整数.（2）将两边配方，得由式 0（mod 3）为正整数，式符合题意. 是完全平方数.4求所有的素数，使得与也是素数。分析：要使几个数同为质数，一般是利用某一质数的余数来确定，如均为质数，由于这是的一次式，故三个数就用模3的余数来确定，而二次式对三个数就模5，四个数一般就模7了。要使，与都是素数，须对除以素数的余数进行分类讨论，最后确定只能是这个素数.解：设，且若或4时，；若或3时，；即时，为5的倍数且比5大，不为质数。故，此时，；都是素数，即本题有唯一解。二、几个重要定理定理1：（欧拉（Euler）定理）若1，则.证明：取模的一个既约剩余系 由性质易知： 也是模的一个既约剩余系，于是中的任意一个数都能在中找到与它同余的数，反之也如此从而 ， ，故，证毕.分析： 这是数论证明题中常用的一种方法，使用一组剩余系，然后乘一个数组组成另外一组剩余系来解决问题。定理2：（费尔马（Fermat）小定理）对于质数及任意整数有.证明：设为质数，若是的倍数，则.若不是的倍数，则，由欧拉函数的计算公式及欧拉定理得，由此定理成立.推论：设为质数，是与互质的任一整数，则.同余组定义：设为整系数多项式（），我们把含有的一组同余式（）称为同余方程组。特别地，当均为的一次整系数多项式时，该同余方程组称为一次同余方程组.若整数同时满足：，则剩余类（其中）称为同余方程组的一个解，记作.定理3：（中国剩余定理，也称孙子定理）设是两两互素的正整数，那么对于任意整数，一次同余方程组，有唯一解：其中 ， 满足，.【例题分析】【欧拉定理及其应用举例】1.设，求证：。证明：因为，故由知，从而，但是，故由欧拉定理得：，从而；同理，。于是，即。2、设求证与的末三位数相同.证明:由条件只需证明 ，即: 也即证明 事实上，由 ，利用欧拉定理有 再由是奇数知: ,进而 由(3)、（4），并注意到可得（2），于是（1）成立.【Fetmat小定理及其应用举例】3求证：对于任意整数，求证 是整数.证明：令，则只需证是15的倍数即可。由3，5是素数及Fetmat小定理得，则，于是有 ；同理 而（3，5）=1，故，即是15的倍数，所以是整数.4求证：（为任意整数）。证明：令，则；所以含有因式由Fetmat小定理，知13|7|又13，7，5，3，2两两互素，所以2730=能整除。5设是直角三角形的三边长，且都是整数，求证：可以被30整除。证明：不妨设是直角三角形的斜边长，则。若2 ，2 ，2 c，则，这与 矛盾！所以2|.若3 ，3 ，3 c，因为，则，这与矛盾！从而3|.若 5 ，5 ，5 c，因为，所以或0(mod5)，这与矛盾！从而5|.又(2,3,5)=1，所以30|.【中国剩余定理应用举例】6证明：对于任意给定的正整数，均有连续个正整数，其中每一个都有大于1的平方因子。证明：由于素数有无穷多个，故我们可以取个互不相同的素数，而考虑同余组 因为显然是两两互素的，故由中国剩余定理知，上述同余组有正整数解。于是，连续个数分别被平方数整除。注：本题的解法体现了中国剩余定理的一个基本功效，它常常能将“找连续个正整数具有某种性质”的问题转化为“找个两两互素的数具有某种性质”，而后者往往是比较容易解决的。7证明：对于任意给定的正整数，均有连续个正整数，其中每一个都不是幂数。分析：我们来证明，存在连续个正整数，其中每一个数都至少有一个素因子，在这个数的标准分解中仅出现一次，从而这个数不是幂数。证明：取个互不相同的素数，考虑同余组.因为，显然是两两互素的，故由中国剩余定理知，上述同余组有正整数解，.同理知，同余组有整数解，即，故 ，即在的标准分解中恰好出现一次，所以 都不是幂数.8 设是给定的偶数，证明：存在整数使得:，且.证明：（1）当为素数幂时，能够证明，存在使 且.实际上，若，则，此时可取.显然 ，且.若，则与中有一对满足要求.(2) 一般情形下，设是的一个标准分解.上面已经证明，对每个存在整数使得 且.由中国剩余定理知，同余式 有解，同余式 有解.现不难验证解符合问题中的要求：因 ，故 ，于是.又由知，故.矮化砧嫁接的苹果树树冠体积小于乔化砧嫁接的苹果树树冠体积，矮化砧苹果树单株产量低于乔化砧苹果树，所以，栽植矮化苹果树必须根据不同的矮化砧木和不同类型的短枝型品种适当加大栽培密度7