高中数学联赛数论

第一章数论专题

我们把未知数的个数多于方程的个数,且其解受到某种限制的方程,叫做不定方程.通常主要研

究不定方程的正整数解、整数解、有理数解等.

不定方程问题的常见类型是：

（1）求不定方程的解；

（2）判定不定方程是否有解；

（3）确定不定方程解的数量（有限还是无限）.

不定方程问题的常用解法是：

（1）代数分析与恒等变形法，如因式分解、配方、换元等；

（2）估计范围法，利用不等式放缩等方法，确定出方程中某些变量的取值范围,进而求整解；

（3）同余法，即恰当选取模m,对方程两边做同余分析，以缩小变量的范围或发现性质，从而得

出整解或判定无解；

（4）构造法，构造出符合要求的特解，或构造一个求解的递推式，证明方程有无穷多解；

（5）无穷递降法，无穷递降法是一种用反证法表现的特殊形式的归纳法，由Fermat创立并运用

它证明了方程x'+y'z"没有非零整解.从此,无穷递降作为一种重要的数学思想方法广为流传应用，并

在平面几何、图论及组合中经常用到它.

引例：求所有正整数对（x,y）满足x'=y?

手写板图示0101-01

不定方程

例xy=丫*一丫正整数对&,y）

解：显然（1，1）是解x云y

若x=y=l

若x>声21<哮）y=yX-2y

x>2y且y|x^=ky（k二3）

ky=y（k-2）y一

k-2

易证：k，5时『一2>：2>fc

手写板图示0101-02

不定方程

例x，=丫*一丫正整数对&,y）

解：显然（1,1）是解X>y

若x=y=l

若x>声2lV（J<=yX-2y

x>2y且y|xi^x=ky（k三3）

Iy—&-2）y.[—k—2

kz-y丁・・k-y

易证：会5时yk-2三2k—A

当k=3时（9,3）

当k=4时（8,2）

综上（1,1）……

1.二元一次不定方程

定义1形如ax+by=c（a,b,ceZ,a,b不同时为0）的方程，称为二元一次不定方程.

定理1不定方程ax+by=c有整数解的充要条件是（a,b）|c.

定理2设（x°,y。）是不定方程ax+by=c的一组整解，则此方程的一切整数解为（x,y）

ba

x0+------£,y°—------1

(a,5)(a,b))，其中tGZ.当(a,b)=1时,(x,y)=(xo+bt,yo-at).

手写板图示0101-03

不定方程

1.二元一次不定方程ax+by=c

有解<?,■（a,b）|c

定理：特解（x0,y0）

b

X=XQ+

(a,b)

a

y=y。­

(a,b)

手写板图示0101-04

例7x+4y=100

解・x0=-100(7.4)=1

yo=2OO

—100+4t

则(t£z)

200-7t

100—4y=14+#

7

=12rx=12+4t

y=4-7t

例1求不定方程3A+2T+8Z=40的正整数解。

手写板图示0101-05

例1.求3x+2y+8z=40正整数解

解：3x=2(20—y—4z)

••.x为偶数x,y,zGN+

8z<40z<5

z=l3x+2y=32

z=2

z=3

z=4

例2足球比赛的计分规则是：胜一场得3分,平一场得1分，负一场得0分。那么，一个球队

打14场球积分19分的情况共有多少种.

手写板图示0101-06

例2.

x+y+z=14

3x+y=19

2x—z=54种

例3公元五世纪末，我国数学家张丘建在他的名著《算经》里提出一个世界数学史上著名的“百

鸡问题”：“鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问鸡翁、母、雏

各几何？”。

手写板图示010L07

例13.x+y+z=100

5x+3y+-5■—100

J

7x+4y=1004种

例4时钟的刻度盘（写有数字1,2,…，12的圆盘），以其中心为轴，固定在教室的黑板上，刻

度盘可以绕轴转过30°的整数倍的任意角度。起初，在黑板上靠近刻度盘上的数字旁边的地方写

上“0”，然后转动刻度盘若干次，每次转动停止后，都将刻度盘上的数加到靠近它旁边的黑板上所

写的数字，这样是否可以做到：

(1)黑板上所写的数都是1984?

(2)黑板上所写的数除了一个之外，其余所写的数都是1984?

(3)黑板上所写的数除了两个之外，其余所写的数都是1984?

O手写板图示010L09,

⑵不可以

刻度盘上12、1、2.......10处为1984

逆时针转30°-j次数XjG=l、2……12)

r叼+2血+3»：3+…+11町[+12xi2=1984①

2xt+3X2+4X3H------F12x1i+x12=1984②

3XI+4X2+5X3+I+X[[+2X[2=1984③

10町+IIX2+12X3+…+8X[[+%[2=1984⑩

111町+12交+町+…+9X[[+10x12=1984⑪

。手写板图示0101-10一

^X14-X2+X3H------Fxu-llx12=0

==

Isq+xz+xsH------Fx10-llxn+x120

,Xi+x2—11X3+X4"!-------FX12=0

xt=79x3—1984^0

1x2=1984—77x3^0

19841984

WX3W

7977

25.1......WX3W25.8…”

不存在X3GN+无解

©手写板图示0101-11

町=78x+X3—1984

｛4

=

«21984—75x4—2X3

75叼+2叼W1984

・・、・上1984

・又3三0・・W和26.4

75

••x4W26

X[=44,x3=0,X4=X5=.........x12=26

X2=34可能

2.勾股数定理

定义2形如的方程叫做勾股数方程，并称满足(x,y)=1的解为方程的基本解.

引理给定正整数n,且n》2,则不定方程uv=w"①，适合w>0,u〉0,v>0,(u,v)=1的一切正整数

解为：u=a",v=b",w=ab,其中a>0,b>0,(a,b)=1②.

手写板图示0102-01

不定方程

1.二元一次不定方程

2.勾股数不定方程

x2+y=z2(x,y)=l基本解.

弓I理:uv=wnw>0,u>0,(uv)=1

一切正整数解；u=an,v=bnw=ab

其中a>0,b>0(ab)=1

分析:设(u,v,w)为方程uv=w11一个解.

au=a=ui,v=b11二(a>0,b>0,.中不含有n次因子)

an|wn,bn|wn...a|w,b|w(uqvi)=l

(u,v)=1(a11»b11)=1(a,b)=lab|w^w=abW[

・・・5V[=w,若wfWl存在质数P符合P,

...P叫U1V1=wj矛盾，

W『=l/.UjV!=1/.U[=1,V1=1

h2+22+-+w2

例1求最小的正整数n(n22)，使得Vn为整数.

O手写板图示0102-02

例1.严土2午工!,(n+l)(2n+lT

-x

6

那由2=(n+l)(2n+l)知n=+1(mod6)

若6|n+l,设n=6m—1得x2=1)(m,12m—1)=1

.0.口12m—1完全平方数12m-1=3(mod4)矛盾

(2k)2—4k2—0(mod4)

(2k+l)2=4k2+4k+l—1(mod4)

手写板图示0102-03

例1.八2+229±j(n+1)(2n+1)

6

那四2(n+l)(2n+l)知n三±l(mod6)

若6|n+l,设n=6m—1得x2=m(12jn—1)'''(m,12m—1)=1

/-m^D12m—1完全平方数12m—1=3(mod4)矛盾

若61n—1,设n=6m+1得x2=(3m+1)(4m+1)(3m+l,4m+1)=1

设3m+l=v2,4m+l=u2消m得4V2—3u2=1

当11=v=1时，/.n=l不合题意

9手写板图示0102-04

例i./E2flz(n+1)(2n+1)

6

那多2(n+1)(2n+1)知n=±l(mod6)

若6|n+l,设n=6m—1得x2=1)(m,12m-1)=1

.0.血112m—1完全平方数12m-1=3(mod4)矛盾

若61n—L设n=6m+1得x2=(3m+1)(4m+1)(3m+l,4m+1)=1

设3m+l=«,4m+1=u2消m得4V2—3=1

当u=v=1时，「♦n=1不合题意

v=13,u=15,m=56n=337

最小

定理方程x?+y2=z?③适合条件x>0,y>0,(x,y)=1,且2|x④的一切正整数

为:x=2ab,y=a2-b2,z=a2+b2,其中a>b>0,(a,b)=1,且a,b一奇一偶⑤.

12处,一叫（/步上2ab、

推论单位圆上一切有理点为〔一。2+占“一。2+/J及+小2+/1其中a,b不全为

零，“士”号可任取.

手写板图示0102-05

定理:方程x2+y-z2(x>0,y>0,(x,y)=l,且2|x)

一切解：x=2ab,y=a2~b2，z=a2+b2

(a>b>0,(a,b)=1a,b一奇一偶)

证明:2|x,21y

设(x,y)=d,x2+y2=z2,d|z=a2+b2

222

d|2a2,d|2b2.•・d|2(a2,b)d|y=a-b

*.*(a,b)=1d=l^od=2y为奇数，d|yd=1

手写板图示0102-06

引理:uv=wnw>0,u>0,v>0(uv)=1

一切正整数解；u=an,v=bnw=ab

其中a>0,b>0(ab)=1

定理:方程好+y2=z2(x>0,y>0,0y)=1,且2|x)

一切解：x=2ab,y=>2-b2,z=四+jj2

(a>b>0,(a,b)=1a,b一奇一偶)

证明：2|x,2jy

一方面设(x,y)=d,x2+y2=z2,d|z=a2+b2

「・d|2a2,d|2b2"""d|2(a2>b2)d|y=a2—b2

,「(a,b)=1d=l或d=2.y为奇数，d|yd=l

另一方面：(x,y,z)为任意解.z|x,(x,y)=ly，z奇数

2=2^Q,y)『(字』

由引理知：三吆=a2b2=a•b(a>b>0,(a,b)=l)

22，

手写板图示0102-07

壹2+3『

(nx)2+(my)2=(mn)2

nx=2ab

my=a2—b2

mn=a2+b2

xy=(2aba2—b2v

(飞，五)一,齐R，苕声

例2已知x"yn二k无正整数解.求证:方程X，y电z2也无正整数解.

手写板图示0103-01

例2.xn+yn=*无正整数解,x2n+y2n=/也无正整数解。

证明:若不然,设Z为解中最小者，」.(x,y)=l

由勾股数定理x“=2uv,^=U2—v2=(u+v)(U—v)(u,v)=l

u,v-奇一偶(u+v,u—v)=1,(u+v,2V)=1

由引理：u+v=anu—v=bn

不妨设v为偶数，2uv=xn(u,2v)=2V=2^Z^

bn+cn=a”即(b,5a)为方程xN-y-zn一组解

矛盾。

例3求方程2、+3'=z2的所有整数解(及y,z).

手写板图示0103-02

Xy

2+3=Z2

（0,1,土2））

（3,0,±3）＞6组

（4,2,±5）J

手写板图示0103-03

解：设（x,y,z）是方程2*+3丫=%2一组整数解.

①若x<0或yVO0<2X0<3y0<2X+3y<l

z无整数解

②若（x,y,z）为解（x,%—z）为解只需z>0

③当x=0时，l+3y=z23y=（z—1）（z+1）

.:3是素数{:fl二:$t<s5.s+t=y

3^-3=23t（3S-t-1）=2：3+W2/.3t=l

t=0,s=l（0,1,2）

④当y=0时，------

⑤当x和茜B是正整数时，先证X,洞为偶数.

假设X奇数，设x=2p+l（p为非负整数）22p+1+3y=z2

2（3+l）P+3y=z2

pp

（3+1）=1（mod3）2（3+1）+3v=2（mod3）

手写板图示0103-04

解：设（x,y,z）是方程2X+3y=Z*2*—组整数解.

①若xV0或yVO0<2X^-10<3y^4

JJ

0<2X+3y<lZ无整数解

②若（x,y,z）为解（x,y,—z）为解只需z>0

③当x=0时，A-3y=Z2/.3^=（z—1）（z+1）

•••3是素数JZ-1=\t〈s且s+t=y

lz+l=3S

/.3-3=231（3$—t-i）=2V3^2

3t=1t=0,s=l（0,1,2）

④当y=0时，

⑤当x和y«B是正整数时，先辿洞为偶数.

设x=2py=2q22P+32，^=z232Q=（Z-2P）-（Z+2P）

_P_t

Jz23t〈s且t+s=2q

tz+2^=3S

2p+1=3t（3S-1）t=0z=2P+l

手写板图示0103-05

解：设（x,y,z）是方程2X+3y=z2一组整数解.

若2“=1,i+2P-3q=l2P=3q不可能

2U=2u=l2P=3q+l

k

若p是奇数，记p=2k+l2*（3+1）=2（mod3）

/.p是偶数，记p=2k3口+1三l（mod3）矛盾.

22k=3Q+l（2k）2—l=3q

2k—1=1k=lp=2q=l

/.x=4,y=2,z=5

3.沛尔（pell）方程

定义3通常pell方程指以下四个不定方程：x2-dy2=±l,±4,其中x,y《Z,d€N,,且d不

是平方数。

如果pell方程的正整数解（x,y）中，使得x+Jfy最小的正整数解为（x„y,）,则称（x„

y.）为方程的最小解。

手写板图示0104-01

沛尔方程（Pell）

X2-dy2=±1>X2-dy2=±4

x,yGz,dGN+用E完全平方数

最小解使得x+/1y最小正整数解（x-yj

定理1设dGN*,d不是平方数，方程（-dyJl的最小解为（xi,y。，则

~（X1+超了j+（X1-应为）"]

Xn-2，

限1+日为）"一（X[一直力）"]

yn=2Va,n=l,2,…。

给出方程x2-dy2=l的全部正整数解.称Xi+J7yi为方程x2-dy2=l的基本解。

手写板图示0104-02

定理1X?—dy?=]基本解4+n';/]

1nn

rxn=y[(X[+/Typ+(Xj-ZdYi)]

①Inn

lyn=^[(X]+/Typ-(Xj-ZdYi)]

②xn+yn/a=(Xi+yiyy)n

fxn+1=x1xn+dylyn

③<

^n+l—乂[丫4+y]Xn

Xx

(n+1—2X]Xn—n-i

④

lyn+1=2Xlyn-yn-i

定理2设方程x'-dy'T的正整数解(x,y)中，使得x+J『y最小的解为(x”外)，则

(Xl+日力+('1-也了1)“，

Xn—2，

,n=l,2,•

给出方程x2-dy2=-l的全部正整数解。

手写板图示0104-03

定理2：X2—dy2=-1（无解）

12n-12n-1

rXn=I［（Xj+ZT力）+（X［_/y%）］

］12n-12n—1

（Vn=^^［冈+石力）—（Xj—jyyj）］

例1设正整数d无平方因子，xo+J7y。为方程x2-dy2=l的基本解.求该方程的正整数解（x,y）,

使得X的所有素因子整除Xoo

定理3（1）当a为非零整数时，方程x?-a2y』只有平凡解（±1,0）；方程仅当a=±1

时有整数解（0,±1）»

（2）存在无穷多个非平方数d>0,使方程x2-dy2=T无整解。

4.费尔马大定理

不定方程x"+y"=z"（正整数nN3）无正整数解.

费尔马大定理,是困扰人们近四百年的著名世界难题，已于1994年被普林斯顿大学教授A.Wiles

攻克。

手写板图示0104-04

分析：J—a2y2=（x+犯）&—ay）=1

x+ay=x-ay=l或一1

x=±ly=0

例2证明：存在无数个正整数〃，使得［用为完全平方数。

手写板图示0104-05

22

例2.x-2y=-i易知（1,1）为方程一组解

方程有无数解任取（u,v）为一蛆解

2222

U-2V=-12V=U+1/2v=Ju2_）,1

u2</Iuv=uJ.+i=Ju4+u2<54+21?+1=u2+l

［/fuv］=u2为完全平方数

取n=uv证毕

例3试找出最大的CW点,使得对任意正整数77,都有｛〃｝》.（｛耳=方［切，其中［切表示不超过

X的最大整数）

手写板图示0104-06

]

最大CER+VnEN+st{/5"n!5：

解：所求最大正数为c=^=

一方面VnGN+,记{%n}=8,[/Tn]=a

贝IJ：9=/5~n—a得（店11）—2/yn8+B2=Q

ooo・

2/s'n0—9=5n—a5：1，2店n8>l-

«■-r・

手写板图示0104-07,

最大CGR+VnGN+st{/Fn}^

解：所求最大正数为c=^=

一方面VnEN+,记{店n}=8,[JTn]=a

则：9=/5-n—a得（yyn）2—2/5-n0+02=a2

275-n9-82=5n2—a2>lS/s_nQ>10>

另一方面考虑Pell方程x2—5y2=—1

有最小解（X],%）=（2,1）

n

x

rn+/5y=（^+JsYi），x：2-5y：2=（x2「5y；9）n=（-1）n

令:n

,,（X2n+1尸2n+l）（n£N+）也为Pell方程（*）正整数解

limX2n+1=+°°

n—>+oo

0手写板图示0104-08

+

最大CERVnEN+st{后日手5=>[f^n]■n>c

解：所求最大正数为c=9羡？

{石了211+1}=后y2n+l—X2n+1=JX2n+l+1—X2n+1

222

(X2n+1<后y2n+l<^Zn+i+l))

r-2---------AL+l-1-1

{石丫2「+1}Fn+l=UX2n+l+1-X2n+1)-----尸—

J5

_______超n+1+1________

代(/¥n+l+1+X2n+1)

lim{­/Vy2n+lJ，y2n+l_1

n—+oo一幅

]

••cWVT故“

手写板图示0104-09

+

最大CERVnGN+st{/Tn}>卷=>{/Tn}-n>c

叵Q

解：所求最大正数为c=S^

20.236

10

lim

n—»+oo

x£+l+1

y2n+l}'y2n+l=(/X2n+1+1-X2n+1卜

/x£+i+l

型同币

nW、{兀丫24+1}叫/1=1叱

n>十8n—>+oo用(i+_______2后

不定方程的解法

1.因式分解法

将方程的一端化为常数，做因数分解，另一端含未知数的代数式因式分解，再由各因式的取值

分解为若干方程组进行求解。

例1求方程2x2+5y2=ll(xy-11)的正整数解。

手写板图示0105-01

二不定方程解法

1.因式分解法：

例12x2+5y2=11(xy-11)

分析：2x+5y2—llxy=-121

一一，一—_~~~一一~~■一~~~~_―

(2x—y)(x-5y)=-121

c2x-y=-121,-1,1,

5y=1,121,-121

仅有广一解皿27)

<X—5y=—121

例2求方程x'-y工/的正整数解。其中y为素数，且3和y都不是z的约数。

Q手写板图示0105-02

例2X3—y3=z23y2=2(2x+y)+l

分析：(x—y)(x2+xy+y2)=z2—4u+6y+l

22

(X—y,X+xy+y)=1=3u+6y+(u+l)

22

rx-y=uu+l=0(mod3)

Ix2+xy+y2=v2

u2=0或1(mod?)矛盾

(2x+y)24-3y2=4v2

相减y2—3=4u2+6y

22o

4v—(2x+y)=3yz2o

(y—3)—4u=12

(xJy,z)=(8,7,13)

例3求方程xJ-5xy+6y2-3x+5y-25=0整数解。

手写板图示0105-03

例3(X—2y+1)(x—3y~4)=21

(—50,—25)

(28,15)

(4,-1)

(—26,—9)

(-16,-9)

(-6,-1)

(50,15)

(—72,—25)

2.配方法

将方程一边变形为平方和的形式，另一边是常数。从而缩小解的存在范围，达到求解或判定无

解之目的。

例1求方程x*2-12x+y2+2=0的整数解。

手写板图示0105-04

例1.X2—12x+y2+2=O

22

(x-6)+y=34

2

・・・yW34

y2=0,1.4,9,16,25

检验34-y2为完全平方数

•♦y=9或25

(x,y)=(llJ3)(1,3)(11,-3)(1,-3)

(9,5)(3,5)(9,-5)(3,-5)

例2证明方程x2+y2+z?+3(x+y+z)+5=0无有理数解。

手写板图示0105-05

例2x2+y2+z2+3(x+y+z)+5=0

222

(2X4~3)+(2y+3)+(2z+3)=7有有理解

*-*-*«*-*—，//

考虑a2+b2+c2=?m2有整数解”

设蝇整数解(a,b,c,m)中最小正整数

①若M为偶数，a,b,c均为偶数从而傍，)，气勤也是解矛盾

22

②若m为奇数，7m=q(mod8)n=0,1,4(mod8)无解

原方程无解

例3求方程x'（yT）+/■（x-1）=1的整数解。

手写1板图示0105-06

例3x2'(y—1)+y2'(x—1)=1

分析：当y=l时x=2

当x=2时，y=l或一5

手写板图示0105-07

例3X2'(y—1)+y2'(x-l)=l

⑵1)(1,2)

分析：当y=l时x=2

(-5,2)(2,-5)

当x=2时，y=l或一5

当y>l时，(y-l)-x2+y2x-(y2+l)=0有整数解

A=y4+4(y2+1)(y—1)=y4+4y3—4y2+4y—4

=(y2+2y)2—8y2+4y—4

=(y2+2y—2)2—(4y2—12y+8)

=(y2+2y—3)2—(2y2—16y+13)

=(y2+2y—4)2+(20y—20)

手写板图示0105-08

4y2—12y+8>00y>2

2y2-16y+13>0

20y—20>0<=>y>l

•,当代8时，(y2+2y—4)2<A<(y2+2y—3)2

当2Vy<8时，(y2+2y—3)2</iV(y2+2y—2)2

/.当y>2时△不是完全平方数

解为（2,1）（1,2）

当y=2时，X2+4X_5=0（一5,2）（2,一5）

解得x=l或x=-5当y>l时，

=(y2+2y—2)2—(4y2—12y+8)

=(y2+2y-3)2—(2y2-16y+13)

=(y2+2y~4)2+(20y—20)

手写板图示0105-09