赛题精讲
例1：数1978n与1978m的最末三位数相等，试求正整数m和n，使得n+m取最小值，这里n?m?1. （第20届IMO试题）
【解】由已知1978?1078(mod1000),而1000=8×125，所以 1978?1078(mo8d) ①
nmnm1978n?1078m(mod125) ②
因n?m?1，且（1978m，125）=1，则由②式知1978nm≡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≡1（mod25）.故可令19784=5t+1，
－
而5 t，从而0≡1978n
－m－1=19784k－1=（5k+1）k－1≡
k(k?1)?(5t)2 2+k?5t(mod125)，显然，使上式成立的k的最小值为25.
再确定m的最小值：因1978≡2（mod8），则由①式知，2?2(mod8) ④ 由于n?m?1,④式显然对m=1，2不成立，从而m的最小值为3.
故合于题设条件的n+m的最小值为106.
【评述】比例中我们用了这样一个结论：1978的各次方幂的个位数字是以8，4，2，6循环出现，即，当r=1，2，3，4时，1978义：
整数列?xn?各项除以m（m?2，m∈N*）后的余数an组成数列?an?.若?an?是一个周期数列，则称?xn?是关于模m的周期数列，简称模m周期数列.满足an?T?an（或an?T?xn （modm））的最小正整数T称为它的周期.
例如，（1）1978pnm?19784q?r?8,4,2,6(mod10).这种现象在数学上称为“模同期现象”.一般地，我们有如下定
?n?是模10周期数列，周期为4；（2）自然数列{n}是一个模m（m?2，m∈N*）周期数列，
周期为m；（3）任何一个整数等差数列都是一个模m（m?2，m∈N*）周期数列，周期为m.
例2：设a是方程x3?3x2?1?0的最大正根，求证：17可以整除[a1788]与[a1988].其中[x]表示不超过x的最大整数. （第29届IMO预选题）
【证明】根据如下符号表可知，若设三根依次为????a，则?1????
x f(x)符号
－1 － －11,???1, 221 21 2+ 1 － 23 － 3 + + 22?a,由于f(??)??2?3?(?3?2?2?1)??2?3?0,于是????,|?|??.
26
另一方面，由韦达定理知，
22?6a2?a3?2a3?a3????(???)?2???(3?a)??9??9??1?(8?a2)
aaa2222?a2?(22)2?8,??2??2?1.
为了估计[a1788]、[a1988]，先一般考察[an]，为此定义：
un??n??n?an.(n?0,1,2,?)
直接计算可知：u0?3,u1?2???a?3.u2??2??2?a2?9,以及un?3?3un?2?n(n?0). 又
因
0??n??n?1(?|?|??,即?n??n?0,又????3???2?22?1,当
n?2时，
?n??n?|?|n??n??2??2?1),则an?un?(?n??n)?un?1?[1?(?n??n)].
?[an]?un?1.(n?1,2,?)
由此知，命题变为证明：u1788?1和u1988?1能被17整除. 现考察?un?在模17的意义下的情况：
u0?3,u1?3,u2?9,u3?7,u4?1,u5?11,u6?9,u7?9,u8?16,u9?5,u10?6,u11?2,
u12?1,u13?14,u14?6,u15?0,u16?3,u17?3,u18?9,??
可见，在模17意义下，?un?是16为周期的模周期数列，即un?16?un(mod17).由于 1788?12(mod16),1988?4(mod16),故u1788?u12?1(mod17),u1988?u4?1(mod17),故
u1788?1?0,u1988?1?0(mod17).命题得证.
例3：求八个整数n1,n2,?,n8满足：对每个整数k（－1985 【解】令数集G?k|k?a1?a2?3?a3?32???an?1?3n,ai?{?1,0,1},i?1,2,?,n?1. ??3n?1?1记 G?1?3?3???3?显然 max H，mixG?1?3?32???3n??H. 22n且G中的元素个数有3n?1?2H?1个.又因G中任意两数之差的绝对值不超过2H，所以G中的数对模2H+1不同余.因此，G的元素恰好是模2H+1的一个绝对值最小的完系，于是，凡满足?H?k?H的任意整数都属于G，且可惟一地表示为：a1?a2?3?a3?32???an?1?3n形式. 当n=7时，H=3280>1985，而n=6时，H=1043<1985.故n1=1，n2=3，?，n8=37为所求. 例4：设n为正整数，整数k与n互质，且0 27 色中的一种，染法如下：（i）对M中每个i，i与n－i同色；（ii）对M中每个i，i≠k,i与|k－i|同色.求证：M中所有的数必为同色. （第26届IMO试题） 【证明】因(k,n)?1,又0，1，?n－1是模n的一个完全剩余系，所以0，k，2k，?，（n－1）k也是模n的一个完全剩余系.若设jk?rj(modn)(其中1?rj?n?1,j?1,2,?,n?1), 则M={r1,r2,?,rn?1}.下只需证rj?1与rj(1?j?n?2).因为，若如此，当r1的颜色确定后，M中所有都与r1同色. 由于(j?1)k?rj?1(modn),则rj?k?rj?1(modn)，因此， （1）若rj?k?n,则rj?1?rj?k，于是，由条件（i）知，k?rj?1?n?rj与n?(n?rj)?rj同色.又由条件（ii）知，k?rj?1与|k?rj?1?k|?rj?1同色，故rj?1与rj同色.综上所述可知，rj?1与rj同色.命题得证. 例5：设a和m都是正整数，a>1.证明：m|?(a?1). 【证明】实上，显然a与a?1互素，且a模a?1的阶是m，所以由模阶的性质③导出m|?(a?1). 例6：设p是奇素数，证明：2p－1的任一素因了具有形式2px?1,x是正整数. 【证明】设q是2p－1的任一素因子，则q≠2.设2模q的阶是k，则由2?1(modq)知k|p，故k=1或p（因p是素数，这是能确定阶k的主要因素）.显然k≠1，否则2?1(modq),这不可能，因此k=p. 现在由费马小定理2证毕. 例7：设m,a,b都是正整数，m>1，则m?1,m?1)?mabab(a,b)q?11pmmmm?1(modq)推出k|q?1,即p|q?1.因p、q都是奇数，故q－1=2px（x是个正整数）， ?1. (a,b)【证明】记d?(m?1,m?1).由于（a,b）|a及（a,b）|b，易知m?1|ma?1及 m(a,b)?1|mb?1，故m(a,b)?1|d，另一方面设m模d的阶是k，则由 ma?1(modd),mb?1(modd)推出，k|a及k|b，故k|（a，b）.因此m(a,b)?1(modd),即d|m(a,b)?1. 综合两方面可知，d?m(a,b)?1.证毕. 例8：设n，k是给定的整数，n>0，且k（n－1）是偶数.证明：存在x,y,使得(x,n)?(y,n)?1,是x?y?k(modn). 【证明】我们先证明，当n为素数幂p时结论成立.实际上，我们能证明，存在x,y，使 p xy，且x?y?k.如p=2，则条件表明k为偶数，可取x?1,y?k?1;如p?2,则x?1,y?k?1或x?1,y?k?2中有一对满足要求.一般情形下，设n?p11?prr是n的标准分解，上面已证明，对每个pi，均有整数xi，yi，使pi xiyi，且xi?yi?k(1,2,?,r).现在孙子定理表明，同余方程组 28 ????1x?x1(modp1),?,x?xr(modprar)有解x，同样 ?1y?y1(modp1),?,y?yr(modprar) 也有解y.现在易证x,y符合问题中的要求：因pi xiyi，故pi xy（i=1，?，r），于是（xy，n）=1.又 x?y?xi?yi?k(modpi?1)(i?1,?,r),故x?y?k(modn). 例9：设n为任意的正整数.证明：一定存在n个连续的正整数解，使其中任何一个都不是质数的整数幂. （第30届IMO试题） 【证明】取2n个两两不同的质数p1,p2,?,pn和q1,q2,?,qn.同余方程组x??i(modpiqi), i?1,2,?,n.由于p1q1,p2q2,?,pnqn两两互质，根据孙子定理必有解，取为正整数N，则n个连续正整数N+1， N+2，?，N+n都至少含有两个不同的质因数，因而它们中的任一个都不是质数的整数幂.证毕. . 、 数论素有“数学皇后”的美称。由于其形式简单，意义明确，所用知识不多而又富于技巧性，千姿百态，灵活多样。有人曾说：“用以发现数学天才，在初等数学中再也没有比数论更好的课程了。”因此在理念的国内外数学竞赛中，几乎都离不开数论问题，使之成为竞赛数学的一大重要内容。 例1 证明无穷数列10001，100010001，??中没有素数。 证明：设an?100010001?1，则an?1?10?10???10???????n个1484(n?1)104n?1=4 10?1108k?1(108)k?1108?1??当n为偶数，设n?2k，an=4 10?1108?1104?1所以an为合数。当n为奇数，设n?2k+1， （2k+1）2k?12k?1104?1（102）?1（102）?1an==?所以an为合数。 104?1102?1102?1评析：对n分奇偶，分情况讨论，问题变得清晰易证。同时注意，若n为奇数时，xn?yn可分解因式。 例2 证明对任意整数n?1，n4?4n不是素数。 证明：当n为偶数时，n4?4n为偶数，所以n4?4n为合数； (2k)4 当n为奇数，设n?2k?1，则n4?4n=n4?42k?1?n4?4?=n4?4n2(2k)2?4?(2k)4?4n2(2k)2 ?[n2?2(2k)2]2?4n2(2k)2 ?[n2?2(2k)2?2n?2k]?[n2?2(2k)2?2n?2k]所以n4?4n为合数。 29 例3 设正整数a,b,c,d满足ab?cd。证明：a?b?c?d不是素数。 证明：由于ab?cd，则设 a?pu,c?pvd?qu,b?qvadu??，其中(u,v)?1，则 cbv故a?b?c?d=pu?qv?pv?qu?p(u?v)?q(u?v)?(p?q)(u?v)所以为合数。 ad?，不妨设gcd(a,c)?s,gcd(d,b)?t,则 cba1sd1tad，所以1?1，即a1b1=c1d1 ?c1sb1tc1b1评析：此题中采用方法可扩展如下：若 a?a1s,c?c1sb?d1t,b?b1t，且gcd(a1,c1)?gcd(d1,b1)?1由于 所以a1d1c1,gcd(a1,c1)?1，故a1d1。同理可证d1a1，所以a1=d1同理可得c1=b1例4 证明：若正整数a,b满足2a2?a?3b2?b，则a?b和2a?2b?1都是完全平方数。 证明： 因2a2?2b2?a?b?b2，即(a?b)(2a?2b?1)?b2 故只需证a?b和2a?2b?1互质。 设gcd(a?b,2a?2b?1)?d,即证d?1 则da?b,d2a?2b?1 由于d2b2，所以db，又da?b，则da。所以d1，故d?1得证。 故a?b和2a?2b?1互质，所以a?b和2a?2b?1都是完全平方数。 评析：有时，适当的因式分解可以使问题简化，以证得结论。 例5 一个正整数，加上100为一个完全平方数，若加上168则为另一个完全平方数，求这个数。 解：设这个数为x，则 2??x?100?a 其中a,b?N（注：限定正的可减少讨论）。 ?2??x?168?b故(b?a)(b?a)?22?17，从而b?a与b?a则等于把22?17拆开的因数1、2、4、17、34、68.这样就有六种情形。又由于b?a?b?a，且b?a与b?a同奇偶性，故 ?b?a?2 ??b?a?34所以b?18,a?16。则x?162?100?156。 例6 求方程x4?y4?z4?2x2y2?2x2z2?2y2z2?24的全部整数解。 解：对原方程进行变形、因式分解 30