高中数学竞赛教案讲义整数问题

1、高 中 数 学 竞 赛 教 案 讲 义 ( 1 7 ) 整 数 问题 ( 共 3 页 )-本页仅作为文档封面，使用时请直接删除即可- -内页可以根据需求调整合适字体及大小- - 2 - 第十七章整数问题一、常用定义定理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是给定的两个整数， u1

2、0，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 为整数，则kakaapppn2121，其中 pj(j=1,2, ,k)是质数（或称素数），且在不计次序的意义下，表示是唯一的。6同余：设 m 0, 若 m|(a-b) ，即 a-b=km，则称 a 与 b 模同 m同余，记为 ab(modm) ，也称 b 是 a 对模 m的剩余。7完全剩余系：一组数y1,y2, ,ys满足：对任意整数a

3、有且仅有一个 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 ，则)(ma1(modm),(m)称欧拉函数。- 3 - 10（欧拉函数值的计算公式）若kakaapppm2121，则(m)=. )11(1kiipm11（孙子定理）设m1,m2, ,mk是 k 个两两互质的正整数，则同余组：xb1(modm1),x b2(modm2), ,x bk(modmk)有唯一解，x1m m1b1+

4、2m m2b2+ +kmmkbk(modm) ，其中 m=m1m2mk；im=imm，i=1,2, ,k ；iimm1(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 个奇数的平方和。- 4 - 5最小数原理。例 5 证明：方程 x4+y4=z2没有正整数解。6整

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

6、+9). 5求证：存在一个具有如下性质的正整数的集合a，对于任何由无限多个素数组成的集合，存在 k2 及正整数 m a和 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 且 0r n，求最大正整数 a，使得存在正整数 n1,n2, ,n6，对任意正整数aa，都有)(123456affffffnnnnnn=1，并证明你的结论。8设 x 是一个 n 位数，问：是否总存在非负整数y9 和 z