高中数学竞赛讲义十七

高中数学竞赛讲义十七

──整数问题

一、常用定义定理

1．整除：设a,b∈Z,a≠0，如果存在q∈Z使得b=aq，那么称b可被a整除，记作a|b，且称b是a的倍数,a是b的约数。b不能被a整除，记作a b.

2.带余数除法：设a,b是两个给定的整数，a≠0，那么，一定存在唯一一对整数q与r，满足b=aq+r,0?r<|a|，当r=0时a|b。

3．辗转相除法：设u0,u1是给定的两个整数，u1≠0，u1 u0,由2可得下面k+1个等式：u0=q0u1+u2,0

u1=q1u2+u3,0

uk-2=qk-2u1+uk-1+uk,0

4．由3可得：（1）uk+1=(u0,u1)；（2）d|u0且d|u1的充要条件是d|uk+1；（3）存在整数x

0,x1，使uk+1=x0u0+x1u1.

5．算术基本定理：若n>1且n为整数，则

，其中pj(j=1,2,…,k)是

质数（或称素数），且在不计次序的意义下，表示是唯一的。

6．同余：设m≠0,若m|(a-b)，即a-b=km，则称a与b模同m同余，记为a≡b(modm)，也称b是a对模m的剩余。

7．完全剩余系：一组数y1,y2,…,ys满足：对任意整数a有且仅有一个yj是a对模m的剩余，即a≡yj(modm)，则y1,y2,…,ys称为模m的完全剩余系。

p-1

8．Fermat小定理：若p为素数，p>a,(a,p)=1，则a≡1(modp)，且对任意整数a,有p

a≡a(modp).

9．若(a,m)=1，则

≡1(modm),

(m)称欧拉函数。

10．（欧拉函数值的计算公式）若，则(m)=

11．（孙子定理）设m1,m2,…,mk是k个两两互质的正整数，则同余组： x≡b1(modm1),x≡b2(modm2),…,x≡bk(modmk)有唯一解， x≡

M1b1+

M2b2+…+

Mkbk(modM)，

其中M=m1m2mk；=，i=1,2,…,k；≡1(modmi),i=1,2,…,k.

二、方法与例题 1．奇偶分析法。

例1 有n个整数，它们的和为0，乘积为n，（n>1），求证：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．不等分析法。

333222

例2 试求所有的正整数n，使方程x+y+z=nxyz有正整数解。

233233

解 设x,y,z为其正整数解，不妨设x?y?z，则由题设z|(x+y)，所以z?x+y，

但x?xz,y?yz，因而z=nxy-

323222

?nxy-(x+y)，故x+y?z?[nxy-(x+y)]，所

22332222

以nxy?2nxy(x+y)+x+y，所以nxy<

2442233

。若x?2，则4?

nxy<

2

3

?3，矛盾。所以x=1，所以ny<

3

2

3

，此式当且

仅当y?3时成立。又z|(x+y)，即z|(1+y)，所以只有y=1,z=1或y=2,z=3，代入原方程得n=1或3。

3．无穷递降法。

22222

例3 确定并证明方程a+b+c=ab的所有整数解。

解 首先(a,b,c)=(0,0,0)是方程的整数解，下证该方程只有这一组整数解。假设(a1,b1,c1)是方程的另一组整数解，且a1,b1,c1不全为0，不妨设a1?0,b1?0,c1?0且

，由

≡1或0(mod4)知a1,b1,c1都是偶数(否则

(mod4))，从而是 方程x+y+z=2xy的一组整数解，且不全为0，同理可知

22222

也都是偶数为方程x+y+z=2xy的解。这一过程可以无限进行下

222422

去，另一方面a1,b1,c1为有限的整数，必存在k∈N,使2>a1,2>b1,2>c1，从而是整数，矛盾。所以该方程仅有一组整数解(0,0,0).

4．特殊模法。

例4 证明：存在无穷多个正整数，它们不能表示成少于10个奇数的平方和。

[证明] 考虑形如n=72k+66,k∈N的正整数，若i=1,2,…,s且1?s?9。因为n≡2(mod8)，又又因为

kkk

不

，其中xi为奇数，

，

≡1(mod8)，所以只有s=2.所以

≡2或0(mod3)，且3|n，所以3|x1且3|x2，所以9|n。但n=72k+66≡3(mod9)，

矛盾。所以n不能表示成少于10个奇数的平方和，且这样的n有无穷多个。

5．最小数原理。

442

例5 证明：方程x+y=z没有正整数解。

[证明] 假设原方程有一组正整数解(x0,y0,z0)，并且z0是所有正整数解z中最小的。因此，

，则

a-b,

2

2

=2ab,z0=a+b，其中(a,b)=1,a,b一奇一偶。(mod4)，而

2

2

22

假设a为偶数，b为奇数，那么

所以a为奇数，b为偶数。于是，由

(mod4)，矛盾，

2

2

得x0=p-q,b=2pq,a=p+q（这里

，因为p,q,p+q

2

2

2

2

2

2

2

(p,q)=1,p>q>0,p,q为一奇一偶）。从而推得

两两互质，因此它们必须都是某整数的平方，即p=r,q=s,p+q=t，从而r4+s4=t2，即(r,s,t)

22222

也是原方程的解，且有t

6．整除的应用。

例6 求出所有的有序正整数数对(m,n)，使得是整数。

解 （1）若n=1,则是整数，所以m-1=1或2，所以(m,n)=(2,1),(3,1).

（2）若m=1,则(m,n)=(1,2),(1,3).

，所以n-1=1或2，所以

（3）若m>1，n>1，因为是整数，所以也

是整数，所以m,n是对称的，不妨设m?n，

ⅰ）若m=n，则为整数，所以n=2,m=2.

ⅱ）若m>n，因为n+1≡1(modn),mn-1≡-1(modn)，所以

3

≡-1(modn).

所以存在k∈N，使kn-1=,又kn-1=

所以(k-1)n<1+,所以k=1，所以n=1=,所以

所以n-1=1或2，所以(m,n)=(5,3)或(5,2). 同理当m

综上(m,n)=(1,2),(2,1),(1,3),(3,1),(2,2),(2,5),(5,2),(3,5),(5,3). 7．进位制的作用

例7 能否选择1983个不同的正整数都不大于10，且其中没有3个正整数是等差数列中的连续项？证明你的结论。

5

解 将前10个自然数都表示为三进制，在这些三进制数中只选取含数字0或1（而不含数字2）的数组成数集T，下证T中的数符合要求。

105115

（1）因为3<10<3,所以前10个自然数的三进制至多由11个数字组成，因而T中的

21011

元素个数共有1+2+2+…+2=2-1=2047>1983（个）。这是因为T中的k位数的个数相当于

k-1

用0，1这两个数在k-1个位置上可重复的全排列数（首位必须是1），即2,k=1,2,…,11.

2105

（2）T中最大的整数是1+3+3+…+3=88573<10。

（3）T中任意三个数不组成等差排列的三个连续项。否则，设x,y,z∈T,x+z=2y，则2y必只含0和2，从而x和z必定位位相同，进而x=y=z，这显然是矛盾的。

三、习题精选

2

1．试求所有正整数对(a,b)，使得(ab-a+b+1)|(ab+1).

2222

2．设a,b,c∈N+，且a+b-abc是不超过c+1的一个正整数，求证：a+b-abc是一个完全平方数。

22

3．确定所有的正整数数对(x,y)，使得x?y，且x+1是y的倍数，y+1是x的倍数。

n2

4．求所有的正整数n，使得存在正整数m,(2-1)|(m+9).

5．求证：存在一个具有如下性质的正整数的集合A，对于任何由无限多个素数组成的集合，存在k?2及正整数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且0?r?n，求最大正整数A，使得存在正整数n1,n2,…,n6，对任意正整数a?A，都有

=1，并证明你的结论。

8．设x是一个n位数，问：是否总存在非负整数y?9和z使得10z+10x+y是一个完全平方数？证明你的结论。

9．设a,b,c,d∈N+,且a>b>c>d,ac+bd=(b+d+a-c)(b+d-a+c)。证明：ab+cd不是素数。

n+1

5