同余理论在数学竞赛中的运用

1、同余理论在数学竞赛中的运用卢军萍杭州师范大学 数学与应用数学043班摘要：这些年来，同余理论在数学竞赛中的应用越来越广泛。本文详细了同余理论的基础知识，并通过举例以便更好的理解。并重点对数学竞赛中有关同余理论的应用作了系统的划分。每一部分都有2-4个例题加以举例说明。关键词：同余；数学竞赛引言 数学竞赛已逐渐形成一门特殊的数学学科竞赛数学。像IMO竞赛等等受到越来越大的重视。而在数学竞赛中，初等数论的有关题目占得比例越来越大，尤其是同余理论在数学竞赛中有着举足轻重的地位。下面，本文重点论述一下同余理论在数学竞赛中的运用。首先，先介绍一下同余的一些基本知识。同余的性质及几个重要的定理.同余的定义

2、、性质定义 给定正整数m，如果整数a与b之差被m整除，则称a与b对于模m同余，或称a与b同余，模m，记为,此时也称b是a对模m的同余。如果整数a与b之差不能被m整除，则称a与b对于模m不同余。定理 下面的三个叙述是等价的：（） ；（）存在正整数q，使得,（）存在整数，使得,，.定理 同余具有下面的性质：（）（自反性）；（）（对称性）若，则；（）（传递性）若，则；（）假设a,b,x,y是整数，并且，则；（）设, ()以及x,y都是整数，并且，则；（）,;（）,;（）若，则;();().下面简单介绍一下，以上同余性质的一些应用。例 求被50除的余数。解： 有性质（）得， 即所求的余数是29。例 求

3、的个位数。解： 因为因此若则 （）现在所以由式（1）得到即n的个位数是3。例 证明：若n是正整数，则。11证明：因为再有性质（）得，得证。例 已知求和。解：因为99=911 所以 （） （）有（）式得： （）有（）式得： （）由于，所以由式（）与（）得出或6，或，可得四个方程组 ，解得。.剩余类、完全剩余系和简化剩余系定义给定正整数m，对于每个整数i，,称集合是模的一个剩余类。定义设m是正整数，从模m的每一个剩余类中任取一个整数，称集合是模的一个完全剩余系（或简称为完全系）。由于的选取是任意的，所以模m的完全剩余系有无穷多个，通常称：i.ii.定理整数集合A是模m的完全剩余系的充要条件是：i.

4、 A中含有m个整数；ii. A中任何两个整数对模m不同余。 定理设m剩余系，则也是模m的一个完全剩余系。定理设 分别是模和模的完全剩余系，则是模的一个完全剩余系。推论若，的完全剩余系数时，的完全剩余系数。定理设，则当的完全剩余系数时，的完全剩余系数。定义设是模m的一个剩余类，则称是模m的一个简化剩余类。例设，则在数列 （）中有且仅有一个数b，满足： ()若则。解：因为（a，p）=1, 所以由定理，式（）中的数构成模p的一个完全剩余类，因此，必有数b满足试（），设b=ka，那么i. ；ii. ，即p|(a+1)(a-1),因此p|a-1或p|a+1,这；iii. 显然 矛盾；iv. 矛盾； 若又

5、有，故所以是不可能的，这就证明了唯一性。例设m是给定的整数，求证存在整数a,b和k，其中a,b均不能被2整除，使得（1999年第四届冬令营试题）。分析：这道题说难不难，说易不易，关键在于是否将上试看成一个同余的形式，如果能找到a,b为奇数，满足上式，则原问题可以很快解决，像这样的限制条件实际上是障眼法。而上面所举的同余方程，要证他有解，则可利用剩余系的理论。证明：先证明如下的引理引理：当通过模的一个简化剩余系时，亦通过的一个简化剩余系。实事上，由于当故引理只需要证明当与对于模不同余，且与均为奇数时，与 对于模也不同余。由于而为19个奇数之和，仍为奇数，故下证原命题： 由于与互质，故由引理可知存

6、在不妨设，否则我们可以取充分大的，用代替上面的a，故可设,使由于，故故我们找到了这样的3个整数a，1，k,其中a,1均为奇数，使从而原命题得证。.Euler定理同余理论中有一个非常著名的定理,并且它在理论和应用两个方面都是很重要的，它就是Euler定理。定理（Euler定理 ） 设是正整数，=1，则 . 定理（Fermat定理） 设是素数，则对于任意的整数，有 . 定理（Wilson定理） 设为素数，则. 定理（孙子定理） 设，是两两互素的正整数，记，同余方程组，的一切解为，其中，. 下面列举一下这些定理的运用。例设是使成立的最小正整数，则（）（）对于任意的。解：（）由Euler定理，因此，由

7、带余数除法，有：因此，由上式及do的定义，利用定理，我们得到即整数r满足有do的定义可知必是r，即。（）假设存在不妨设这与do的定义矛盾，则假设不成立。得证。例设n是正整数，记解：容易验证，当时，是素数，所以由Fermat定理可知结论显然成立。当时，有记：其中和都是整数，上式即是证毕。例求整数，它被3，5，7除的余数分别是1，2，3。解：n是同余方程组的解，在孙子定理中，取 ，则；所以。因此，所求的整数n52+105t，。同余理论在数学竞赛中的运用.同余理论用于处理有关整数的进制问题例一个四位数，它的个位数字与百位数字相同，如果把这个四位数的数字顺序颠倒一下（即千位数字与个位数字互换，百位数字

8、与十位数字互换），所得的新数减去原数得7812，求原来得四位数。（1979年云南省竞赛题）解：设该数的千位，百位，十位数分别为x,y,z,则原数为 ， （）颠倒后的新数为， （）（）-（）得：7812=999（y-x）+90(z-y)即：868=111（y-x）+10(z-y)= 则原数千位数字x不能为0，则，又显见百位数字，所以y=9，则x=1，z=7，故所求四位数为1979。例N是整数，它的b进制表示是777。求最小的正整数b，使得N为十进制的四次方。（第9届加拿大竞赛题）证明：由题意是求最小的正整数b，使得方程（）对x有整数解。而又因为7是素数，所以，为此不妨设则（）式化为最小b的出现在

9、k最小的时候取k=1，此时有即解得正整数 ，即有2同余理论用于处理有关整除的问题整数与求余是密切相关的，若能把同余理论在整除问题中灵活运用，可方便快速的解决许多问题。例证明（）没有正整数能让被7整除 （）求出所有正数使能被7整除。（第六届IMO试题）解：（）依题意，即求得的所有正整数， 通过计算我们有 ， （）当不是3的倍数时，有两种情况：而 （）而 （）故只有当是3的倍数时，能被7整除.（） 由（）（）（）式有：， ， ，故没有正整数能让被7整除.例 证明：正整数A是完全平方数的充分必要条件是对于任意整数n，中至少有一项可以被n整除。（第51届捷克和斯洛伐克奥林匹克题）证明：充分性：若，则由

10、于是连续的个正整数，所以，一定有某个j使得可以被n整除。必要性：假设A不是完全平方数，则A中一定有一个素因子，其指数为奇数次幂，即存在k，使得，且不整除A取，对于，一定存在一项j，使得又因为不整除A，所以不整除但是由且可得由于是完全平方数，则一定有，矛盾所以假设不成立，A是完全平方数。证毕.同余理论应用于解决有关数列问题例数列定义如下：的最大质因子。问：11是否在此数列中出现。解：若存在，使，则由并且与2，3，7互质，于是，设 （14）对（14）两边模4，应有，故为奇数。对（14）两边模3，应有，故为奇数。对（14）两边模7，应有，故这与对任意，矛盾所以11不在中出现。例 设定义如下：， （）

11、，证明：除“1”外这两个数列没有其他相同的项.分析：这两个数的前项分别是： 欲证时，没有相同的项，直接论证有一定的困难，我们转而考察被某个正整数除后所得的余数，逐次用2，3，去除，前面各项，可以发现，。即数列是由3，5组成的周期为2的数列，数列是以1，7组成的周期为2的数列，以下用数学归纳发给以严格论证。初值已验证。假设则 ，。因此，时上述猜想是正确的，从而一切不小于3的自然数猜想正确，所以原命题成立。.同余理论用于求解不定方程例确定方程的全部非负整数解，不记排列的次序。（第八届IMO试题）解：当x为偶数时，显然当x为奇数时，显然这样，任意整数的四次方对于模16只有0，1两个可能值，从而对于模

12、16的所有可能值是0，1，2，14但，因此原方程无解注意：对于不定方程的问题，如果直接求解有困难，不妨从方面考虑一下，看能否证明其无解。此题注意到整数具有16k和16k+1的形式，从而考虑模16来证明方程无整数解。例 试证：（）如果正整数及方程有一组整数解，那么这个方程至少有三组整数解。（）当=2891时，上述方程无整数解。 （第二十三届IMO试题）证明：（）可证明若是原方程的一组整数解，则可找到另外两组不同的整数解：.（）用反证法，假设有整数解使得：， （）则，于是：（）若，则 ；（）若，则 ；（）若，则.对于第一种情况，代入（）得：，左边，右边，矛盾；对于第二种情况，上述另一组解将导致：，

13、这也就是第一种情况，已证；对于第三种情况：，代入（）得：，左边，右边，矛盾。 综上所述，方程无整数解。.同余理论应用于解决有关染色问题例设，求证：必定可以对中的数进行中颜色的染色，使得中任意个构成等差数列的数不同色。证明：由于，故可将的每一个数表示成进制中的位数(当位数不够在前面添)。记则，事实上，对，使得，将中的数对应染上第一，二，三，四种颜色，下证这种染色方法满足要求。只需证明无项构成等差数列。反证法，假设均在，若不整除，则的进制的末位数字通过了从而存在j使得的末位数字为。若，而则的进制的倒数第二位数字通过了，故也存在j使，又矛盾。若，而则的进制的倒数第三位数字类似地导出矛盾。若，矛盾。综

14、上，假设不成立，从而结论得证。例 给集合中每个数染色，若 对与同色， 存在，使对任意，与同色，求证只有一个色。分析：设，且，则是的完系。再令，其中。那么，且也是的一完系，由于，所以它是的最小非负完系的一个排列，但，从而是的一个排列。欲证同色，只需证同色，现用数学归纳法证明。证明：（）当时，由题设知，同色，命题为真.（）假设当时，同色，现欲证与也同色.若，由于，并注意到，所以是被除所得的余数，即，由题设条件可知，与同色，即与同色.若，由于，并注意到，所以是被除所得的余数，即与同色.又由题设条件，与同色，故与.若，则产生矛盾，事实上，这时有这说明，于是，但这与只有相矛盾.利用构造剩余系解同余问题通

15、过构造完全剩余系，简化剩余系可以巧妙地解决一些同余问题。例试确定具有下述性质的所有正整数n，集合可以分成两个不相交的非空子集，使得一个子集中所有元素的积，等于另一个子集的所有元素之积。解：在中加进数是模的一个完全剩余系。假定有满足题设条件的n存在，分两种情况讨论：（）不整除n，则有设两个子集的元素的积为m，则。因为是质数，故中必有一个这不成立。（）整除n，则令分成的两个子集的元素的乘积为m，便有：而无解，事实上：所以满足条件的m不存在综上所述，满足题设条件的n不存在。例 设，且m为奇数，。证明：和数是m的倍数。证明：因为，m是模m的完全剩余系，所以也是完全剩余系。则即故，得证。.同余理论用于证

16、明有关重要定理例用同余理论证明著名的Euler定理。 证明：设是模的一个简化剩余系，因为，所以 也是模的一个简化剩余系，对于同一个剩余类，上述两个剩余系各有一数是其中的元素，因此，这两个数应同余，不妨设与同余，其中是的一个排列，即有， 。累乘得，又 ，所以。因此，可约去 得 。证毕。例用同余理论证明Fermat定理。证明： 若，则由欧拉定理得到 .若，则，所以 .证毕.同余理论用于其他方面例欧拉的一个猜想在1960年被美国的数学家推翻，他们证实了存在正实数n，使得，求n的值。（第七届美国数学邀请赛）解：分三步来解这个问题先对n进行初步估值因为所以133 n 200。求出n的个位数由可知：个位数

17、为4。求n的十位数根据余数判别法可知：所以即：3n，n=144或174仍根据余数判别法可知：所以n=144。例数与的最后三位数相等，试求出正整数和，使得取最小值这里。分析：因为数与的最后三位数相等，所以，而 ，故 （） （）由于 （）又由于，显然时，（）式不成立，所以，再由（）式得， （）而1978的各次幂的个位树只能取8，4，2，6循环，所以只有当为4的倍数时，（）才能成立.不妨设， 注意到，。可令，则 。于是应含有作为因子，其最小为25.因此最小。 而，所以当和均最小时， 最小，此时， 其中。以上是同余理论在数学竞赛中的有关应用的分类与举例，而鉴于同余理论在数论中的特殊地位，若要灵活地掌握和应用它，还需加强对数论知识的系统、有效的学习。参考文献：1. 李长明，周焕山.初等数学研究M.北京：高等教育出版社，1995:66-952. 于秀源，瞿维建.初等数论M.济南：山东教育出版社，