高中数学竞赛教材讲义 第十七章 整数问题讲义

▁▂▃▄▅▆▇█▉▊▋▌精诚凝聚 =^_^= 成就梦想 ▁▂▃▄▅▆▇█▉▊▋▌

第十七章 整数问题

一、常用定义定理

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为整数,则n?p11p22?pkk,其中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,有ap≡a(modp).

9.若(a,m)=1,则a?(m)≡1(modm),?(m)称欧拉函数。

10.(欧拉函数值的计算公式)若m?pp?p,则?(m)=ma11a22akkaaa?(1?i?1k1). pi11.(孙子定理)设m1,m2,…,mk是k个两两互质的正整数,则同余组: x≡b1(modm1),x≡b2(modm2),…,x≡bk(modmk)有唯一解,

''x≡M1'M1b1+M2M2b2+…+MkMkbk(modM),

其中M=m1m2mk;Mi=

M,i=1,2,…,k;Mi'Mi≡1(modmi),i=1,2,…,k. mi二、方法与例题 1.奇偶分析法。

例1 有n个整数,它们的和为0,乘积为n,(n>1),求证:4|n。 [证明] 设这n个整数为a1,a2,…,an,则a1,a2,…,an=n, ①

▃ ▄ ▅ ▆ ▇ █ █ ■ ▓点亮心灯 ~~~///(^v^)\\\\\\~~~ 照亮人生 ▃ ▄ ▅ ▆ ▇ █ █ ■ ▓

▁▂▃▄▅▆▇█▉▊▋▌精诚凝聚 =^_^= 成就梦想 ▁▂▃▄▅▆▇█▉▊▋▌

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为其正整数解,不妨设x≤y≤z,则由题设z2|(x3+y3),所以z2≤x3+y3,

x3?y322332222

但x≤xz,y≤yz,因而z=nxy-≥nxy-(x+y),故x+y≥z≥[nxy-(x+y)],2z3

2

3

2

2

2

所以nxy≤2nxy(x+y)+x+y,所以nxy<2??2

4

4

22

3

3

?11?11?????nx3ny3。若x≥2,则4≤xy??nxy<2???11?11211≤3,矛盾。所以x=1,所以ny<,此式当且????2???333?ynnyny?xy?nx仅当y≤3时成立。又z2|(x3+y3),即z2|(1+y3),所以只有y=1,z=1或y=2,z=3,代入原方

程得n=1或3。

3.无穷递降法。

例3 确定并证明方程a2+b2+c2=a2b2的所有整数解。

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

a12?b12?c12?0,由a12b12≡1或0(mod4)知a1,b1,c1都是偶数(否则a12?b12?c12a12b12(mod4)),从而(a1b1c1,,)是 方程x2+y2+z2=2x2y2的一组整数解,222且不全为0,同理可知

a1b1c1ab1c1,,也都是偶数(1,2,2)为方程x2+y2+z2=24x2y2的解。2222222这一过程可以无限进行下去,另一方面a1,b1,c1为有限的整数,必存在k∈N,使2k>a1,2k>b1,2k>c1,从而

a1b1c1,k,k不是整数,矛盾。所以该方程仅有一组整数解k222(0,0,0).

4.特殊模法。

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

2[证明] 考虑形如n=72k+66,k∈N的正整数,若n?x12?x2???xs2,其中xi为奇

数,i=1,2,…,s且1≤s≤9。因为n≡2(mod8),又xi2≡1(mod8),所以只有s=2.所以

2,又因为xi2≡2或0(mod3),且3|n,所以3|x1且3|x2,所以9|n。但n?x12?x2▃ ▄ ▅ ▆ ▇ █ █ ■ ▓点亮心灯 ~~~///(^v^)\\\\\\~~~ 照亮人生 ▃ ▄ ▅ ▆ ▇ █ █ ■ ▓

▁▂▃▄▅▆▇█▉▊▋▌精诚凝聚 =^_^= 成就梦想 ▁▂▃▄▅▆▇█▉▊▋▌

n=72k+66≡3(mod9),矛盾。所以n不能表示成少于10个奇数的平方和,且这样的n有无穷多个。

5.最小数原理。

442

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

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

2222222因此,(x0,则x0=2ab,z0=a2+b2,其中(a,b)=1,a,b一奇一)?(y0)?z0?a2-b2,y022偶。假设a为偶数,b为奇数,那么x0?z0?0(mod4),而x0?a2?b2?3(mod4),矛2盾,所以a为奇数,b为偶数。于是,由x0?b2?a2得x0=p2-q2,b=2pq,a=p2+q2(这里2(p,q)=1,p>q>0,p,q为一奇一偶)。从而推得y0?2ab?4pq(p2?q2),因为p,q,p2+q2

两两互质,因此它们必须都是某整数的平方,即p=r2,q=s2,p2+q2=t2,从而r4+s4=t2,即(r,s,t)也是原方程的解,且有t

6.整除的应用。

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

mn?1解 (1)若n=1,则

2是整数,所以m-1=1或2,所以(m,n)=(2,1),(3,1). m?1n3?1n3?1?22(2)若m=1,则,所以n-1=1或2,所以??n2?n?1?n?1n?1n?1(m,n)=(1,2),(1,3).

m3n3?1?(m3n3?1)?m3(n3?1)m3?1(3)若m>1,n>1,因为是整数,所以也?mn?1mn?1mn?1是整数,所以m,n是对称的,不妨设m≥n,

n3?1n3?n?n?11ⅰ)若m=n,则2为整数,所以n=2,m=2. ??n?2n?1n?1n?1n3?1ⅱ)若m>n,因为n+1≡1(modn),mn-1≡-1(modn),所以≡-1(modn).

mn?13

n3?1n3?1n3?11??n?, 所以存在k∈N,使kn-1=,又kn-1=

mn?1n?1mn2?1n2?1n3?1n2?121?n?1?. 所以(k-1)n<1+,所以k=1,所以n=1=,所以m?mn?1n?1n?1n?1所以n-1=1或2,所以(m,n)=(5,3)或(5,2).

同理当m

▃ ▄ ▅ ▆ ▇ █ █ ■ ▓点亮心灯 ~~~///(^v^)\\\\\\~~~ 照亮人生 ▃ ▄ ▅ ▆ ▇ █ █ ■ ▓

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4