2019-2020年高中数学竞赛教材讲义 第十七章 整数问题.doc

2019-2020年高中数学竞赛教材讲义 第十七章 整数问题一、常用定义定理1整除：设a,bZ,a0，如果存在qZ使得b=aq，那么称b可被a整除，记作a|b，且称b是a的倍数,a是b的约数。b不能被a整除，记作a b.2.带余数除法：设a,b是两个给定的整数，a0，那么，一定存在唯一一对整数q与r，满足b=aq+r,0r|a|，当r=0时a|b。3辗转相除法：设u0,u1是给定的两个整数，u10，u1 u0,由2可得下面k+1个等式：u0=q0u1+u2,0u2|u1|；u1=q1u2+u3,0u3u2；u2=q2u3+u4,0u4u3；uk-2=qk-2u1+uk-1+uk,0ukuk-1；uk-1=qk-1uk+1,0uk+11且n为整数，则，其中pj(j=1,2,k)是质数（或称素数），且在不计次序的意义下，表示是唯一的。6同余：设m0,若m|(a-b)，即a-b=km，则称a与b模同m同余，记为ab(modm)，也称b是a对模m的剩余。7完全剩余系：一组数y1,y2,ys满足：对任意整数a有且仅有一个yj是a对模m的剩余，即ayj(modm)，则y1,y2,ys称为模m的完全剩余系。8Fermat小定理：若p为素数，pa,(a,p)=1，则ap-11(modp)，且对任意整数a,有apa(modp).9若(a,m)=1，则1(modm),(m)称欧拉函数。10（欧拉函数值的计算公式）若，则(m)=11（孙子定理）设m1,m2,mk是k个两两互质的正整数，则同余组：xb1(modm1),xb2(modm2),xbk(modmk)有唯一解，xM1b1+M2b2+Mkbk(modM)，其中M=m1m2mk；=，i=1,2,k；1(modmi),i=1,2,k.二、方法与例题1奇偶分析法。例1 有n个整数，它们的和为0，乘积为n，（n1），求证：4|n。证明 设这n个整数为a1,a2,an，则a1,a2,an=n， a1+a2+an=0。 首先n为偶数，否则a1,a2,an均为奇数，奇数个奇数的和应为奇数且不为0，与矛盾，所以n为偶数。所以a1,a2,an中必有偶数，如果a1,a2,an中仅有一个偶数，则a1,a2,an中还有奇数个奇数，从而a1+a2+an也为奇数与矛盾，所以a1,a2,an中必有至少2个偶数。所以4|n.2不等分析法。例2 试求所有的正整数n，使方程x3+y3+z3=nx2y2z2有正整数解。解 设x,y,z为其正整数解，不妨设xyz，则由题设z2|(x3+y3)，所以z2x3+y3，但x3xz2,y3yz2，因而z=nx2y2-nx2y2-(x+y)，故x3+y3z2nx2y2-(x+y)2，所以n2x4y42nx2y2(x+y)+x3+y3，所以nxy。若x2，则4nxy3，矛盾。所以x=1，所以nya1,2kb1,2kc1，从而不是整数，矛盾。所以该方程仅有一组整数解(0,0,0).4特殊模法。例4 证明：存在无穷多个正整数，它们不能表示成少于10个奇数的平方和。证明 考虑形如n=72k+66,kN的正整数，若，其中xi为奇数，i=1,2,s且1s9。因为n2(mod8)，又1(mod8)，所以只有s=2.所以，又因为2或0(mod3)，且3|n，所以3|x1且3|x2，所以9|n。但n=72k+663(mod9)，矛盾。所以n不能表示成少于10个奇数的平方和，且这样的n有无穷多个。5最小数原理。例5 证明：方程x4+y4=z2没有正整数解。证明 假设原方程有一组正整数解(x0,y0,z0)，并且z0是所有正整数解z中最小的。因此，则a2-b2,=2ab,z0=a2+b2，其中(a,b)=1,a,b一奇一偶。假设a为偶数，b为奇数，那么(mod4)，而(mod4)，矛盾，所以a为奇数，b为偶数。于是，由得x0=p2-q2,b=2pq,a=p2+q2（这里(p,q)=1,pq0,p,q为一奇一偶）。从而推得，因为p,q,p2+q2两两互质，因此它们必须都是某整数的平方，即p=r2,q=s2,p2+q2=t2，从而r4+s4=t2，即(r,s,t)也是原方程的解，且有tt2=p2+q2=a1，n1，因为是整数，所以也是整数，所以m,n是对称的，不妨设mn，）若m=n，则为整数，所以n=2,m=2.）若mn，因为n3+11(modn),mn-1-1(modn)，所以-1(modn).所以存在kN，使kn-1=,又kn-1=所以(k-1)n1+,所以k=1，所以n=1=,所以所以n-1=1或2，所以(m,n)=(5,3)或(5,2).同理当mn时，有(m,n)=(2,5),(3,5).综上(m,n)=(1,2),(2,1),(1,3),(3,1),(2,2),(2,5),(5,2),(3,5),(5,3).7进位制的作用例7 能否选择1983个不同的正整数都不大于105，且其中没有3个正整数是等差数列中的连续项？证明你的结论。解 将前105个自然数都表示为三进制，在这些三进制数中只选取含数字0或1（而不含数字2）的数组成数集T，下证T中的数符合要求。（1）因为3101051983（个）。这是因为T中的k位数的个数相当于用0，1这两个数在k-1个位置上可重复的全排列数（首位必须是1），即2k-1,k=1,2,11.（2）T中最大的整数是1+3+32+310=88573bcd,ac+bd=(b+d+a-c)(b+d-a+c)。证明：ab+cd不是素数。