同余理论及其应用
东北育才学校 费振鹏
基础知识
一、定义
定义1：整数集Z根据模正整数m?m?1?来分类：若a、b被m除的余数相同，则a与b属于同一类，否则不属于同一类．这样得到m个类，即Mi??i?km|k?Z,i?0,1,2,?m?1?．称之为模m的剩余类（同余类）．
定义2：若整数a、b之差被正整数m整除，称a、b关于模m同余，记作a?b?modm?．即
a?b?modm??m?a?b?．从字面上理解，所属模m的同一个剩余类的两个整数模m同余．
定义3：在模m的m个剩余类中各取一个整数作为代表，这些代表的集合称为模m的完全剩余系．简称完系．
定义4：绝对值不超过?m?的模m的完系称为模m的绝对最小完系．将0,1,2,?,m?1称为模m??2??的最小非负完系．
定义5：当模m的某一剩余类Mi中某一整数与m互质，由欧氏除法（辗转相除法）知Mi中每个数与m均互质，则称此剩余类是模m的缩剩余类（亦称简化剩余类）．
定义6：设m为正整数，从1到m的整数中与m互质的整数的个数用??m?表示，称??m?为欧拉函数．模m的缩剩余类（简化剩余类）也是??m?个．
定义7：在模m的??m?个缩剩余类（简化剩余类）中各取一个整数作为代表，这些代表的集合称为模m的缩剩余系（简化剩余系），简称缩系（简系）．
定义8：满足ak?1?modm?的最小正整数k称为整数a模m的指数（阶）． 二、定理
定理1：同余的基本性质： ⑴a?a?modm?；
⑵若a?b?modm?，则b?a?modm?；
⑶若a?b?modm?，b?c?modm?，则a?c?modm?；
1
⑷若a?b?modm?，m?qn，n?N，则a?b?modn?． 定理2：若a1?b1?modm?，a2?b2?modm?，则
⑴a1?a2?b1?b2?modm?；⑵a1?a2?b1?b2?modm?；⑶a1a2?b1b2?modm?． 推论：⑴若ai?bi?modm??i?1,2,?,n?，则?ai?i?1n?b?modm?；?aii?1i?1nnin??b?modm?．
ii?1⑵若a?b?modm?，n为任意正整数，则na?nb?modm?；an?bn?modm?． 定理3：若ac?bc?modm?，则a?b?mod??m??． c,m???推论：若?c,m??1，ac?bc?modm?，则a?b?modm?． 定理4：若a?b?modm?，则?a,m???b,m?．
定理5：若a?b?modmi?，i?1,2,?,k，则a?b?mod?m1,m2,?,mk??．
?m定理6：设f是m??N??的正约数，在模f的属于c的剩余类中取整数c,c?f,?,c???f?1?f，
??则它们是模m的
mf个剩余类．
定理7：m个整数a1,a2,?,am是模m的完系的充要条件是a1,a2,?,am关于模m两两不同余． 定理8：若?k,m??1，其中k?Z*（Z*表示非零整数集），b?Z，m?N+，m?1且x1,x2,?,xm是模m的完系，则kx1?b,kx2?b,?,kxm?b也是模m的完系．
定理9：（裴蜀定理）设a，b，d是整数，则?a,b??d的充要条件是da，db，且存在整数
u，v使得ua?vb?d．
推论：⑴?a,b??1的充要条件是存在整数u，v使得ua?vb?1．
⑵a，b均为正整数，?a,b??1的充要条件是存在正整数u，v使得ua?vb?1． 定理10：（费马小定理）若a是整数，p是质数且?a,p??1，则ap?1?1?modp?． 推论：若p是质数，则ap?a?modp?．这里不要求a、p互质．
定理11：??m?个整数是模m的简系的充要条件是它们均与m互质且模m两两互不同余． 定理12：设a1,a2,?,a??m?是模m的简系，且?c,m??1，则ca1,ca2,?,ca??m?也是模m的简系．
2
定理13：（欧拉定理）若a是整数，正整数m?1且?a,m??1，则a??m??1?modm?． 定理14：欧拉函数的性质： ⑴若整数m?2，则??m?是偶数．
??⑵设m??pi是m的标准分解式，则??m??m???1?1?．
p?ii?1i?1kk?i?⑶若正整数m、n满足?m,n??1，则??mn????m???n?． ⑷???d??m，其中?表示d遍历m的所有正约数．
dmdm定理15：（威尔逊定理）若p是质数，则?p?1?!??1?modp?．
典型例题
一、选取适当的模
例1.求最大的正整数n，使得方程组
?x?1?2?y1??x?2??y2????x?k??yk????x?n??yn2222222
有整数解?x,y1,y2,?,yn?． （2003年越南数学奥林匹克）
分析：我们利用平方数的性质处理问题． 解：所求最大正整数n?3．
当n?3时，?x?1??y??x?2??y??x?3?212222222??y1?y2?2x?3,?y．进而得? 22??y2?y3?2x?5.23易得所给方程组有整数解?x,y1,y2,y3????2,0,1,0?．
2?y12?y2?2x?3,?2当n?4时，?y2?y32?2x?5,则y1，y2，y3，y4奇偶交替出现．
?22y?y?2x?7.34?从而2y22??y12?y32??2?*?且2y32??y22?y42??2?**?．
若y1，y3为奇数，则由y2是偶数得2y22?0?mod8?，而由2y22?2?y12?y32?4?mod8?． 即得出式?*?矛盾．
若y1，y3为偶数，则y2，y4为奇数．同理可得出式?**?矛盾．所以n?4无解．
3
而当n?4时显然无解． 综上可得所求最大正整数n?3． 例2.已知a1?1，a2?2，an?2??5an?1?3an,若an?an?1为偶数,
an?1?an,若a?a为奇数.nn?1证明：对一切正整数n，an?0． （1988年全国高中数学联赛二试）
分析：我们只要证明an模某一常数不为0即可．
证明：若某一个ak?0，则对任意正整数m有ak?0?modm?，因此，我们只要找到一个m，对任何一个n均有ak??0?modm?即可．
先通过计算前几项：a1?1，a2?2，a3?7，a4?29，a5?22，a6?23，…
模3的余数分别为1，2，1，2，1，2，…于是猜想奇数项模3余1，偶数项模3余2． 即a2n?1?1?mod3?，a2n?2?mod3?，其中n??*．下面用数学归纳法证明这一猜想： 当n?1时，a1?1?1?mod3?，a2?2?2?mod3?，结论成立； 假设当n?k时，结论成立，即a2k?1?1?mod3?，a2k?2?mod3?．
则不管a2k?1?5a2k?3a2k?1?2a2k?4?1?mod3?，还是a2k?1?a2k?a2k?1?2?1?1?mod3?，均有
a2k?1?1?mod3?．
进而不管a2k?2?5a2k?1?3a2k?2a2k?1?2?mod3?，还是a2k?2?a2k?1?a2k?1?2?2?mod3?，均有a2k?2?2?mod3?． 综上所述，猜想结论成立． 因此，原命题结论成立． 注：本题有如下加强命题：
⑴此数列所有项都不是3的倍数；（根据上面的证明，容易得出这个结论） ⑵此数列所有项都不是4的倍数；
⑶此数列为模3的模周期数列；（根据上面的证明，容易得出这个结论）
⑷此数列为模4的模周期数列（模4的结果为1，2，3，…，据此也可证明加强命题⑵）．
a1?1?mod4?，a2?2?mod4?，a3?3?mod4?．
4
设n?k时，a3k?2?1?mod4?，a3k?1?2?mod4?，a3k?3?mod4?．则n?k?1时，
a3k?1?5a3k?3a3k?1?1?mod4?，a3k?2?a3k?1?a3k?2?mod4?，a3k?3?5a3k?2?3a3k?1?3?mod4?．因此对一切n均有ak??0?mod4?，从而原命题成立．
评注：选择适当的模结合相关知识，如平方数性质、模周斯数列是解决同余问题的技巧之一． 二、不定方程
例3.证明：方程3y2?x4?x没有正整数解． （2004年韩国数学奥林匹克）
分析：我们选择适当的模对x进行分类处理问题． 证明：⑴当x?1?mod3?时，
设x?3a?1?a?N?，x4?x?2?mod3?． 而方程左边3y2?0?mod3?，矛盾． 所以此时无解． ⑵当x?0?mod3?时，
设x?3a?a?N*?，x4?x?x?x?1??x2?x?1??3a?3a?1??9a2?3a?1??3y2． ∴a?3a?1??9a2?3a?1??y2．
而?a,3a?1??1，?a,9a2?3a?1??1，?3a?1,9a2?3a?1???3a?1,3??1， ∴a，3a?1，9a2?3a?1均为完全平方数．
但由?3a?1??9a2?3a?1??3a?知9a2?3a?1不可能是完全平方数． 所以此时无解． ⑶当x??1?mod3?时，
设x?3a?1?a?N*?时，x4?x?x?x?1??x2?x?1??9a?3a?1??3a2?3a?1??3y2． ∴3|y2?3|y．令y?3c?c?N*?，则a?3a?1??3a2?3a?1??3c2． ∴3|a．令a?3b?b?N*?，则b?9b?1??27b2?9b?1??c2． 与⑵类似，b，9b?1，27b2?9b?1均为完全平方数．
其中9b?1?2?mod3?不可能是完全平方数，矛盾．所以此时无解．
5
22