山东省滨州双城教育数学竞赛讲义 第17章《整数问题》.doc

1、第十七章 整数问题一、常用定义定理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

2、且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（孙子定

3、理）设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。2不等分析法。例2 试求所有的正整数n，使方程x3+y3+z3=nx2y2z2有正整数解。3无穷递降法。例3 确定并证明方程a2+b2+c2=a2b2的所有整数解。4特殊模法。例4 证明：存在无穷多个正整数，它们不能表示成少于10个奇数的平方和。5最小数原

4、理。例5 证明：方程x4+y4=z2没有正整数解。6整除的应用。例6 求出所有的有序正整数数对(m,n)，使得是整数。7进位制的作用例7 能否选择1983个不同的正整数都不大于105，且其中没有3个正整数是等差数列中的连续项？证明你的结论。三、习题精选1试求所有正整数对(a,b)，使得(ab-a2+b+1)|(ab+1).2设a,b,cN+，且a2+b2-abc是不超过c+1的一个正整数，求证：a2+b2-abc是一个完全平方数。3确定所有的正整数数对(x,y)，使得xy，且x2+1是y的倍数，y2+1是x的倍数。4求所有的正整数n，使得存在正整数m,(2n-1)|(m2+9).5求证：存在一

5、个具有如下性质的正整数的集合A，对于任何由无限多个素数组成的集合，存在k2及正整数mA和nA，使得m和n均为S中k个不同元素的乘积。6求最小的正整数n(4)，满足从任意n个不同的整数中能选出四个不同的数a,b,c,d使20|(a+b-c-d).7.对于正整数a,n,定义Fn(a)=q+r，其中q,r为非负整数，a=qn+r且0rn，求最大正整数A，使得存在正整数n1,n2,n6，对任意正整数aA，都有=1，并证明你的结论。8设x是一个n位数，问：是否总存在非负整数y9和z使得10n+1z+10x+y是一个完全平方数？证明你的结论。9设a,b,c,dN+,且abcd,ac+bd=(b+d+a-c)(b+d-a+c)。证明：ab+cd不是素数。