高中数学竞赛专题讲座---同余理论及其应用(一)

《高中数学竞赛专题讲座---同余理论及其应用(一)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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两两互不同余。又设是模m的简化剩余系，如果，则也是模m的简化剩余系。定理11.欧

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

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

5、。因此由于由费马小定理，，则所以所以，原结论成立。评注二项式定理也是处理数论问题的重要工具。三.同余与不定方程例5.（2004年韩国数学竞赛）证明：方程没有正整数解。分析我们选择适当的模对进行分类处理问题。证明：（1）当时，而方程左边能被3整除，此时无解。（2）当时，，，而，，，均为完全平方数。而所以此时无解。（3）当时，，令则，令，则与（2）类似，均为完全平方数。设则，即，所以方程无整数解。综上所述，原方程无整数解。评注方程右边可以进行因式分解，而左边系数为3，因而选择模3对进行分类处理问题。例6.（2004年巴尔干数学奥林匹克）是质数，解：分析我们要充分利用是质数的条件。解：若,则无整数解

6、；若，则由于是质数，由费马小定理，即，①，再由费马小定理即1.若则8②；2.由①知：；由②知：即，，又为质数。而为奇质数，为偶数，与为质数矛盾。所以此时无解；3.若，由知，无解；4.若，则当时：易知：时，，无解，，当时，两边模4，知无解；时，左边小于0，无解；当时：两边模4，时，左边小于0。当时：同理无解；时，左边小于0。当时：无解；时，满足条件。为一组解。当时，无解；时，无整数解；当时，，为一组解。综上，；为解。评注在处理有关质数的幂的问题中，费马小定理常发挥重要作用。四.同余定理例7.设p是奇素数，a是连续数列①中的任一数，则数列②中必有一个且只有一个数关于模p与1同余，设此数为ia，则i

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