数学竞赛中的数论问题题型全(6)

赛题精讲

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

【解】由已知1978nn?1078m(mod1000),而1000=8×125，所以

m8) ① 1978?1078(mod1978n?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记 2nG?1?3?3???3?显然 max H，mixG?1?3?3???3??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).

m【证明】实上，显然a与a?1互素，且a模a?1的阶是m，所以由模阶的性质③导出m|?(a?1).

mmm例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?1p1?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+ …… 此处隐藏：3890字，全部文档内容请下载后查看。喜欢就下载吧 ……