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

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

卢军萍

杭州师范大学 数学与应用数学043班

摘要：这些年来，同余理论在数学竞赛中的应用越来越广泛。本文详细了同余理论的基础知识，并通过举例以便更好的理解。并重点对数学竞赛中有关同余理论的应用作了系统的划分。每一部分都有2-4个例题加以举例说明。 关键词：同余；数学竞赛

１ 引 言

数学竞赛已逐渐形成一门特殊的数学学科——竞赛数学。像IMO竞赛等等受到越来越大的重视。而在数学竞赛中，初等数论的有关题目占得比例越来越大，尤其是同余理论在数学竞赛中有着举足轻重的地位。下面，本文重点论述一下同余理论在数学竞赛中的运用。首先，先介绍一下同余的一些基本知识。

２ 同余的性质及几个重要的定理

２.１同余的定义、性质

[定义１] 给定正整数m，如果整数a与b之差被m整除，则称a与b对于模m同余，或称a与b同余，模m，记为

a?b?modm?,

此时也称b是a对模m的同余。

如果整数a与b之差不能被m整除，则称a与b对于模m不同余。 [定理１] 下面的三个叙述是等价的： （ⅰ）a?b?modm? ；

（ⅱ）存在正整数q，使得a?b?qm, （ⅲ）存在整数q1，q2，使得a?q1m?r[定理２] 同余具有下面的性质： （ⅰ）（自反性）a?a(modm)；

（ⅱ）（对称性）若a?b(modm)，则b?a(modm)； （ⅲ）（传递性）若a?b,b?c(modm)，则a?c(modm)； （ⅳ）假设a,b,x,y是整数，并且a?b(modm),x?y(modm)，则

,a?q2m?r，0?r?m.

a?x?b?y(modm),ax?by(modm)；

1

（ⅴ）设ai,bi (0?i?n)以及x,y都是整数，并且x?y(modm)，ai?bi(modm)，

0?i?n，则

?nnaxi??biyii(modm)；

i?0i?0（ⅵ）a?b(modm),dm,d?0?a?b(modd);

（ⅶ）a?b(modm),k?0,k?N?ak?bk(modmk);

（ⅷ）若a?b(modmi)，(i?1,2,?,n)，则a?b(mod[m1,m2,?,mn]); (ⅸ)a?b(modm)?(a,m)?(b,m);

(ⅹ)ac?bc(modm),(c,m)?1?a?b(modm).

下面简单介绍一下，以上同余性质的一些应用。 [例１] 求(25733?46)26被50除的余数。 解： 有性质（ⅴ）得， (25733?46)26??733?4?26??7?72?16?4?26

??7??1?16?4?26??7?4?26

?326?3?35?5 ?3??7?5??3?7??72?2

??21???1?2??21

?29?mod50?

即所求的余数是29。 [例２] 求n?777的个位数。

解： 因为71??3,72??1,74?1?mod10?

因此若77?r?mod4?

则 n?777?7r?mod10? （１）

现在77?(?1)7??1?3?mod4?

所以由式（1）得到

2

n?77?73???3???7?3?mod10?,

73即n的个位数是3。

[例３] 证明：若n是正整数，则13|42n?1?3n?2。11 证明：因为42n?1?3n?2?4?42n?9?3n?4?16n?9?3n

再有性质（ⅵ）得，

4?16n?9?3n?4?3n?9?3n?13?3n?0?mod13?

得证。

[例４] 已知99|62??427,求?和?。 解：因为99=9?11

所以9|62??427, （２）

11|62??427, （３）

有（２）式得：9|6?2?????4?2?7?21????

?9|3???? （４）

有（３）式得：11|6?2?????4?2?7?13????

?11|2???? （５）

由于0??,??9，所以由式（４）与（５）得出

????15或6，????9或?2，可得四个方程组 ?????6?????6?????15?????15或?或?或??????9?????2????9?????????2 ，

解得??2，??4。

２.２剩余类、完全剩余系和简化剩余系

[定义２]给定正整数m，对于每个整数i，0?i?m?1,称集合

Ri(m)??n|n?i(modm),n?Z?

是模的一个剩余类。

[定义３]设m是正整数，从模m的每一个剩余类中任取一个整数xi(0?i?m?1)，称集合?x0,x1,?,xm?1?是模的一个完全剩余系（或简称为完全系）。

3

由于xi的选取是任意的，所以模m的完全剩余系有无穷多个，通常称： i. ii.

?0,1,2,?,m?1?是模m的最小非负完全剩余系；?1?1??m??(当m是奇数时),?,?1,0,1,?,m)或?－m2,?,?1,0,1,?,m22?12(当m是偶数时是模的绝对最小的完全剩余系。

［定理３］整数集合A是模m的完全剩余系的充要条件是：

i. A中含有m个整数； ii. A中任何两个整数对模m不同余。

[定理４］设m?1,a,b是整数（a,m）?1,{x1,x2,?,xm}是模m的一个完全剩余系，则?a1x1?b,a2x2?b,?anxn1?b?也是模m的一个完全剩余系。

［定理５］设m1,m2?N,A?Z,(A,m)?1, X?{x1,x2?xn},Y?{y1,y2?yn} 分别是模m1和模m2的完全剩余系，则R?{Ax?m1y|x?X,y?Y}是模m1,m2的一个完全剩余系。

［推论１］若m1,m2?N,(m1,m2)?1，则当x1和x2分别通过模m1和模m2的完全剩余系数时，m2x1?m1x2通过模m1,m2的完全剩余系数。

［定理６］设mi?N(1?i?n)，则当xi通过模mi(1?i?n)的完全剩余系数时，

x?x1?m1x2?m1m2x3???m1m2?mi?1xn通过模m1m2?mn的完全剩余系数。

［定义４］设Ｒ是模m的一个剩余类，若有a?R,使得(a,m)?1，则称Ｒ是模m的一个简化剩余类。

［例５］设p?5是素数，a?{2，3?p?2}，则在数列

a,2a,3a,?(p?1)a,pa （６）

中有且仅有一个数b，满足：

b?1(mod p) (７)

若b?ka则k?a,k?{2,3,?p?2}。

解：因为（a，p）=1, 所以由定理２，式（６）中的数构成模p的一个完全剩余类，因此，必有数b满足试（７），设b=ka，那么 i.

k?p,否则b?pa?0(modp)与b?1(modp)；

4

ii.

k?a,否则b?a2?1(modp)，即p|(a+1)(a-1),因此p|a-1或p|a+1,

这与2?a?p?2矛盾； iii. iv.

显然k?1,否则b?1?a?1(modp),即p|a?1,这与2?a?p?2) 矛盾；

k??1,否则b??1?a?1(modp),即p|a?1,这与2?a?p?2)矛盾；

若又有k',2?k'?p?2,使得b?k'a(modp),则k'a?ka(modp)，故(a,p)?1 所以k?k'(modp),从而p|k?k'是不可能的，这就证明了唯一性。

[例６]设m是给定的整数，求证存在整数a,b和k，其中a,b均不能被2整除，k?0 使得2m?a19?b99?k?21999（1999年第四届冬令营试题）。

分析：这道题说难不难，说易不易，关键在于是否将上试看成一个同余的形式如果能找到a,b为奇数，满足上式，则原问题可以很快解决，2m?a19?b99(mod21999)，

像k?0这样的限制条件实际上是障眼法。而上面所举的同余方程，要证他有解，则可利

用剩余系的理论。

证明：先证明如下的引理

引理：当a通过模21999的一个简化剩余系时，a亦通过2191999的一个简化剩余系。

实事上，由于当(a,21999)?1时，（a19,21999）?1

1999故引理只需要证明当a与b对于模2对于模21999不同余，且a与b均为奇数时，a与b

1919也不同余。

19由于(a18?b19)?(a?b)(a18?a17b1???a1b17?b18)

17111718而a?ab???ab?b为19个奇数之和，仍为奇数，故

21999|a19?b19?21999|a?b

下证原命题： 由于2m?1与21999互质，故由引理可知

1999存在a?Z,(a,2不妨设a19)?1,且a19?2m?1(mod21999)

?2m?1，否则我们可以取充分大的t?Z?，用a?t?21999代替上面的a，故

19可设k?Z,使2m?1?a?k?21999

5

由于a19?2m?1，故k?Z?

故我们找到了这样的3个整数a，1，k,其中a,1均为奇数，k?0，使

2m?a19?b99(mod21999)

从而原命题得证。 ２.３Euler定理

同余理论中有一个非常著名的定理,并且它在理论和应用两个方面都是很重要的，它就是Euler定理。

［定理７］（Euler定理 ） 设m是正整数，(a,m)=1，则

a?(n)?1(modm). ［定理８］（Fermat定理） 设p是素数，则对于任意的整数a，有

ap?a(modp).

［定理９］（Wilson定理） 设p为素数，则(p?1)!??1(modp).

［定理１０］（孙子定理） 设n?2，m1,m2,?,mn是两两互素的正整数，记

M?m1m2?mn，Mi?M(i?1,2,?,n)，同余方程组 mix?c1(modm1)， x?c2(modm2)，

??

x?cn(modmn)

的一切解为x??MMii?1n'iic(modM)，其中MiM'i?1(modmi)，i?1,2,?,n.

下面列举一下这些定理的运用。

[例７]设(a,m)?1,do是使a?1(modm)成立的最小正整数，则 （１）do|?(m)

（２）对于任意的i,j,0?i,j?do?1,i?j,有a与a对于模m不同余。 解：（１）由Euler定理，do??(m)，因此，由带余数除法，有：

ijd?(m)?qdo?r,q?Z,q?0,0?r?do

6

因此，由上式及do的定义，利用定理１，我们得到

1?a?(m)?aqdo?r?ar(modm)

即整数r满足ar?1(modm)0?r?do 有do的定义可知必是r＝０，即do|?(m)。

（２）假设存在i,j,0?i,j?do?1,i?j,ai?aj(modm)

不妨设i?j,因为（a,m)?1,所以ai?j?0(modm),0?i?j?do这与do的定义矛盾，则假设不成立。

得证。

[例８]设n是正整数，记Fn?22?1,则2nFn?2(modFn)

解：容易验证，当n?4时，Fn是素数，所以由Fermat定理可知结论显然成立。 当n?5时，有n?1?2n,2n?1|22 记：22nn ?k2n?1，则2Fn?2?2n?122n?2?2(2n22n?1)?2(k2n?1?1)?2[(22n?1)k?1]?2P(22?1)?Q(22?1)Fn其中Ｐ和Ｑ都是整数，上式即是2?2(modFn)

证毕。

[例９]求整数，它被3，5，7除的余数分别是1，2，3。

?n?1(mod3)?解：n是同余方程组?n?2(mod5) 的解，在孙子定理中，

?n?3(mod7)?取 m1?3,m2?5,m3?7,m?m1?m2?m3?105，

M1?35,M2?21,M3?15

则35M1'?1(mod3),2M1'?1(mod3),得M1'?2； 21M2'?1(mod5),M1'?1(mod5),得M2'?1； 15M3'?1(mod7),M3'?1(mod7),得M3'?1；

105)。 所以n?1?35?2?2?21?1?3?15?1?157?52(mod7

因此，所求的整数n＝52+105t，t?Z。

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

３.１同余理论用于处理有关整数的进制问题

[例１０]一个四位数，它的个位数字与百位数字相同，如果把这个四位数的数字顺序颠倒一下（即千位数字与个位数字互换，百位数字与十位数字互换），所得的新数减去原数得7812，求原来得四位数。（1979年云南省竞赛题） 解：设该数的千位，百位，十位数分别为x,y,z,则

原数为 103x?102y?10z?y， （８） 颠倒后的新数为103y?102z?10y?x， （９） （９）-（８）得：7812=999（y-x）+90(z-y)

即：868=111（y-x）+10(z-y)= 102(y?x)?10(z?x)?(y?x) 则??y?x?8原数千位数字x不能为0，则x?1,y?x?8?9，

?z?x?6又显见百位数字y?9，所以y=9，则x=1，z=7，故所求四位数为1979。 [例１１]N是整数，它的b进制表示是777。求最小的正整数b，使得N为十进制的四次方。（第9届加拿大竞赛题） 证明：由题意是求最小的正整数b，使得方程7b?7b?7?x（１０）对x有整数解。

而7b?7b?7?0(mod7),则x?0(mod7)

又因为7是素数，所以x?0(mod7)，为此不妨设x?7k 则（１０）式化为b?b?1?7k 最小b的出现在k最小的时候 取k=1，此时有b?b?1?343

22342424b2?b?342?0

即(b?18)(b?19)?0

解得正整数 b?18，即有(777)18?(74)10

３．2同余理论用于处理有关整除的问题

整数与求余是密切相关的，若能把同余理论在整除问题中灵活运用，可方便快速的解决许多问题。

[例１２]证明（１）没有正整数能让被7整除

8

（２）求出所有正数使能被7整除。（第六届IMO 试题）

解：（１）依题意，即求得2n?1(mod7)的所有正整数n，

通过计算我们有

21?2(mod7)，22?4(mod7)，23?1(mod7)，

23k?(23)k?1k(mod7) （１１）

当n不是3的倍数时，有两种情况：

１n?3k?1而23k?1?2?(23k)?2(mod7) （１２） ２n?3k?2而23k?2?4?(23k)?4(mod7) （１３）

故只有当n是3的倍数时，2?1能被7整除. （２） 由（１１）（１２）（１３）式有：

n23k?1?2(mod7)， 23k?1?1?3(mod7)， 23k?2?1?5(mod7)，

故没有正整数n能让2?1被7整除.

[例１３] 证明：正整数A是完全平方数的充分必要条件是对于任意整数n， （第51届捷克(A?1)2?A,(A?2)2?A,?,(A?n)2?A中至少有一项可以被n整除。和斯洛伐克奥林匹克题） 证明：充分性：若A?d，则

2n(A?j)2?A?(d2?j)2?d2?(d2?d?j)(d2?d?j)

由于d?d?j对于j?1,2,?,n是连续的个正整数， 所以，一定有某个j使得(A?j)?A可以被n整除。

必要性：假设A不是完全平方数，则A中一定有一个素因子，其指数为奇数次幂，即存在k，使得

22A?0(modp2k?1)，且p2k不整除A

取n?p2k，对于j?1,2,?,p，一定存在一项j，

22k2k使得(A?j)?A?0(modp) 又因为p2k不整除A，所以p22k不整除(A?j)

2k2k?12但是由(A?j)?A?0(modp)且A?0(modp)

9

可得(A?j)2?0(modp2k?1)

由于(A?j)2是完全平方数，则一定有(A?j)2?0(modp2k)，矛盾 所以假设不成立，A是完全平方数。 证毕

３.３同余理论应用于解决有关数列问题

[例１４]数列?pn?定义如下：p1?2,pn为的最大质因子。问：1?p1?pn?（）1n?111是否在此数列中出现。

解：若存在n?N，使pn?11，则由p1?2,p2?3,p3?7,可知n?4,

并且1?p1p2?pn?1与2，3，7互质，于是， 设5??11?,??0,??1 （14）

对（14）两边模4，应有?1?1??(?1)??(?1)?(mod4)，故?为奇数。 对（14）两边模3，应有1?(?1)??(?1)??(?1)???(mod3)，故?为奇数。 对（14）两边模7，应有1?(?2)??(4)???2??22?(mod7)，故

?2??2??6(mod7)这与对任意n?N?，2n?1,2,4(mod7)矛盾

所以11不在?pn?中出现。 [例１５] 设{an},{bn}定义如下：

a0?1,a1?1,an?1?an?2an?1，

， b0?1,b1?7,bn?1?2bn?3bn?1 （n?1,2,?）

证明：除“1”外这两个数列没有其他相同的项. 分析：这两个数的前n项分别是：

an:1,1,3,5,11,21,43,85?

bn:1,7,17,55,161,487,1457,4357,?

欲证n?3时，{an},{bn}没有相同的项，直接论证有一定的困难，我们转而考察被某个正整数除后所得的余数，逐次用2，3，?去除an，bn前面各项，可以发现

a2n?1?3(mod8),a2n?2?5(mod8)，

10

b2n?1?1(mod8),b2n?2?7(mod8)。

即数列{an(mod8)}是由3，5组成的周期为2的数列，数列{bn(mod8)}是以1，7组成的周期为2的数列，以下用数学归纳发给以严格论证。

初值已验证。假设

a2k?1?3(mod8),a2k?2?5(mod8) b2k?1?1(mod8),b2k?2?7(mod8)

则

a2(k?1)?1?a2k?3?a2k?2?2a2k?1?5?2?3?11?3(mod8)， a2(k?1)?2?a2k?4?a2k?3?2a2k?2?3?2?5?11?3(mod8)， b2(k?1)?1?b2k?3?2b2k?2?3b2k?1?2?7?3?1?13?5(mod8)， b2(k?1)?2?b2k?4?2b2k?3?3b2k?2?2?1?3?7?1?3(mod8)。

因此，n?k?1时上述猜想是正确的，从而一切不小于3的自然数n猜想正确，所以原命题成立。

３.４同余理论用于求解不定方程

[例１６]确定方程

?xi?1144i?1599的全部非负整数解(x1,x2,?,x14)，不记排列的

次序。（第八届IMO试题）

解：当x为偶数时，显然x?0(mod16)

当x为奇数时，显然x?1(mod16)

这样，任意整数的四次方对于模16只有0，1两个可能值， 从而

44?xi?1144i对于模16的所有可能值是0，1，2，?，14

但1599?15(mod16)，因此原方程无解

注意：对于不定方程的问题，如果直接求解有困难，不妨从方面考虑一下，看能否证明其无解。此题注意到整数x,x具有16k和16k+1的形式，从而考虑模16来证明方程无整数解。

[例１７] 试证：（１）如果正整数n及方程x?3xy?y?n有一组整数解

3234(x,y)，那么这个方程至少有三组整数解。

11

（２）当n=2891时，上述方程无整数解。 （第二十三届IMO试题）

证明：（１）可证明若(x,y)是原方程的一组整数解，则可找到另外两组不同的整数解：

(y?x,?x);(?y,x?y).

（２）用反证法，假设有整数解(x,y)使得：

x3?3xy2?y3?2891， （１５） 则

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，代入（１５）得：

(3k)3?3(3k)(3t?2)2?(3t?2)3?2891，

左边?2(mod9)，右边?2(mod9)，矛盾；

3u?y?x?0(mod3)，对于第二种情况，上述另一组解(u,v)?(y?x,?x)将导致：v??x?2(mod3)，这也就是第一种情况，已证；

对于第三种情况：x?3k?2,y?3t，代入（１５）得：

(3k?2)3?3(3k?2)(3t)2?(3t)3?2891，

左边?2(mod9)，右边?2(mod9)，矛盾。 综上所述，方程x?3xy?y?2891无整数解。 ３.５同余理论应用于解决有关染色问题

3233?，1,2,3,?2004[例１８]设S??求证：必定可以对Ｓ中的数进行４中颜色的染色，

使得Ｓ中任意７个构成等差数列的数不同色。

证明：由于2004?2058?6?7，故可将Ｓ的每一个数表示成７进制中的４位数

3(dcba)7(当位数不够在前面添０)。

12

记

Ai??x?S|x?(dcba)7,a?i,b?i,c?i?,i?1,2,3,4

则S?A1?A2?A3?A4，事实上，对?小?S，x?(dcab)7,有i??1，2，3，4?，使得

i??a,b,c?,则x?Ai，将A1,A2\\A1,A3\\(A1?A2),A4\\(A1?A2?A3)中的数对应

染上第一，二，三，四种颜色，下证这种染色方法满足要求。

只需证明Ai(1?i?4)中无７项构成等差数列。 反证法，假设a?jd(j?0,1,2,?,6)均在Aj，

?6 若７不整除d，则a?jd(j?0,1,2,?,6)的７进制的末位数字通过了0,1,2,从而存在j使得a?jd的末位数字为i?{1,2,3,4},即a?jd?Ai。

若d?0(mod7)，而d?0(mod72)则a?jd(j?0,1,2,?,6)的７进制的倒数第

?6，故也存在j使a?jd?Ai，又矛盾。 二位数字通过了0,1,2,若d?0(mod72)，而d?0(mod73)则a?jd(j?0,1,2,?,6)的７进制的倒数第三位数字类似地导出矛盾。

若d?0(mod7),则a?6d?1?6?7?2004,a?6d?S，矛盾。 综上，假设不成立，从而结论得证。

[例１９] 给集合M?{1,2,?,n?1}(n?3)中每个数染色，若 ① 对i?M,i与n?i同色，

② 存在(k,n)?1，使对任意i?M，i?k，i与|i?k|同色， 求证M只有一个色。

分析：设k?M，且(k,n)?1，则k?0,k?1,?,k(n?1)是n的完系。

再令k?l?ql?n?rl，其中0?rl?n?1。

那么，rl?kl(n)，且r0,r1,?,rn?1也是n的一完系，由于0?rl?n?1，所以它是n的最小非负完系0,1,?,n?1的一个排列，但r0?0，从而r1,?,rn?1是

331,?,n?1的一个排列。

欲证M同色，只需证rl(l?1,2,?,n?1)同色，现用数学归纳法证明。

13

证明：（１）当n?3时，M?{1,2}，由题设①知，M同色，命题为真.

（２）假设当1?l?n?2时，rl同色，现欲证rl与rl?1也同色.

若rl?n?k，由于k(l?1)?(ql?n?rl)?k?ql?n?(rl?k)，并注意到，所以rl?k是k(l?1)被n除所得的余数，即rl?1?rl?k，由题设0?rl?k?n条件②可知，rl?1与rl?1?k同色，即rl?1与r同色.

若rl?n?k，由于k(l?1)?ql?n?rl?k?(ql?1)n?(rl?k?n)，并注意到，所以rl?k?n是k(l?1)被n除所得的余数，即rl?1与k?rl?1同0?rl?k?n?n，色.

又由题设条件①，rl与n?rl同色，故rl?1与rl. 若rl?n?k，则产生矛盾，事实上，这时有

k(l?1)?kl?k?ql?n?rl?k?ql?n?(n?k)?k?(ql?1)n

这说明n|k(l?1)，于是rl?1?0，但这与只有rl?0相矛盾. ３.６利用构造剩余系解同余问题

通过构造完全剩余系，简化剩余系可以巧妙地解决一些同余问题。 [例２０]试确定具有下述性质的所有正整数n，集合

M??n,n?1,n?2,n?3,n?4,n?5?

可以分成两个不相交的非空子集，使得一个子集中所有元素的积，等于另一个子集的所有元素之积。

解：在Ｍ中加进数n?6,则n，n?1,n?2,n?3,n?4,n?5,n?6是模７的一个完全剩余系。

假定有满足题设条件的n存在，分两种情况讨论：

（１）７不整除n＋６，则有ai?M,使ai?0(mod7)

设两个子集的元素的积为m，则m?0(mod7)。因为７是质数，故Ｍ中必有一个ai?aj,使ai?0(mod7)这不成立。 （２）７整除n＋６，则令Ｍ分成的两个子集的元素的乘积为m，便有：

m2?n(n?1)(n?2)(n?3)(n?4)(n?5)?1?2?3?4?5?6??1(mod7) 14

而x2??1(mod7)无解，事实上：

12?1,22?4,32?2,42?2,52?4,62?1(mod7) 所以满足条件的m不存在

综上所述，满足题设条件的n不存在。

[例２１] 设m,n?N?，且m为奇数，证明：和数1?2???m (m,2n?1)?1。是m的倍数。

证明：因为１，２，?，m是模m的完全剩余系， 所以2,2?2,?,2?m也是完全剩余系。

nnn 则

?(2k)k?1mn??kn(modm)

k?1mm

?(2?1)?kn?0(modm)

nk?1n

即m|(2?1)m?kk?1nmn,而(m,2n?1)?1

故m|?kk?1，得证。

３.７同余理论用于证明有关重要定理

[例２２]用同余理论证明著名的Euler定理。

证明：设a1,a2,?a?(m)是模m的一个简化剩余系，因为(a,m)?1，

所以 aa1,aa2,?aa?(m)也是模m的一个简化剩余系，对于同一个剩余类，上述两个剩余系各有一数是其中的元素，因此，这两个数应同余，不妨设ai与aaki同余，

(i?1,2,?,?(m))，其中k1,k2,?k?(m)是1,2,?,?(m)的一个排列，即有

ai?a?aki(modm)， i?1,2,?,?(m)。

累乘得

a1?a2???a?(m)?a?(m)?ak1?ak2???ak?(m)(modm)，

又 (ai,m)?1，所以(a1?a2???a?(m),m)?1。 因此，可约去 a1?a2???a?(m) 得 a证毕。

?(m)?1(modm)。

15

[例２３]用同余理论证明Fermat定理。 证明： 若(a,p)?1，则由欧拉定理得到

ap?1?1(modp)?ap?a(modp). 若(a,p)?1，则p|a，所以 ap?0?a(modp).

证毕.

３.８同余理论用于其他方面

[例２４]欧拉的一个猜想在1960年被美国的数学家推翻，他们证实了存在正实数n，使得133?110?84?27?n，求n的值。（第七届美国数学邀请赛） 解：分三步来解这个问题 ⒈ 先对n进行初步估值

因为1.335?10,1.105?10,0.845?1,0.275?1

555551.335?1.105?0.845?0.275?22?25

所以 133〈 n〈 200。 ⒉ 求出n的个位数

由R(a5)?R(a)(mod10)可知：

1335?1105?845?275?3?0?4?7?4(mod10)

∴个位数为4。 ⒊ 求n的十位数

根据余数判别法可知：

1335?1105?845?275?0(mod3)

所以n?0(mod3) 即：3∣n，n=144或174 仍根据余数判别法可知：

51335?1105?845?275?2(mod7) n5?2(mod7)

所以n=144。

[例２５]数1978与1978的最后三位数相等，试求出正整数m和n，使得m?n取最小值这里n?m?1。

分析：因为数1978与1978的最后三位数相等，所以1978?1978(mod1000)，

16

nnmmnm

而 1000?8?125， 故

1978n?1978m(mod8) （１６）

1978n?1978m(mod125) （１７）

由于

1978?1976?2?2(mod8)?2n?2m(mod8) （１８）

又由于n?m?1，显然m?1,2时，（１８）式不成立，所以m?3，再由（１７）式得

(53,1978n)?1，

1978n?1978m(mod125)?1978n?m?1(mod125) （１９）

而1978的各次幂的个位树只能取8，4，2，6循环，所以只有当n?m为4的倍数时，（１９）才能成立.不妨设n?m?4k，

注意到19784?(1975?3)4?34?1(mod5)，19784?1(mod25)。 可令1978?5t?1， 则

40?19784k?1?(5t?1)k?1?2k(k?1)?(5t)2?k?5t(mod125)。 2于是k应含有5作为因子，其最小为25.因此n?m?4?25?100最小。 而

m?n?(n?m)?2m,n?m?0,2m?0，

所以当n?m和2m均最小时， m?n最小，此时

n?m?100?2?3， 其中m?3,n?103。

以上是同余理论在数学竞赛中的有关应用的分类与举例，而鉴于同余理论在数论中的特殊地位，若要灵活地掌握和应用它，还需加强对数论知识的系统、有效的学习。

17

参考文献：

[1]. 李长明，周焕山.初等数学研究[M].北京：高等教育出版社，1995:66-95 [2]. 于秀源，瞿维建.初等数论[M].济南：山东教育出版社，2001:1-72

[3]. 李胜宏，李名德.高中数学竞赛培优教程(专题讲座)[M].杭州：浙江大学出版社，2003:1-52

[4]. 林永伟，叶立军.数学史与数学教育[M]. 浙江大学出版社，2004.4

[5]. 冷岗松，沈文选，唐立华.奥赛经典[M].湖南：湖南师范大学出版社，2006.3 [6]. 熊斌、冯志刚.数学竞赛之窗[J]. 数学通讯，2004，(11): 43-44 [7]. 陈晓辉.关于同余理论在中学奥赛中的应用[J]. 数学通讯，2001年第5期：43-45 [8]. 林晓燕.谈同余理论在初等数学中的几点应用[J].怀师专学报.1995年4月第14卷第一期：102-104

18

本文来源：https://www.bwwdw.com/article/p6jr.html