同余理论及其应用
基础知识
一. 定义
定义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到的整数中与互素的整数的个数用表示，称为欧拉函数。当时，有
二. 定理
定理1. 的必要充分条件是a和b被m除的余数相等。
定理2. . .若则.若则
定理3. 若，，则.；.
；..
定理4. 如果，则.；.
推论. 如果n为任意正整数，则
定理5. 如果则
推论. 如果，则
定理6. 如果则
定理7. a和b属于模m的同一剩余类的充要条件是
定理8. m个整数是模m的完全剩余系的充要条件是关于模m两两互不同余。
定理9. 设f是正整数m的正因数。在模f的属于c的剩余类中取整数，则它们是模m的个剩余类。
定理10. 与m互素的个整数是模m的简化剩余系的充要条件是这个整数关于模m两两互不同余。又设是模m的简化剩余系，如果，则也是模m的简化剩余系。
定理11. 欧拉定理：如果，则
定理12. 费马小定理：如果，则，其中为素数。它也常写作：，这里不要求互素。
定理13. 裴蜀定理：设是整数，则的充要条件是，存在整数使得
推论1. 的充要条件是，存在整数使得
推论2. 均为正整数，的充要条件是，存在正整数使得
典型例题：
一. 同余与完全平方数
例1. 设素数p满足，证明p必不能表作三个平方数之和。
分析 我们利用平方数模8的性质进行处理。
证明：设存在三个整数使其中或为偶数，或为奇数。因此下式
必居其一。事实上，当a是奇数或时，有当a是偶数或时，有或同样b和c也必居下式之一：
将所有可能满足的式子任意组合，只能得到而得不到因此形如的素数不能表作三个平方数之和。
评注 选择合适的模是处理平方数问题的技巧之一。
例2. （2003年越南数学奥林匹克）求最大的正整数n，使得方程组
有整数解
分析 我们利用平方数的性质处理问题。
解：当时，易知所给的方程组有整数解，当时，
，则奇偶交替出现，则且
若为奇数，则 矛盾。同理：若为偶数，则为奇数。后面式子又矛盾，所以无解。显然无解。
评注 选择适当的模，利用平方数性质是解决平方问题的技巧之一。
二. 费马小定理与欧拉定理
例3. 证明
分析 由原式联想到费马小定理。
证明：，由费马小定理,, ,,
,,而
并且，由此可知：，所以原命题成立。
评注 费马小定理是处理此类整除问题的重要工具。
例4. （2004年加拿大）为奇素数，证明：
解：由于为偶数，则，由二项式定理：
右侧除最后两项外均被整除。因此
由于由费马小定理
， ，则
所以
所以，原结论成立。
评注 二项式定理也是处理数论问题的重要工具。
三. 同余与不定方程
例5. （2004年韩国数学竞赛）证明：方程没有正整数解。
分析 我们选择适当的模对进行分类处理问题。
证明：（1）当时， 而方程左边能被3整除，此时无解。（2）当时，，
，而，，，
均为完全平方数。而 所以此时无解。（3）当时，，令 则，令，则与（2）类似，均为完全平方数。设 则，即
，所以 方程无整数解。综上所述，原方程无整数解。
评注 方程右边可以进行因式分解，而左边系数为3，因而选择模3对进行分类处理问题。
例6. （2004年巴尔干数学奥林匹克）是质数，解：
分析 我们要充分利用是质数的条件。
解：若,则无整数解；若，则 由于是质数，由费马小定理，即， ，再由费马小定理 即1. 若则 ；2. 由知：； 由知：即，，又为质数。而为奇质数，为偶数， 与为质数矛盾。所以此时无解；3. 若，由知 ，无解；4. 若，则当时：易知：时，，无解，，当时，两边模4，知无解；时，左边小于0，无解；当时：两边模4， 时，左边小于0。当时：同理 无解；时，左边小于0。当时：无解；时，满足条件。为一组解。当时，无解；时，无整数解；当时， ，为一组解。综上，；为解。
评注 在处理有关质数的幂的问题中，费马小定理常发挥重要作用。
四. 同余定理
例7. 设p是奇素数，a是连续数列 中的任一数，则数列
中必有一个且只有一个数关于模p与1同余，设此数为ia，则i为中一数且与a相异。
分析 利用为素数
证明：因为中各数均小于p，p为素数，所以中每一个数均与p互素。由于a是中某数，故因此，由定理11，数列与数列代表同一类数，也就是说，数列表示模p的除p的倍数外，其余的一切类数。因此中必有一数，使 。这个i决不能等于a，事实上，如果，则有，从而就有
。由于p是素数，且，故或，两者必居其一。但，即。所以不可能有及。故另外可以证明否则如果就有
但，即，所以,因此不可能有所以再次可以证明否则就有，但这与矛盾。这样就证明了数列中必有一数ia，有，而又，故i必为中一数且与a相异。此外，如果中有两数使，那么由于，故有，但，从而有，这与假设矛盾。
评注 本题是最基本的结论之一。
例8. 求证： 这里p为奇素数。
分析 我们利用例1的结论。
证明：对任意，都存在唯一的使注意到时，否则若，即
矛盾。又注意到故可以把中和两两配对，每一对的乘积同余于1模p，由于有且仅有两解，所以除了1，和自己配对外，其余个数恰可配成对。
评注 本题即威尔逊定理。
五. 同余与其他
例9. 已知证明：对一切正整数n,
分析 我们只要证明模某一常数不为0即可。
证明：若某一个，则对任意正整数m有，因此，我们只要找到一个m，对任何一个n 均有即可， 。设时，，，，则时， ，，因此对一切n 均有，从而原命题成立。
评注 同余是处理此类问题的有效方法之一。
例10. （1996年保加利亚）求所有的质数，使得整除
解：如果，由费马小定理， ，所以，假设，则，。不失一般性，我们设，则，由裴蜀定理，存在正整数，使。由费马小定理，所以==，又，所以，矛盾。所以 之一为3 。若，则，所以。类似，因此，解。
👁️ 阅读量：0
© 版权声明：本文《高中数学竞赛专题讲座---同余理论及其应用(一)》内容均为本站精心整理或网友自愿分享，如需转载请注明原文出处：https://www.zastudy.cn/jiangzuo/1686217601a208601.html。