第36讲同余习题导学案教案奥数实战演练习题.docx

第36讲同余习题导学案教案奥数实战演练习题.docx

《第36讲同余习题导学案教案奥数实战演练习题.docx》由会员分享，可在线阅读，更多相关《第36讲同余习题导学案教案奥数实战演练习题.docx（14页珍藏版）》请在冰点文库上搜索。

第36讲同余习题导学案教案奥数实战演练习题

第17讲同余

同余是数论中的重要概念，同余理论是研究整数问题的重要工具之一。

设m是一个给定的正整数，如果两个整数a与b用m除所得的余数相同，则称a与b对模同余，记作，否则，就说a与b对模m不

同余，记作，

显然，；

1、同余是一种等价关系，即有自反性、对称性、传递性

1）.反身性：

；

2）.对称性：

；

3）.传递性：

若，则;

2、加、减、乘、乘方运算

若（modm）（modm）

则（modm），（modm），（modm）

3、除法

设（modm）则（mod）。

A类例题

例1．证明：

一个数的各位数字的和被9除的余数等于这个数被9除的余数。

分析20≡2（mod9），500≡5（mod9），7000≡7（mod9），……，由于10n－1=9M，则10n≡1（mod9），故an×10n≡an（mod9）。

可以考虑把此数变为多项式表示an×10n+an-1×10n-1+…+a1×10+a0后处理。

证明设a==an×10n+an-1×10n-1+…+a1×10+a0，

∵10≡1（mod9），∴10n≡1（mod9），

∴an×10n+an-1×10n-1+…+a1×10+a0≡an+an-1+…+a1+a0。

说明要熟练记忆并应用常见的数据模的特征。

例2．A，B两人玩一种32张扑克牌的取牌游戏，A先取，以后轮流进行，每次只能从剩下的牌中取1张，或者质数张牌，谁取到最后一张牌获胜，问：

谁有必胜策略？

分析原有32张牌，如果A总取奇数张牌，B只要取1张牌，使A面临偶数张牌就可以了，此时A总不能取完偶数张牌。

但2是质数，A可以取两张牌。

注意到32是4的倍数，A只能取奇数张牌或2张牌，B的应对方案稍作调整，可以有必胜的策略。

解B有必胜策略。

由于32≡0（mod4），

而A取的牌不能是4及其倍数，从而A取后，剩下的牌张数x≡3（mod4），或x≡2（mod4），或x≡1（mod4），

于是B可以通过取1，2或3张牌，使得剩下的牌的张数y≡0（mod4），

所以，B依次此策略，在A取后，剩下的牌张数不同余于0（mod4），总是有牌，而B取后剩下的牌的张数y≡0（mod4），从而B能取到最后一张牌。

例3在已知数列1，4，8，10，16，19，21，25，30，43中，相邻若干数之和，能被11整除的数组共有多少组。

分析相邻若干数之和可通过，中来实现。

解记数列各对应项为并记依次为1、5、13、23、39、58、79、104、134、177它们被11除的余数依次为1、5、2、1、6、3、2、5、2、1。

由此可得

由于是数列相邻项之和，且当时，则满足条件的数组有：

3+1+3=7组。

说明在解题的适当时候取模的运算会使运算量减少，并使过程变得简洁。

情景再现

1．能否把1，2，……，1980这1980个数分成四组，令每组数之和为，且满足。

2．两人做一种游戏：

轮流报数，报出的数只能是1，2，3，4，5，6，7，8，9，10，把两人报出的数连加起来，如果得数是2003，最后报数的人就获胜．现在甲、乙两人已经依次报过3，5，7，5，6，乙再接着报下一个数，那么乙经过动脑筋，发现应该报某一号就有赢的把握．试问乙应该报哪一号？

以后各次报数时乙应如何报数才能保证赢？

3．（前南斯拉夫数学竞赛，1988年）有27个国家参加的一次国际会议，每个国家有两名代表．求证：

不可能将54位代表安排在一张圆桌的周围就坐，使得任一国家的两位代表之间都夹有9个人．

B类例题

例4．共1998个小朋友围坐一圈，从某人开始逆时针方向报数，从1报到64，一直报下去，直到每人报过10次为止．

⑴有没有报过5，又报过10的人？

⑵有没有报过5，又报过11的人？

分析报过5（10）的人的编号模64的同余特征是本题的突破口。

解把这些学生依次编为1——1998号．

⑴设既报过5又报过10的人原编为x号，则有

x+1998k≡5（mod64）

x+1998l≡10（mod64）

∴1998（l－k）≡5（mod64），即1998（l－k）=5+64n，这不可能．

⑵既报5又报11的人原来编为x号．

x+1998k≡5（mod64）

x+1998l≡11（mod64）

∴1998（l－k）≡6（mod64），即14（l－k）=6+64n，Þ7（l－k）=3+32n，取n=1，得l－k=5，即第k圈报5的人，第k+5圈后报11，

∵1998×5=64×156+6，这说明前5圈报5的人共157个，即共有157人既报5又报11．

说明本题是同余在解不定方程（组）上的一个简单应用。

例5（1992年友谊杯国际数学竞赛）求最大的正整数x，使得对任意y∈N，有x|（）。

分析x最大不超过的最小值18，（mod18）（mod2）,（mod9）。

解由条件，x|（7＋12－1），x|18，故x≤18。

下证：

对任意y∈N，有18|（）。

事实上，首先是偶数，所以2|（）；其次，当y=3k（k∈N*）时，≡≡－1≡0（mod9），当y=3k＋1（k∈N*）时，≡≡7＋3－1≡0（mod9），当y=3k＋2时，≡≡49－4≡0（mod9）。

故对任意y∈N*，有9|。

∵（2，9）=1∴18|

所求的x为18

说明本题中将模18分解为模2与模9来处理充分观察到模9的特征。

例6试求出一切可使被3整除的自然数。

分析。

对n按6的同余类分类处理。

说明要体会模6的选取。

中对n按模3分类，对按模2分类可以分别确定结果，所以选择按模6分类。

情景再现

4．设a为小于100的自然数，且a3+23能被24整除，这样的a有多少个？

5．求除以13的余数。

6．有三堆棋子的个数分别为19，8，9．现进行如下操作：

每次从三堆中的任意两堆中分别取出1个棋子，然后把这2个棋子都加到另一堆上去．试问：

能否经过若干次这样的操作使得

（1）三堆的棋子数目分别为2，12，22；

（2）三堆棋子的数目均为12．

C类例题

例7（第20届IMO试题）数1978n与1978m的最末三位数相等，试求正整数m和n，使得n+m取最小值，这里

分析数1978n与1978m的最末三位数相等等价于1978n-m≡1（mod1000），寻找最小的n-m及m。

解由已知1000=8×125，所以

①

②

因，且（1978m，125）=1，则由②式知1978n-m≡1（mod125）③

又直接验证知，1978的各次方幂的个位数字是以8、4、2、6循环出现的，所以只有n－m为4的倍数时，③式才能成立，因而可令n－m=4k.由于.n+m=（n－m）+2m=4k+2m，因而只需确定出k和m的最小值.

先确定k的最小值：

因为19784=（79×25+3）4≡34≡1（mod5），19784≡34≡6（mod25）.故可令19784=5t+1，而5不整除t，从而0≡1978n-m－1=19784k－1=（5k+1）k－1≡+，显然，使上式成立的k的最小值为25.

再确定m的最小值：

因1978≡2（mod8），则由①式知，④

由于④式显然对m=1，2不成立，从而m的最小值为3.

故合于题设条件的n+m的最小值为106.

说明此例中我们用了这样一个结论：

1978的各次方幂的个位数字是以8，4，2，6循环出现，即，当r=1，2，3，4时，这种现象在数学上称为“模同期现象”.一般地，我们有如下定义：

整数列各项除以m（m≥2，m∈N*）后的余数组成数列.若是一个周期数列，则称是关于模m的周期数列，简称模m周期数列.满足（或（modm））的最小正整数T称为它的周期.

例8（第29届IMO预选题）设a是方程的最大正根，求证：

17可以整除[a1788]与[a1988].其中[x]表示不超过x的最大整数.

分析探求是本题的关键，而a的值无法准确计算得到。

所以本题通过韦达定理寻求了的递推形式。

证明根据如下符号表可知，若设三根依次为，

则

x

－1

－

1

3

f（x）符号

－

+

+

－

－

+

。

另一方面，由韦达定理知，

为了估计[]、[]，先一般考察[an]，为此定义：

直接计算可知：

又因

当时，

由此知，命题变为证明：

能被17整除.

现考察在模17的意义下的情况：

可见，在模17意义下，是16为周期的模周期数列，即由于

1788

故命题得证.

说明本题利用导数估计了根的分布，递推式的构造需要仔细体味。

情景再现

7．设三角形的三边长分别是整数且已知其中而表示不超过的最大整数.求这种三角形周长的最小值.

习题17

A

1．证明对于任何整数,能被7整除；

2．试判断能被3整除吗？

3．求14＋24＋34＋…＋20044的末位数。

4．试证：

对一切正整数n，能被8整除。

B

5．设是最初的几个质数的乘积，这里。

证明p-1和p+1都不是完全平方数。

6．设a，b，c，d是4个整数，证明：

差b－a，c－a，d－a，c－b，d－b，d－c的积能被12整除。

7．正整数n满足：

十进制表示下的末三位数为888，求满足条件的最小的n值。

8．在每张卡片上各写出11111到99999的五位数，然后把这些卡片按任意顺序排成一列，证明所得到的444445位数不可能是2的幂；

C

9．在1，2，3，…1989，…1994中最多可以取多少个数，使得所取的

数中任意3个数之和能被18整除。

10．给出一个数198********3…654321，它是由大到小依次写出自然数1985、1984、…、直到写出3、2、1后连接成一个数而成，现从其首位起，把首位数字乘以2加上第二位数字，把结果再乘以2后加上第三位数字，再把结果乘以2后加上第四位数字，…，这样一直算下去，直到个位数字为止，于是得到一个新的数，把新的数再按上述方法做一次，又得第二个数，…这样一直做下去，直到得到一个一位数为止，问得到的一位数是多少？

11．设a,b,c是三个互不相等的正整数，求证：

a3b－ab3，b3c－bc3,c3a－ca3三个数中，至少有一个数能被10整除．

12．连结正n边形的顶点，得到一个闭的n年折线形，证明：

当n为

偶数，则在连线中有两条平行线。

“情景再现”解答：

1．

2．解：

3＋5＋7＋5＋6=26，

2003≡1（mod11），26＋x≡1（mod11）x=8，即只要报8．

以后每次甲报k时，乙就报11－k即可．

3．将54个座位按逆时针由1开始编号：

1，2，3，……

如果满足要求的排法存在，则不妨设1和11是同一国的代表，从而11和21不是同一国的代表，故21和31是同一国家代表．进一步可以得出：

和是同一国家的代表（若和大于54，则取它们被54除的余数为号码的位置，比如61即等同于7）．

特别地，取时，261和271是同一国家的代表，然而

，．

即1和45是同一国家的代表，与1和11是同一国家的代表矛盾．命题得证．

4．a3+23=a3－1+24,∴a3－1≡0（mod24）,∴3|a3－1，8|a3－1．

由a≡0,1,2（mod3）得a3≡0,1,2（mod3）；

若a为偶数，则a3≡0（mod8）,若a为奇数，则a2≡1,故a3≡a（mod8）．

从而a≡1（mod24）;于是a=1，25，49，73，97，共有5个数．

5．1001≡0（mod13）

108≡1000≡－1（mod13）

106≡1（mod13）

10≡4（mod13）

102≡16≡10（mod6）

103≡102≡10（mod6）

10n≡10n-1≡…≡10≡4（mod6）

10n＝6k＋4

∴≡106k+4≡（106）k×104≡1k×104≡104≡3（mod13）

6．

（1）

．

（2）不可能完成．由于每次操作后，每堆棋子数目或者减1，或者加2，不妨写为

．

若被3除的余数均不相等，则操作后得到的三个数，，被3除的余数的变化为，，．也就是说，每次操作后不改变三个数被3除的余数互不相等这样一个事实．

由于一开始给的三个数被3除的余数各不相等，而所要求达到的结果被3除的余数都为0，故不能完成．

7．由题设可知,

于是

由于（3,2）=（3,5）=1,∴由①可知.

现在设是满足的最小正整数,则对于任意满足的正整数,我们有,即u整除v.事实上,若不整除,则由带余除法可知,存在非负整数及,使得,其中。

从而可以推出,而这显然与的定义矛盾,所以.注意到

，从而可以设,其中为正整数.

同理可由推出.故.

现在我们求满足的正整数.

因为,所以

即

或

即有,并代入该式得

即有.

即,其中为正整数,

故,s为正整数.

同理可以证得,为正整数.

由于,所以有.

这样一来,三角形的三个边为和.由于两边之差小于第三边,故,因此,当时三角形的周长最小,其值为（1000+501）+（500+501）+501=3003.

“习题”解答：

A

1．

都能被7整除；

2．

3．解：

记14＋24＋34＋…＋20044＝N，设N的末位数为a，则N≡a（mod10）

∴N4≡a4（mod10）

∵14≡1（mod10）　24≡6（mod10）　34≡1（mod10）　44≡6（mod10）

54≡5（mod10）　64≡6（mod10）　74≡1（mod10）　84≡6（mod10）　94≡1（mod10）

∴14＋24＋34＋…＋20044≡200×（14＋24＋34＋…＋104）＋14＋24＋34＋44≡14≡4（mod10）即末位数为4

4．证明：

若k为奇数，则或±3（mod8）,（mod8）

∴当k为奇数　（mod8）,∴（mod8）

若n为正奇数，

（mod8）

若n为正偶数，（mod8）

∴得证.

B

5．对任意（mod3）

所以或1（mod3）

而3︱p故p-1（mod3）

p-1不是完全平方数

又都是奇数，设＝2k+1.

则（mod4），而完全平方数0或1（mod4）,（mod4）

不是完全平方数。

6．考虑这4个数模4的结果，如果有某两个数对于模4同余，则这二数是4的倍数，如果这4个数对于模4没有两数同余，则这四数必两奇两偶，奇偶相同二数的差能被2整除，于是其积是4的倍数，即得。

再考虑这4个数模3的结果，由于任何整数模3后只能与0，1，2，这三个数同余，则必有二数对于模3同余，这二数的差能被3整除。

综上即得。

7．依题意，知（mod1000）故n的末位数字为2，设n=10k+2，

则分别有

即（mod25）

故25，所以

设，则

即，所以m=5r+3.

则n=500r+192

∴最小的n为192

8．

C

9．设a，b，c，d是取出来的数中任意四个，由a＋b＋c＝18n，a＋b＋d＝18m，18|（c－d），即取出的数对摸18的余数相同，设为k，

则a＋b＋c≡3k（mod18）

k＝0，6，12。

而1994＝18×110×14

最多有6，24，42，…1986或12，30，48，…1992共111个数满足。

10．解设所给数为A，则A被8除的余数与321被8除的余数相同，但321=3×100+2×10+1≡3×4+2×2+1（mod8），又设第一次运算得到的数为B，而B被8除的余数与（3×2+2）×2+1被8除的余数相同（A的千位以上的数字在运算过程中均乘以2n ，其中n≥3）。

即B被8除的余数与A被8除的余数相同。

对B的各位数字进行运算的结果记为C，同理可知，C被8除的余数与B被8除的余数相同，…，依此类推，知最后所得的一位数被8除的余数与A被8被的余数相同，即余1。

而此一位数由两个自然数相加而得，故不等于1，从而，该一位数为9。

11．证明a3b－ab3=ab（a+b）（a－b）；b3c－bc3=bc（b+c）（b－c）；c3a－ca3=ca（c+a）（c－a）．

⑴若a≡0（mod2）或b≡0（mod2），则ab（a+b）（a－b）≡0（mod2）；

若a≡1（mod2）且b≡1（mod2），则a+b≡0（mod2）且a－b≡0（mod2）

于是ab（a+b）（a－b）≡0（mod2）；总之，a3b－ab3≡0（mod2），

同理b3c－bc3≡0（mod2），c3a－ca3≡0（mod2）．

⑵若a≡0（mod5），则ab（a+b）（a－b）≡0（mod5）且ca（c+a）（c－a）≡0（mod5），

故可知，当a≡0，或b≡0，或c≡0（mod5）时，考察

a3b－ab3，b3c－bc3,c3a－ca3

这三个数中，至少有2个能被5整除．

当a0（mod5）且b0（mod5）且c0（mod5）时，

①若a≡b（mod5），则a－b≡0（mod5），于是ab（a+b）（a－b）≡0（mod5）．

同理若b≡c（mod5），则bc≡0（b+c）（b－c）（mod5）；

若c≡a（mod5），则ca（c+a）（c－a）≡0（mod5）．

②若ab，bc，ca，则取M={1，4}，N={2，3}两个集合．

由于a、b、c被5除的余数互不相等且只能是1，2，3，4中的某3个，故必存在两个数，它们被5除的的余数或同属于M，或同属于N，不妨设a、b这两个数被5除的余数属于同一集合，则a+b≡0（mod5）．

总之，a3b－ab3，b3c－bc3,c3a－ca3三个数中，至少有1个能被5整除．

综上可知，a3b－ab3，b3c－bc3,c3a－ca3三个数中，至少有一个数能被10整除．

12．依逆时针顺序将顶点标上0，1，…n－1，问题中的闭折线可用n个数的一个排列

A0，A1，A2，…An-1，An＝A0唯一地表示，且AiAi+1//AjAj+1

=Ai＋Ai+1≡Aj＋Aj+1（modn）

n为偶数，2不能整除（n－1）

模n的非负最小完全剩余系之和满足

0＋1＋…＋（n－1）＝

0（modn）

另一方面＝2≡2×

≡n（n－1）≡0（modn）

∴Ai＋Ai+1（i＝0，…，n－1）不能构成n的完全剩余后，必有i≠j，使Ai＋Ai+1≡Aj＋Aj+Aj+1（modn）得证。