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

摘要：利用同余理论中同余的定义、性质和重要定理可以解决数学竞赛中有关余数、整除、数列和不定方程等问题。

关键词：同余；模；整除；剩余类

中图分类号：G633.6 文献标识码：A 文章编号：1992-7711（2013）13-0118

同余理论是初等数论的重要组成部分，也是研究初等数学的有效工具之一。近几年来，在初、高中数学竞赛中，与同余有关的试题越来越多。这就要求我们不但要掌握同余理论，而且要深入探讨同余理论在数学竞赛中的应用，为解决相关问题提供思路和方法。下面结合数学竞赛试题讨论同余理论及其应用。

一、同余的基本理论

1. 同余的相关定义

定义1 给定一个正整数m，把它叫做模m.如果用m去除任意两个整数a与b所得的余数相同，则称a，b对模m同余，记作a≡ b（mod m）。

定义2 全体整数可按对模m是否同余分为若干个两两不相交的集合，使得在同一集合中的任意两个数对模m一定同余，而属于不同集合的两个数对模一定不同余。每一个这样的集合称为是模m的一个剩余类。

2. 同余的基本性质

性质1 a≡ b（mod m） m a- b.特别地，a≡0（mod m） m a.

性质2 若a1≡ b1（mod m），a2≡ b2（mod m），则a1±a2≡b1±b2（mod m）.

性质3 若a+ b≡c（mod m），则a≡ c-b（mod m）.

性质4 若ai≡ bi（mod m），i=1，2，……n，则ai≡bi（mod m），特别地，an≡ bn（mod m）

性质5 da≡db（mod m） a≡ b（mod m/（d，m））特别地，当（d，m）=1时dai≡db（mod m） a≡ b（mod m）.

性质6 对任意的整数a，b和k（k>0），若ak≡bk（mod mk），则a≡ b（mod m）.

性质7 若a≡ b（mod m1），i=1，2，……，n，则a≡ b（mod[m1，m2，……，mn]）.特别地，当i≠j时，若有（mi，mj）=1，则a≡ b（mod m1m2Lmn）.

性质8 若a≡ b（mod m），d m，d>0，则a≡ b（mod d）.

3. 几个重要的定理

定理1 （Euler定理）设m是大于1的整数，（a，m）=1，则

aφ（m）≡1（mod m）

其中φ（m）是整数的m欧拉函数.

定理2 （Fermat小定理）设P是素数，则aP-1≡1（mod p）.

定理3 一个整数N=能被某个自然数b整除的特征是：这个整数的各数位上的数ai（i=0，1，……，n）与对应的10的i次幂除以这个自然数所得到的余数ri（i=0，1，……，n）的乘积能被这个自然数整除。即10i=qib+ri（0≤ri

证明 10i=qib+r

10i≡ri（mod b）

ai10i≡airi（mod b）

ai10i≡airi（mod b）

N≡0（mod b） airi≡0（mod b）

即b N b airi

通过对各类数学竞赛试题的研究，我们发现同余理论主要用于解决以下四个方面的问题。

二、同余理论的应用

1. 余数方面

由同余的定义可以看出，同余是以带余除法为基础的，其中的“余数相同”是指带余除法中的余数相同。因此一些较为复杂的余数问题借助同余理论来解决会更为简洁灵活。在数学竞赛中，余数问题主要是以以下两种形式出现：

（1）直接求余数

例1. 求61783 被7除的余数.

分析：利用同余理论求余数的基本思路是设法将被除数化为与其同余的最小的数，主要手段是利用同余的定义和带余除法。对于形如ab的被除数，可利用同余的定义，“减小”底数a，利用Euler定理或Fermat小定理，“降低”的a指数b。

解：6178≡4（mod 7）

61783 ≡43 （mod 7）

310=95≡35≡3（mod 7）

310=6t+3，t=0，±1，±2，……

61783 ≡43 =46t+3=（46）t×43（mod 6）

由于7是素数，（4，7）=1，所以由Fermat小定理知

46≡1（mod 7）

故61783 ≡1t·43=64≡1（mod 7），即所求余数为1.

（2）求某数后几位数的问题

例2. 求N=1×3×5×……×1997×1999的末三位数。

分析：因为一个正整数N=可变为N=10m·+，所以N的末m位数就是N除10m以后的余数，则此问题转化为找一个三位数N与关于模1000同余。

解 设N的末三位数为M，则N≡M（mod 1000）.而1000=125×8，且（125，8）=1.由于N中含有5和25这两个因子，所以有

125 N 125 M

令M=125q

M是三位数

1≤q<8

因为N=（1×3×5×7）×（9×11×13×15）×……×（1993×1995×1997×1999）

所以上式中每一个小括号内的数都是形如

（8k+1）（8k+3）（8k+5）（8k+7） （k为非负整数）

8k+1≡1（mod 8） 8k+3≡3（mod 8）

8k+5≡5（mod 8） 8k+7≡7（mod 8）

由性质4，得

（8k+1）（8k+3）（8k+5）（8k+7）≡1×3×5×7≡1（mod 8）

N≡1（mod 8） M≡1（mod 8）

将q=1，2，……，7带入上式，只有当q=5时才满足.

故M=125×5=625，即N的末三位数为625.

（3）整除方面

由性质1可以看出，同余可以看作是对整除问题的进一步探讨，整除可以看作是同余的一种特例，因而同余与整除有着密切的联系.

2. 证明整除问题

例3. 证明1897 2903n-803n-464n+261n （n为自然数）.

分析由a≡0（mod m） m a知，该问题可以转化为证明

2903n-803n-464n+261n≡0（mod 1 897）成立.因1897=7×271，且（7，271）=1，所以问题又转化为证明式子

2903n-803n-464n+261n≡0（mod 7）

2903n-803n-464n+261n≡0（mod 271）

同时成立.

解：由同余关系2903≡803（mod 7），464≡261（mod 7）和性质4，得

2903n≡464n（mod 7）

803n≡261n（mod 7）

由性质2和性质3，得

2903n-803n-464n+261n≡0（mod 7）

2903≡464（mod 271）

803≡261（mod 271）

由性质4，得

2903n≡464n（mod 271）

803n≡261n（mod 271）

由性质2和性质3，得

2903n-803n-464n+261n≡0（mod 271）

由于1897=7×271，且（7，271=1），所以由性质7，得

2903n-803n-464n+261n≡0（mod 1 897）

3. 寻求能被某整数整除的数的特征

例4. 求证：能被11整除的数的特征是：这个数的偶数位上的数字之和与奇数位上的数字之和的差能被11整除。

分析：由定理3知，解决问题的关键在于求出10i=qib+ri中的ri.

证明 由10≡-1（mod 11），得

102i≡1（mod 11） （i=0，1，2，……）

102i+1≡1（mod 11） （i=0，1，2，……）

N=ai10i

=a2i102i+a2i+1102i+1

=a2i+a2i+1（mod 11）

N≡0（mod 11） =a2i+a2i+1（mod 11）≡（mod 11）

4. 数列方面

数学竞赛中的一些数列问题利用同余和剩余类的相关知识求解，不但快速简明，而且可以培养反证法和分类讨论的数学思想.

（1）分组问题

例5. 能否把1，2，3，……，1979，1980这个数1980分成四组，令每组数之和为S1，S2，S3，S4，且满足S2-S1=10，S3-S2=10，S4-S3=10？

分析 由于S1，S2，S3，S4要满足S2-S1=10，S3-S2=10，S4-S3=10，所以不难发现如果1980这个数能分成四组，则它们的和一定能整除4，即T=1+2+3+……+1980与0对模4同余。

解：假设能把1980这个数分成四组，由题意得

T=S1+S2+S3+S4=S1+S1+10+S1+20+S1+30

=4S1+60

≡0（mod 4）

但T=1+2+3+……+1980==990×1981≡2（mod 4），产生矛盾，所以假设不成立.即1980这个数不能按要求分为四组.

（2）等差数列个数问题

例6. 从集合{1，2，3，……，n} （n≥3）中任取m（3≤m≤n）个不同的数，使m这个数成等差数列，这样的数列有多少个？

分析：设a1，a2，a3，……，am是公差为d的各项为整数的等差数列，am=a1+（m-1）d，=d，则首末两项的差能m-1被整除，即am≡a1（mod m-1），随着首末两项的确定，等差数列的各项也随之确定.为此只需要考虑等差数列的首末两项的选取有多少种方法.

解：以m-1为模，将{1，2，3，L，n}集合分成m-1个剩余类，其中Kr={k k=q（m-1）+r，1≤k≤n，q∈z}，0≤r≤m-2

当m≤n≤2（m-1）时，若n=m-1+r，则K1，K2，……，Kr中都含有两个元素，而K0和Kr+1，Kr+2，……，Km-1中都只有一个元素，所以等差数列的个数为rP2.

当n≥2（m-1）时，K0，K1，K2，……，Km-1都至少含有两个元素，若n=q（m-1）+r，0≤r≤m-2，q≥2，则K1，K2，L，Kr都含有q+1个元素，而K0和Kr+1，Kr+2，……，Km-1都含有q个元素，所以等差数列的个数为rPq+1+（m-1-r）Pq.

（3）不定方程方面

直接证明某不定方程有无整数解往往比较困难，根据方程的特征将其转化为同余理论的相关问题，会使证明过程既直观又易于实现。

5. 不定方程解的存在性问题

例7. 证明方程2x2-5y=7无整数解.

分析：若一个不定方程有解，则方程的两端对同一个模m（常数）同余。反之，若方程的两端对某个模m不同余，则这个方程无整数解。由此可知，该问题转化为寻找一个整数m，使得方程的两端对模m不同余。

证明：由等式2x2=5y+7，可以知道y必为奇数.

（1）若x为偶数，则

2x2≡0（mod 8）

y2=（2n+1）2=4n（n+1）+1

y2≡1（mod 8）

5y2+7≡4（mod 8）

因方程的两边对同一整数8的余数不等，故x不能为偶数。

（2）若x为奇数，则

（上接第119页）

2x2=2（2n+1）2=8n2+8n+2≡2（mod 4）

5y2+7≡0（mod 4）

因方程的两边也对同一整数4的余数不等，故x不能为奇数。

综合（1）（2），可证得原方程无整数解.

从以上的例题可以看出，解决与同余理论有关的数学竞赛试题，首先要仔细观察，善于发现试题的特征，进而将问题巧妙地转化为同余理论的相关问题，最后利用同余的定义、基本性质以及重要定理对问题进行分析解答，这样不但可以减少大量的计算，而且使得解题思路简洁明了。

参考文献：

[1] 闵嗣鹤，严士健.初等数论[M].北京：高等教育出版社，2003.

[2] 潘承洞，潘承彪.初等数论[M].北京：北京大学出版社，1999.

[3] 罗增儒.初中数学奥林匹克·二年级[M].西安：陕西师范大学出版社，2001.

[4] 陈晓辉.关于同余理论在中学奥赛中的应用[J].数学通讯，2001（5）.

[5] 林晓燕.谈同余理论在初等数学中的几点应用[J].怀化学院学报， 1995（5）.

[6] 刘合义.谈数论中的同余及其应用[J]. 衡水师专学报，2002（1）.

（作者单位：陕西省安康市石泉县石泉中学 725200）

推荐访问:数学竞赛 理论