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

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

数学与统计学院、数学与应用数学、0701班，湖北，黄石，435002

1.引言

近几年来，国际中学生奥林匹克数学竞赛的试题中，与数论有关的题目呈递增的趋势，而用初等数论的知识去解题也更加方便、简洁,这引起了国际数学界对中学数学教学中初等数论内容的相当重视。由此可见，初等数论在数学竞赛中的地位和作用越来越重要了。

同余理论是初等数论的重要内容之一，它不仅是研究数论问题的重要工具，而且还可用来解决许多初等数学问题。本文将在介绍同余理论系统知识的基础上，详细介绍同余性质和定理在中学数学中的应用，并举出相应的竞赛实例，进一步加深大家对同余理论对中学数学竞赛的重要性及广泛应用性的认识。

2.同余的相关概念、性质和几个重要定理 2.1同余的定义、性质

定义1 给定一个正整数m,把它叫做模。如果用m去除任意两个整数a与b所得的余数相同，我们就说a,b对模m同余，记作

abmodm.

1

湖北师范学院2011届数学与统计学院学士学位论文

命题 整数a,b对模m同余的充分必要条件是m|ab.

该命题说明同余这一概念又可以定义如下：

abmodm定义1 若m|ab,则a与b对模m同余即.

同余式的写法，使我们联想起等式。其实同余式和代数等式有一些相同的性质，最简单的就是

13下面的性质：

性质（1）：（自反性）

aamodm.

bamodm性质（2）：（对称性） 若

abmodm, 则.

acmodm性质（3）：（传递性） 若abmodm,bcmodm，则

.

在代数中，等式可以相加、相减和相乘，同样的规则对同余式也成立。 性质（4）：若abmodm,cdmodm，则

acbdmodmacbdmodm ，.

由此我们还可以得到：若

abmodm，k是整数，n是自然数，则

2

湖北师范学院2011届数学与统计学院学士学位论文

akbkmodm，

akbkmodm，

anbnmodm.

从而有:

xymodm性质（5）：若aibimodm(i0,1,2,,n)，，则

axbymodmiiiii0i0nn.

对于同余式

abmodmacbcmodm，是否能直接约去公约数c，得到一个正确 的同余式

？

255mod1051mod10在这个问题上，同余式与等式是不同的。例如：，约去5，得.

这显然是不正确的。但下面这种情形，相约是可以的： 性质（6）：若acbcmodm,c,m1，则

3

湖北师范学院2011届数学与统计学院学士学位论文

abmodm.

同余还有下面三个性质：

abmodmabmodd性质（7）：若，d|m,d0，则.

性质（8）：若

abmodm，k0,kN，则

akbkmodmk.

abm1,m2,,mk性质（9）：若abmodmi,i1,2,,k，则.

2.2剩余类和完全剩余系

abmodm全体整数集合可按模m来划分：当且仅当时，a和b属于同一类。于是全体整数按

模m被分为m类，每一个这样的类被称为模的剩余类。在m个剩余类中各取一个数作为代表，这样的m个数被称为模m的完全剩余系，例如0,1,2,,m1是模m的一个完全剩余系，称为最小非负完全剩余系。

完全剩余系有下列性质：

①如果c1,c2,,cm是模m的一个完全剩余系，b是整数，那么c1b,c2b,,cmb也是模m的完全剩余系。

4

湖北师范学院2011届数学与统计学院学士学位论文

a,m1②如果c1,c2,,cm是模m的一个完全剩余系，a是整数，且，则ac1,ac2,,acm也是模m的

完全剩余系。

2.3两个重要定理

同余理论中有两个定理，在理论和应用方面都是很重要的，它们就是欧拉定理和费马小定理。

a,m1a定理1 （欧拉定理）设m是正整数，，则

(m)1modm.

说明：(m)表示m的欧拉函数，其计算方法为：

11)(1)p1p21),p1,p2,pk(m)m(1(1,pk是m的全部不同的素因数。

定理2 （费马小定理）设p是素数，则对于任意的整数a，有

apamodp.

由此易知：当a与模m互素时，m|a了一个有力的工具。

(m)1；当p是素数时，p|apa.这就为整除性的讨论提供

注：以上性质与定理的证明见参考文献[1].

5

湖北师范学院2011届数学与统计学院学士学位论文

3.同余理论在中学数学竞赛中几个重要的应用

3.1 同余理论在处理整除问题上的应用

3.1.1 求余数或证明整除性问题，常以除数为模

a?modm若要求m除a的余数，只需求即可；

若要证明m整除a，只需证

a0modm即可。

例1[4]、 求32008除以13的余数.

解： ∵

331mod13

669 ∴

32008336691333166933mod13

故32008除以13的余数是3.

注:求余数是同余的基本问题，在这种问题中，先求出与1同余的数是一种基本技巧。下面例2也用到了此技巧。

2n例2、求证:（1) 8｜(551999＋17)；（2) 8|(3＋7)；

26

湖北师范学院2011届数学与统计学院学士学位论文

（3）17｜(19551mod81000-1)．

证明:(1)∵

∴

551999171199910mod8

即8｜(551999＋17).

(2) ∵

321mod8

∴

32n71n10mod8

即8|(3＋7).

2n（3）∵

192mod17,194241mod17

∴

19100011942501125010mod17

即17｜(191000-1).

例3（第六届IMO试题）

37

湖北师范学院2011届数学与统计学院学士学位论文

n（1）求出所有正整数n使21能被7整除；

n（2）证明：没有正整数n能让21被7整除.

解：（1）依题意，即求使

231mod72n1mod7的所有正整数n.

因为，所以对n按模3进行分类讨论：

2n23k1mod7 若n3k， ；

2n23k22mod7若n3k1， ；

若n3k2，

2n23k224mod7

n 故，当且仅当3|n时，21是7的倍数。

（2) 证明：由（1）知，

23k12mod723k113mod723k215mod7

8

湖北师范学院2011届数学与统计学院学士学位论文

所以没有正整数n能让2n1被7整除。

例42、对任意的自然数n，证明：

A2903n803n464n261n

能被1897整除.

证明：因为18977271，7与271互质.

因为， 29035mod7

8035mod74642mod7

2612mod7

所以， A2903n803n464n261n



5n5n2n2n0mod7

故，7|A.又因为，

2903193mod271

9

湖北师范学院2011届数学与统计学院学士学位论文

803261mod271 464193mod271

nnnn所以， A2903803464261

故271|A.又193n261n193n261n0mod271

7,2711，所以1897整除A.

nnn2例5、已知n为正奇数，求证：60|6321。

证明：因为若n是正奇数，则

nnn1n2n2n1xy(xy)(xxyxyy)；

nnn1n2n2n1xy(xy)(xxyxyy)；

nnnnnn3|633|213|6321； 所以， ，，从而

4|6n2n，4|3n1，从而4|6n3n2n1；

10

湖北师范学院2011届数学与统计学院学士学位论文

5|6n1，5|3n2n，从而5|6n3n2n1；

nnn60|6321。 (3,4,5)134560又且，所以

3.1.2利用同余理论可证明检查因数的结论

（1）若一个整数的末位数字能被2（或5）整除，则这个数能被2（或5）整除，否则不能；

（2）一个整数的数码之和能被3（或9）整除，则这个数能被3（或9）整除，否则不能；

（3）若一个整数的末两位数字能被4（或25）整除，则这个数能被4（或25）整除，否 则不能；

（4）若一个整数的末三位数字能被8（或125）整除，则这个数能被8（或125）整除，否则不能；

（5）若一个整数的奇位上的数码之和与偶位上的数码之和的差是11的倍数，则这个数能被11整除，否则不能。

下面主要证明（2）和（5），其余可类似证明。

证明：设aanan1a0是任意一个正整数，把a写成十进制数的形式：

11

湖北师范学院2011届数学与统计学院学士学位论文

aanan1a0an10nan110n1a0，

其中ai是整数且0≤ai﹤10,i0,1,2,,n.

101mod3,101mod910i1mod3或9，iN（2）因为，从而，

所以

a0mod3a0mod9aan10nan110n1a0anan1a0anan1

aan10nan110n1

注：算术中的“弃九验算法”就是依据本题的结论。

101mod11,（5）因为从而

1021mod11,1031mod11,,10n(1)nmod11

所以，

aan10nan110n1a110a0

a1a0mod11

an(1)nan1(1)n112

湖北师范学院2011届数学与统计学院学士学位论文

mod11 (a0a2a4)(a1a3a5).

同理，我们很容易证明：

若

aan1000nan11000n1a0,0ai﹤1000,i0,1,2,,n,

则a能被7或11或13整除的充要条件是

7或11或13|(a0a2a4)(a1a3a5).

例6、证明：若a75312289，则13是a的因数，7、11均不是。

12证明：因为a7510003121000289，而2897531252

且只有13|52, 7和11均不能整除52

故13是a的因数，7、11均不是。

3.1.3 与完全平方数有关的问题，常以4（或8)为模

同余理论中平方数的两个重要特征：

13

湖北师范学院2011届数学与统计学院学士学位论文

①任意平方数除以4余数为0和1；

②任意平方数除以8余数为0，1，4.

奇数2(2k1)24k24k11mod4证明：①因为 ，

偶数2(2k)24k20mod4， kN.

所以

1mod4,n是奇数n20mod4,n是偶数

奇数2=2k14k24k14k(k1)12 ②因为，又两个连续整数k，k+1中必有偶数，所以

4k(k1)是8的倍数，从而

奇数2=8t11mod8，t是整数.

又因为

偶数2=2k4k22，对k分二种情况讨论：l是整数，

偶数2=4k216l20mod8k2l 当时， ；

14

湖北师范学院2011届数学与统计学院学士学位论文

偶数24k2=16l(l1)44mod8k2l+1 当时， .

综上，

1mod8,n是奇数n0或4mod8,n是偶数

2例7(1972年基辅数学竞赛题）证明：11,111,1111，中没有平方数。

4证明：平方数关于模4同余0或1，换句话说，关于模4同余2或3的数一定不是平方数。而

1111113mod4，故11,111,1111，中没有平方数。

例8(1954年苏联数学竞赛题)能否找到自然数a和b,使

422 a1954b.

解：不能。

19542mod4,b20或1mod4b 理由如下:设为自然数，由知，

1954b22或3mod4

15

湖北师范学院2011届数学与统计学院学士学位论文

222这说明1954+b不是平方数.故找不到自然数a和b，使a1954b.

3.1.4 求末k位数问题，常以10为模

k求个位数与末两位数的问题，其实质也就是求一数被10或100除所得余数的问题。

例9、求4735528127924的末位数字。

4358124358124解：∵4752279729

483242019454 7314 729

3215mod10

358124∴4752279的末位数字是5.

说明：在求解本题的过程中用到了以下结论：任何正整数的乘方之个位数重复出现的周期为4，即

a4klalmod10，其中a是任意正整数，k为自然数，l1,2,3,4.

例10、求3406的末两位数。

616

湖北师范学院2011届数学与统计学院学士学位论文

解：利用欧拉定理有：因为(3,100)=1,所以

从而，

3(100)3401mod100

4063即的末两位数是29.

34063401063629mod100

3.1.5 与奇偶性有关的问题，常以2为模

一个整数与它的相反数、绝对值奇偶性都相同，两整数和与差的奇偶性相同。若用语言可叙述如下：

aamod2,|a|amod2,a+babmod2.

例11、设a1,a2,4,a6464的任意一种排列， 是自然数1,2，， ①令b1|a1a2|,b2|a3a4|,,b32|a63a64|；

②c1|b1b2|,c2|b3b4|,,c16|b31b32|；

17

湖北师范学院2011届数学与统计学院学士学位论文

③d1|c1c2|,d2|c3c4|,,d8|b15b16|；

④

这样一直做下去，最后得到一个整数x，求证：x为偶数.

证明：因为b1+b2b64|a1a2||a3a4||a63a64|

a1a2a3a4 a1a2a3a4a63a64

a63a64mod2

所以，经过一步“运算”，①变成②，但和的奇偶性未发生变化。

同样，经过多步“运算”依然如此，故

xa1a2 12即证x是偶数.

a64

640mod2

18

湖北师范学院2011届数学与统计学院学士学位论文

例12、（1998年美国数学奥林匹克）设集合1,2,8,1998被分为999个彼此不想交的二元子集

ai,bi，并且对1i999均有aibi9991或6.求证：和数

abii1999i的末位数字为9.

分析：首先明确i1abiia1b1a2b2+a999b999，表示999个这类绝对值的和。求末位数，直接考虑模10就难确定，而考虑模5

字的为题可转化为模10的余数问题，但条件是却很方便。

aibi1或6解：由条件，对任何1i999有

aibi1mod5，从而

999abii1999i9994mod5

于是i1abii的个位数字为9或4.

又aibiaibiaibimod2，有

abab12iiiii1i199999919981mod2

即i1abi999i为奇数，故其个位数字必为9.

19

湖北师范学院2011届数学与统计学院学士学位论文

在整除问题中，还有一个重要结论：连续n个整数中，必然存在唯一的一个整数属于模n同余0的剩余类（即该集合包含了所有n的倍数），则任意连续n个整数之积必是n!的倍数。

3kk对于任一整数,均有k(k1)k(k1)，而连续三个整数中必然有一个是3的倍数，所以有

3|k3k成立。

例13[7]、设a,b,c为正整数，且满足abc9，求证a3b3c3100.

333证明：假设abc100，由已知，

333(abc)(abc)91

333于是 (aa)(bb)(cc)91

3333|aa,3|bb,3|cc，但3不能整除91，假设是错误的。 因为

333因而abc100得证。

3.2同余理论用于求解不定方程

例14[2]、证明方程

20

湖北师范学院2011届数学与统计学院学士学位论文

44xy25z

没有整数解。

证明：对任一整数x，以5为模，有

x0,1,2mod5x20,1,4mod5x40,1,1mod5

即对任一整数x，

x40,1mod5

同样，对于任一整数y，

所以，

y40,1mod5

x4y422,3,4mod5，而5z0mod5，从而所给方程无整数解。

说明：本题所采用的方法是同余中证明不定方程无整数解的基本方法即余数分析法，但这种方法也非常灵活，关键在于确定所取的模(本例我们取模5)，这往往应根据问题的特点来确定。如上面例8也采用的是此法。

21

湖北师范学院2011届数学与统计学院学士学位论文

例15[3]（第23届IMO试题）试证:

323x3xyyn有一组整数解x,y，n（1）如果正整数及方程那么这个方程至少有三组整数解；

（2）当n2891时，上述方程无整数解。 证明：（1）可证若x,y是原方程的一组整数解，则可找到另外两组不同的整数解：

yx,xy,xy ，

323x,yx3xyy2891 （） 则 （2）用反证法。假设有整数解，使得

x3y32mod3

于是，（ⅰ）若x0mod3,则y2mod3； （ⅱ）若x1mod3,则y1mod3； （ⅲ）若x2mod3,则y0mod3

对于第一种情况，令x3k,y3t2,k,tN，带入（）得：

3k33(3k)(3t2)2(3t2)3289122

湖北师范学院2011届数学与统计学院学士学位论文

左边

23mod9，右边2mod9，矛盾；

对于第二种情况，由（1）知另一组解u,vyx,x将导致

uyx0mod3,vx2mod3 这也就是第一种情况，已证；

同样，对于第三种情况，有另一组解(p,q)(y,xy）导致

py0mod3qxy2mod3 ，

这也归结到第一种情况，已证；

323x3xyy2891无整数解。 综上所述，

3.3同余理论与抽屉原理的综合应用

例16[7]（“十一五”全国教育技术研究课题管理专栏）对于任意的五个自然数，证明其中必有3

个数的和能被3整除。

解:首先构造抽屉：任何自然数除以3所得的余数只能是0,1,2中的一个，不妨分别构造三个抽

23

湖北师范学院2011届数学与统计学院学士学位论文

屉——[1],[2],[3].然后讨论。

若这五个自然数除以3后所得的余数分别分布在这三个抽屉中，我们从这三个抽屉中各取一个，其和必能被3整除；

若这5个余数只分布在其中两个抽屉中，则其中一定有某个抽屉包含3个余数。而这3个余数之和或者为0，或者为3，或者为6.故所对应的3个自然数之和是3的倍数；

若这5个余数分布在其中的一个抽屉，很显然，必有3个自然数之和能被3整除。综上命题得证。

注1:抽屉原理的内容为：把n+1个元素任意放入n个抽屉，则其中必有一个抽屉里至少有2个元素。应用抽屉原理解题，关键是根据题目构造合适的抽屉。

注2：实际上题目中抽屉的构造，是按照模3的完全剩余类进行构造的。

4.小结

本文从数学竞赛这个范围入手，着眼于数论在数学竞赛中的地位和作用，介绍了同余理论的系统知识及同余性质的一些应用，并对数学竞赛中有关同余理论的应用作了系统的划分，主要针对同余理论在整除方面的应用加以系统归纳，并举一些例子进行说明，同时也介绍了同余理论在证明不定方程无整数解及与抽屉定理综合应用两方面的简单应用，充分说明了同余理论在中学数学竞赛中

24

湖北师范学院2011届数学与统计学院学士学位论文

重要地位及应用。

5.致谢

经过半年的忙碌和工作，本次毕业论文已经接近尾声，在这里首先要感谢我的指导老师左可正教授。左老师平日里工作繁多，但在我做毕业论文的每个阶段，从初次选题到查阅资料，论文初稿的确定和修改，中期检查，后期详细设计等整个过程中都给予了我悉心的指导，细心地纠正论文中的错误并给予指导。如果没有他的大力支持，此次论文的完成将变得非常困难。除了敬佩左老师的专业水平外，他的治学严谨和科学研究的精神也是我永远学习的榜样，并将积极影响我今后的学习和工作，然后还要感谢大学四年来所有的老师，为我们打下坚实的专业知识的基础。最后祝各位评审老师身体健康，工作顺利！

6.参考文献

[1]

闵嗣鹤，严士健.初等数论(第三版)[M].北京:高等教育出版社,2003.

[2] 余红兵.数学竞赛中的数论问题[M].上海:华东师范大学出版社,2005.

[3] 张亚芳.同余理论在数学竞赛中的应用[J].专题研究,2008,(02):58～59.

[4] 邢忠虎.例谈运用同余解题的取模技巧[J].中学数学研究,2008,(10):42～43.

25

湖北师范学院2011届数学与统计学院学士学位论文

[5] 武保强.浅谈同余理论的应用[J]. 中小学电教,2009,(11): 148～148.

[6] 戴红兵.在同余思想方法指导下寻求整除性问题的证明[J].思茅师范高等专科学校学报,

2007,23(6):42～44.

[7] 姜浩瑞.初等数论在高中数学解题中的一些应用[J].中学数学教学,2006,(05):

28～29.

[8] 方廷刚.整除与同余[J].数学教学通讯，2002,(S4):79～81.

26