初等数论第二章1

初等数论,NumberTheory,第二章不定方程,本章所讨论的不定方程，是指整系数代数方程，并且限定它的解是整数。本章只讨论几类比较简单的不定方程。,第一节一次不定方程,定义1设a1,a2,an是非零整数，b是整数，称关于未知数x1,x2,xn的方程a1x1a2x2anxn=b(1)是n元一次不定方程。,若存在整数x10,x20,xn0满足方程(1)，则称(x10,x20,xn0)是方程(1)的解，或说x1=x10，x2=x20，xn=xn0是方程(1)的解。,第一节一次不定方程,定理1方程(1)有解的充要条件是(a1,a2,an)b。(2),证明记d=(a1,a2,an)。若方程(1)有解，设为(x1,x2,xn)。则由dai（1in）及整除的性质容易知道式(2)成立。必要性得证。,另一方面，由第一章第三节定理2，存在整数y1,y2,yn使得,第一节一次不定方程,因此，若式(2)成立，则,就是方程(1)的解，充分性得证。证毕。,a1y1a2y2anyn=(a1,a2,an)=d。,第一节一次不定方程,定理2设a，b，c是整数，方程axby=c(3)若有解(x0,y0)，则它的一切解具有，tZ(4)的形式，其中,第一节一次不定方程,证明容易验证，由式(4)确定的x与y满足方程(3)。下面证明，方程(3)的解都可写成式(4)中的形式。,设(x,y)是方程(3)的解，则由ax0by0=axby=c得到a(xx0)=b(yy0)，,第一节一次不定方程,由此，以及,和第一章第三节定理4,得到xx0,因此存在整数t，使得,证毕。,第一节一次不定方程,定理1和定理2说明了解方程(3)的步骤：,()判断方程是否有解,即(a,b)c是否成立；()利用辗转相除法求出x0，y0，使得ax0by0=(a,b)；()写出方程(3)的解,第一节一次不定方程,定理3设a1,a2,an,b是整数，再设(a1,a2,an1)=dn1，(a1,a2,an)=dn，则(x1,x2,xn)是方程(1)的解的充分必要条件是存在整数t，使得(x1,x2,xn,t)是方程组,的解。,第一节一次不定方程,证明若有整数t,使得(x1,x2,xn,t)是方程组(5)的解,则显然(x1,x2,xn)满足方程(1).,设(x1,x2,xn)是方程(1)的解，则a1x1a2x2an1xn1anxn=b。(6)令a1x1a2x2an1xn1=b，则由定理1dn1=(a1,a2,an1)b。,第一节一次不定方程,因此，存在tZ，使得a1x1a2x2an1xn1=dn1t，(7)再由式(6)，得到dn1tanxn=b，即(x1,x2,xn,t)满足方程组(5)。,证毕。,第一节一次不定方程,(a1,a2)=d2,(d2,a3)=d3,(dn2,an1)=dn1,(dn1，an)=dn，,定理3说明了求解n元一次不定方程的方法：先解方程组(5)中的第二个方程，再解方程组(5)中的第一个方程，于是，解n元一次不定方程就化为解n1元一次不定方程。重复这个过程，最终归结为求解二元一次不定方程。由第一章第三节定理5，记,第一节一次不定方程,并且消去中间变量t2,t3,tn1，就可以得到方程(1)的解。,逐个地解方程dn1tn1anxn=b，dn2tn2an1xn1=dn1tn1，d2t2a3x3=d3t3，a1x1a2x2=d2t2，,第一节一次不定方程,例1求不定方程3x6y=15的解。,解(3,6)=315，所以方程有解。,由辗转相除法（或直接观察），可知x=1，y=1是方程3x6y=3的解,所以x0=5，y0=5是原方程的一个解.由定理2，所求方程的解是,第一节一次不定方程,例2求不定方程3x6y12z=15的解。,解原方程等价于x2y4z=5.(8),由定理3，依次解方程t4z=5，x2y=t，分别得到(9),第一节一次不定方程,(10),将式(9)与式(10)中的t消去，得到,注：本例在解方程时,首先将原方程化为等价方程(8),这使问题简化.对例1也可以如此处理.,第一节一次不定方程,例3设a与b是正整数，(a,b)=1，则任何大于abab的整数n都可以表示成n=axby的形式，其中x与y是非负整数，但是n=abab不能表示成这种形式。,解()由定理2，方程axby=n(11)的解具有,第一节一次不定方程,的形式，其中x0与y0满足方程(11)。,由假设条件nabab及式(11)与式(12)，有ax=nby=nb(y0at)ababb(y0at).(13)取整数t，使得0y=y0ata1，,则由式(13)得到axababb(a1)=a，x1,x0,即n=axby，x0，y0。,第一节一次不定方程,()设有x0，y0，使得axby=abab，(14)则a(x1)b(y1)=ab。(15),所以ab(y1)。但是(a,b)=1，于是必有ay1，y1a。,同理可以证明x1b，从而a(x1)b(y1)2ab，这与式(15)矛盾，所以式(14)是不可能的。,第一节一次不定方程,例4设a，b，c是整数，(a,b)=1，则在直线axby=c上，任何一个长度大于的线段上至少有一个点的坐标都是整数。,解由定理2，直线axby=c上的坐标都是整数的点(xt,yt)的坐标是,第一节一次不定方程,其中(x0,y0)是直线axby=c上的坐标都是整数的点，由定理1，这样的点是存在的。,对于任意的tZ，记Pt是以(xt,yt)为坐标的点，则Pt1与Pt之间的距离,这说明，两个“相邻的”坐标是整数的点的距离是，从而得出所求之结论。,第一节一次不定方程,例5将写成三个分数之和，它们的分母分别是2，3和5。,解设,则15x10y6z=19。,依次解方程5t6z=19，15x10y=5t，,第一节一次不定方程,得到(16),(17),从式(16)与式(17)中消去t，得到,第一节一次不定方程,取u=0,v=0，得到x=1,y=1,z=4,因此,第一节一次不定方程,例6甲物每斤5元，乙物每斤3元，丙物每三斤1元，现在用100元买这三样东西共100斤，问各买几斤?,解设买甲物x斤，乙物y斤，丙物z斤，则,5x3yz=100，xyz=100。,消去z，得到7x4y=100。(18),第一节一次不定方程,显然x=0，y=25是方程(18)的解，因此，方程(18)的一般解是,因为x0，y0，所以0t3。即t可以取值t1=0，t2=1，t3=2，t4=3。相应的x，y，z的值是,(x,y,z)=(0,25,75),(4,18,78),(8,11,81),(12,4,84).,第一节一次不定方程,例7求不定方程x2y3z=7的所有正整数解.,解依次解方程t3z=7，x2y=t，,得到,从上式中消去t，得到,第一节一次不定方程,(19),要使x1，y1，z1，则应有3u2v0，v1，1u0。(20),所以3u2v2，u12/3u1，,第一节一次不定方程,即u=1。由此及式(20)，有32v0，v12/3v1，,所以v=1。将u=1，v=1代入式(19)，得到原方程的唯一一组正整数x=2，y=1，z=1。,习题一,1.将写成三个既约分数之和，它们的分母分别是3，5和7。2.求方程x12x23x3=41的所有正整数解。3.求解不定方程组：。,习题一,4.甲班有学生7人，乙班有学生11人，现