同余理论及其应用

《同余理论及其应用》由会员分享，可在线阅读，更多相关《同余理论及其应用（8页珍藏版）》请在装配图网上搜索。

1、智浪教育普惠英才文库同余理论及其应用基础知识一. 定义定义1. 设m为正整数，整数a和b之差可被m整除时，称为a和b关于模m 同余，记作 定义2. 被正整数m除余数相等的所有整数的集合称为模m的剩余类。模m的剩余类共有m个。定义3. 在模m的m个剩余类中各取一个整数作为代表，这些代表的集合称为模m的完全剩余系。定义4. 绝对值不超过的模m的完全剩余系称为模m的绝对最小剩余系。定义5. 当模m的某一剩余类的所有整数均与m互素时，则称此剩余类是模m的简化类。模m的简化类共有个。定义6. 在模m的个简化类中各取一个整数作为代表，这些代表的集合称为模m的简化剩余系。定义7. 欧拉函数：设为正整数，从1

2、到的整数中与互素的整数的个数用表示，称为欧拉函数。当时，有二. 定理定理1. 的必要充分条件是a和b被m除的余数相等。定理2. I.II.若则III.若则定理3. 若，则I.；II.；III.定理4. 如果，则I.；II.推论. 如果n为任意正整数，则定理5. 如果则推论. 如果，则定理6. 如果则定理7. a和b属于模m的同一剩余类的充要条件是定理8. m个整数是模m的完全剩余系的充要条件是关于模m两两互不同余。定理9. 设f是正整数m的正因数。在模f的属于c的剩余类中取整数，则它们是模m的个剩余类。定理10. 与m互素的个整数是模m的简化剩余系的充要条件是这个整数关于模m两两互不同余。又设

3、是模m的简化剩余系，如果，则也是模m的简化剩余系。定理11. 欧拉定理：如果，则定理12. 费马小定理：如果，则，其中为素数。它也常写作：，这里不要求互素。定理13. 裴蜀定理：设是整数，则的充要条件是，存在整数使得推论1. 的充要条件是，存在整数使得推论2. 均为正整数，的充要条件是，存在正整数使得典型例题：一. 同余与完全平方数例1. 设素数p满足，证明p必不能表作三个平方数之和。分析 我们利用平方数模8的性质进行处理。 证明：设存在三个整数使其中或为偶数，或为奇数。因此下式必居其一。事实上，当a是奇数或时，有当a是偶数或时，有或同样b和c也必居下式之一：将所有可能满足的式子任意组合，只能

4、得到而得不到因此形如的素数不能表作三个平方数之和。评注 选择合适的模是处理平方数问题的技巧之一。例2. （2003年越南数学奥林匹克）求最大的正整数n，使得方程组有整数解分析 我们利用平方数的性质处理问题。解：当时，易知所给的方程组有整数解，当时，则奇偶交替出现，则且若为奇数，则 矛盾。同理：若为偶数，则为奇数。后面式子又矛盾，所以无解。显然无解。评注 选择适当的模，利用平方数性质是解决平方问题的技巧之一。二. 费马小定理与欧拉定理例3. 证明分析 由原式联想到费马小定理。 证明：，由费马小定理, ,而并且，由此可知：，所以原命题成立。评注 费马小定理是处理此类整除问题的重要工具。例4. （2

5、004年加拿大）为奇素数，证明： 解：由于为偶数，则，由二项式定理：右侧除最后两项外均被整除。因此由于由费马小定理 ， ，则 所以所以，原结论成立。评注 二项式定理也是处理数论问题的重要工具。 三. 同余与不定方程例5. （2004年韩国数学竞赛）证明：方程没有正整数解。分析 我们选择适当的模对进行分类处理问题。证明：（1）当时， 而方程左边能被3整除，此时无解。（2）当时，而，均为完全平方数。而 所以此时无解。（3）当时，令 则，令，则与（2）类似，均为完全平方数。设 则，即，所以 方程无整数解。综上所述，原方程无整数解。评注 方程右边可以进行因式分解，而左边系数为3，因而选择模3对进行分类

6、处理问题。例6. （2004年巴尔干数学奥林匹克）是质数，解：分析 我们要充分利用是质数的条件。 解：若,则无整数解；若，则 由于是质数，由费马小定理，即， ，再由费马小定理 即1. 若则 ；2. 由知：； 由知：即，又为质数。而为奇质数，为偶数， 与为质数矛盾。所以此时无解；3. 若，由知 ，无解；4. 若，则当时：易知：时，无解，当时，两边模4，知无解；时，左边小于0，无解；当时：两边模4， 时，左边小于0。当时：同理 无解；时，左边小于0。当时：无解；时，满足条件。为一组解。当时，无解；时，无整数解；当时， ，为一组解。综上，；为解。评注 在处理有关质数的幂的问题中，费马小定理常发挥重要

7、作用。四. 同余定理例7. 设p是奇素数，a是连续数列 中的任一数，则数列 中必有一个且只有一个数关于模p与1同余，设此数为ia，则i为中一数且与a相异。分析 利用为素数证明：因为中各数均小于p，p为素数，所以中每一个数均与p互素。由于a是中某数，故因此，由定理11，数列与数列代表同一类数，也就是说，数列表示模p的除p的倍数外，其余的一切类数。因此中必有一数，使 。这个i决不能等于a，事实上，如果，则有，从而就有。由于p是素数，且，故或，两者必居其一。但，即。所以不可能有及。故另外可以证明否则如果就有但，即，所以,因此不可能有所以再次可以证明否则就有，但这与矛盾。这样就证明了数列中必有一数ia

8、，有，而又，故i必为中一数且与a相异。此外，如果中有两数使，那么由于，故有，但，从而有，这与假设矛盾。评注 本题是最基本的结论之一。例8. 求证： 这里p为奇素数。分析 我们利用例1的结论。 证明：对任意，都存在唯一的使注意到时，否则若，即 矛盾。又注意到故可以把中和两两配对，每一对的乘积同余于1模p，由于有且仅有两解，所以除了1，和自己配对外，其余个数恰可配成对。 评注 本题即威尔逊定理。 五. 同余与其他例9. 已知证明：对一切正整数n, 分析 我们只要证明模某一常数不为0即可。 证明：若某一个，则对任意正整数m有，因此，我们只要找到一个m，对任何一个n 均有即可， 。设时，则时， ，因此

9、对一切n 均有，从而原命题成立。评注 同余是处理此类问题的有效方法之一。 例10. （1996年保加利亚）求所有的质数，使得整除解：如果，由费马小定理， ，所以，假设，则，。不失一般性，我们设，则，由裴蜀定理，存在正整数，使。由费马小定理，所以=，又，所以，矛盾。所以 之一为3 。若，则，所以。类似，因此，解。练习及参考答案练习1. 求证：存在无穷多个这样的正整数，它们不能表示成少于十个奇数的平方和。分析 对于否定性问题，我们常利用同余。解：设正整数n能够表示成 ，其中为奇数，若，则由及知，即若，则由及知，从而这说明若，则综上所述，被8除余2，被9除余3，即具有形式的正整数便不能表示成，故命题

10、得证。评注 对于某些问题，常常需要多次选择不同的模进行同余处理。练习2. 求出大于1的整数的个数，使得对任意的整数，都有分析 联想例4，猜想的最大值为2730。 解：设满足条件的正整数组成集合S，若，则，因此S 中全部数的最小公倍数也属于S ，即S中的最大数是其余每个数的倍数。，则的约数也整除，于是只需确定最大数，其一切大于1的约数组成集合S。，并且，由例4，由费马小定理，易证，所以，集合S共有31个元素。评注 利用特殊值法确定最大值，再进行证明是处理竞赛问题的典型技巧。练习3. 但为合数，则称341是伪质数，证明：伪质数有无穷多个。分析 我们想办法构造出具体的表达或递推关系。证明：已知341

11、为伪质数，假设m是伪质数，下面证明是伪质数，首先，设，其中为大于1的整数，则，含有因子，并且，所以为合数。其次，由于，设，其中s为大于1的正整数，而，可被整除，因而，所以是伪质数，并且。由此可知伪质数有无穷多个。评注 利用递推关系构造是解决无穷解问题的重要构造方法。练习4. （第43届IMO预选题）求最小的正整数n，使得：有整数解。分析 我们先估计出n的值，在构造出一组解。解： ， ，所以 又其中，于是，由于 ，则所以。评注 选择适当的模，利用同余进行估计是重要的方法之一。练习5. （2003年中国集训队测试）正整数n不能被2, 3整除，且不存在非负整数a, b，使得|2 a3 b| = n。

12、求n的最小值。分析 我们先通过具体赋值猜出 n 值，再进行证明。解：n = 1时，|2 13 1| = 1；n = 5时，|2 23 2| = 5；n = 7时，|2 13 2| = 7；n = 11时，|2 43 3| = 11；n = 13时，|2 43 1| = 13；n = 17时，|2 63 4| = 17；n = 19时，|2 33 3| = 19；n = 23时，|2 53 2| = 23；n = 25时，|2 13 3| = 25；n = 29时，|2 53 1| = 29；n = 31时，|2 53 0| = 31；下证n = 35满足要求，用反证法，若不然，存在非负整数a,

13、 b，使得 |2 a3 b| = 35。(1)若2 a3 b = 35，显然a 0, 1, 2，故a 3，模8，得3 b 3 (mod 8)，即3 b 5 (mod 8)，但3 b 1, 3 (mod 8)，不可能。(2)若3 b2 a = 35，易知b 0, 1，模9，得 2 a 1 (mod 9)， 2 k (mod 9)：2, 4, 8, 7, 5, 1, 2, 4, ， 2 6k 1, 2 6k + 1 2, 2 6k + 2 4, 2 6k + 3 8, 2 6k + 4 7, 2 6k + 5 5 (mod 9)，于是a = 6k，k为非负整数，所以 3 b8 2k = 35。再模

14、7，得 3 b 1 (mod 7)， 3 k (mod 7)：3, 2, 6, 4, 5, 1, 3, 2, ，故b = 6k/，k/为正整数， 3 6k 2 6k = 35，(3 3k 2 3k )(3 3k + 2 3k ) = 35， 或 于是，3 3k = 18或6，不可能。综上可知，nmin = 35。评注 对于不定方程无解的问题常用同余处理。练习6. （2004年亚太地区数学竞赛）证明：对于任意正整数，是偶数。分析 当 n 和 n+1 是合数时，容易处理，我们只要处理n 和 n+1 之一是素数的情况。证明：对于 n = 1, 2, 3, 4, 5 我们有=0，显然为偶数。我们考虑

15、n 6. 如果n 和 n+1 是合数，则它们 一定整除 (n-1)!，并且互素。所以它们的乘积整除 (n-1)!. 由于 n, n+1 中只有一个是偶数，对于 m 6, (m-2)! 所含的2的幂指数大于m所含的幂指数,所以是偶数. 我们最后考虑n+1 = p为一个素数,和 n = p为一个素数. 如果 n+1 = p, 则 p-1 是一个合数,所以 p-1 整除(p-2)!. 令 k = ，由威尔逊定理 (p-2)! = 1（mod p）, 所以 k(p-1) = 1（ mod p），因此 k = -1（mod p）.所以 是一个整数. 但 k 是偶数, 所以k+1 是奇数，因此是奇数. 又

16、，所以 是偶数.如果 n = p, 则 k =是偶数，所以 k+1 是奇数. 由威尔逊定理k(p+1) = -1（mod p）,所以 是一个奇数，所以=是偶数.综上，原命题成立评注 当n 和 n+1 之一是素数时，由我们联想到威尔逊定理。 练习7. 设定义如下：，证明：除“1”以外这两个数列没有其它相同的项。证明：，下面证明：；，其中n为正整数。初值易验证，假设，则，可知时结论成立。同理可证。因而原命题成立。练习8. 求所有的正整数对使得是整数。 证明：若a为任意正整数，则显然是原问题的解，下面我们证明原问题没有其他解。若，易知，不妨设为的最小素因子，则，又由费马小定理，而，由裴蜀定理存在正整数，使。则=，所以，与矛盾。所以没有其他的正整数解。8