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

《同余理论在数学竞赛中地运用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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是整数，并且，则；精彩文档实用标准文案（ⅴ）设,()以

3、及x,y都是整数，并且，，，则；（ⅵ）,,;（ⅶ）,;（ⅷ）若，，则;(ⅸ);(ⅹ).下面简单介绍一下，以上同余性质的一些应用。[例１]求被50除的余数。解：有性质（ⅴ）得，即所求的余数是29。[例２]求的个位数。解：因为因此若则（１）现在精彩文档实用标准文案所以由式（1）得到即n的个位数是3。[例３]证明：若n是正整数，则。11证明：因为再有性质（ⅵ）得，得证。[例４]已知求和。解：因为99=911所以（２）（３）有（２）式得：（４）有（３）式得：（５）由于，所以由式（４）与（５）得出或6，或，可得四个方程组，解得。２.２剩余类、完全剩余

4、系和简化剩余系[定义２]给定正整数m，对于每个整数i，,称集合是模的一个剩余类。[定义３]设m是正整数，从模m的每一个剩余类中任取一个整数精彩文档实用标准文案，称集合是模的一个完全剩余系（或简称为完全系）。由于的选取是任意的，所以模m的完全剩余系有无穷多个，通常称：i.ii.［定理３］整数集合A是模m的完全剩余系的充要条件是：i.A中含有m个整数；ii.A中任何两个整数对模m不同余。[定理４］设m剩余系，则也是模m的一个完全剩余系。　　［定理５］设分别是模和模的完全剩余系，则是模的一个完全剩余系。［推论１］若，的完全剩余系数时，的完全剩余系

5、数。［定理６］设，则当的完全剩余系数时，的完全剩余系数。［定义４］设Ｒ是模m的一个剩余类，，则称Ｒ是模m的一个简化剩余类。［例５］设，则在数列（６）中有且仅有一个数b，满足：(７)若则。解：因为（a，p）=1,所以由定理２，式（６）中的数构成模p的一个完全剩余类，因此，必有数b满足试（７），设b=ka，那么精彩文档实用标准文案i.；ii.，即p

6、(a+1)(a-1),因此p

7、a-1或p

8、a+1,这；iii.显然矛盾；iv.矛盾；若又有，故所以是不可能的，这就证明了唯一性。[例６]设m是给定的整数，求证存在整数a,b和k，其中a,b均不能被2

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

10、档实用标准文案，故可设,使由于，故故我们找到了这样的3个整数a，1，k,其中a,1均为奇数，，使从而原命题得证。２.３Euler定理同余理论中有一个非常著名的定理,并且它在理论和应用两个方面都是很重要的，它就是Euler定理。［定理７］（Euler定理）设是正整数，=1，则.［定理８］（Fermat定理）设是素数，则对于任意的整数，有.［定理９］（Wilson定理）设为素数，则.［定理１０］（孙子定理）设，是两两互素的正整数，记，，同余方程组，，……的一切解为，其中，.下面列举一下这些定理的运用。[例７]设是使成立的最小正整数，则（１）（２

11、）对于任意的。解：（１）由Euler定理，，因此，由带余数除法，有：精彩文档实用标准文案因此，由上式及do的定义，利用定理１，我们得到即整数r满足有do的定义可知必是r＝０，即。