数论论文-二元一次不定方程.doc

二元一次不定方程数学计算机科学学院摘 要:不定方程在历史上有极其丰富的研究,文献极其丰富，也留下很多经典难题,主要研究二元一次不定方程有整数解的条件,以及利用辗转相除法求出它的一切整数解.关键词:辗转相除法;整数解;最大公约数引言未知数个数多于方程个数,且对解有一定限制(比如要求解为正整数等)的方程.数论中最古老的分支之一.古希腊的丢番图早在公元3世纪就开始研究不定方程,因此常称不定方程为丢番图方程.研究不定方程要解决三个问题:判断何时有解.有解时决定解的个数.求出所有的解.中国是研究不定方程最早的国家,公元初的五家共井问题就是一个不定方程组问题,公元5世纪的 张丘建算经中的百鸡问题标志中国对不定方程理论有了系统研究.秦九韶的大衍求一术将不定方程与同余理论联系起来.百鸡问题说：“鸡翁一,直钱五,鸡母一,直钱三,鸡雏三,直钱一.百钱买百鸡,问鸡翁、母、雏各几何?”.设x,y,z分别表鸡翁、母、雏的个数,则此问题即为不定方程组的非负整数解x,y,z,这是一个三元不定方程组问题.1预备知识定理1 设二元一次不定方程ax+by=c (1)(其中a,b,c是整数且a,b都不是0),有一整数解x=x,y=y;又设(a,b)=d,a= ad,b=b,则(1)的一切解可以表成x= x- bt,y= y+ at, (2)其中t=0,1,2,证 x,y是(1)的解,当然满足ax+by=c.因此a(x- bt)+b(y+ at)=c+(b a-a b)t=c. 这表明对任何整数t (2)都是(1)的解.设x,y是(1)的任一解,则ax+by=c，减去ax+by=c,即得a(x-x)+b(y-y)=0.由上式及a=ad,b=bd得到 a(x-x)+b(y-y)=0.又d=(a,b),故(a,b)=1.有一整数t使得y-y=at,即y=y+at.将y代入上式即得x=x-bt.因此x,y可表成(2)的形状.故(2)表示(1)的一切整数解.证毕2 利用辗转相除法求二元一次方程的解 例1 求7x+4y=100的一切整数解. 解 解方程7x+4y=1,此处a=7,b=4,(a,b)=1.7=41+34=31+13=31 因此7x+4y=1的一个解是x=(-1)1=-1,y=(-1)2=2. 故原方程的一个解是x=-100,y=200.由定理1可知其一切解可以表成X=-4t-100,y=7t+200(t=0,1,2,)定理2 二元一次不定方程ax+by=c,ab0,(a,b)=1 的一切整数解可由x=x,y=q-qx+y,得出。其中a=bq+r,0rb,c=bq+r,0rb 而又有(b,r)=(a,b)=1,故方程by+rx=r有整数解.设x=x,y=y是ax+by=c的任一整数解,则 y=q-qx+.又因为y，q- qx都是整数，所以也是整数.令=y， 则x=x，y= y是by+rx=r的一个整数解，即ax+by=c的任一整数解能写成下列形状:x=x,y= q-qx+y,其中x，y是by+rx=r的某一整数解,反之,若x,y是by+rx=r的任一正整数解,则由x=x,y= q-qx+y所求得的x，y是ax+by=c的一解.例2 求107x+37y=25的一切整数解.解 由给定的方程得 y=-2x+=-2x+y,其中y=应该是整数，故得一新的不定方程37y+33x=25 （1）又 x= =-y+ =-y+x,仿上令x=，又得一新的不定方程：33x+4y=25 （2） 又y=6-8x+=6-8x+y，其中y=，即最后算得x+4y=1 （3）显然（3）的一切解是x=1-4t，y=t (t=0,1,2,).因此（2）的一切解是 x=1-4t，y=6-8x+y=-2+33t (t=0,1,2,).而（1）的一切解是y=-2+33t，x=-y+x=3-37t (t=0,1,2,).故给定方程的所有解是x=3-37t，y=2x+y=-8+107t (t=0,1,2,).结论利用辗转相除法求方程解的本质即现找出其一个特解,再由定理1得出其所有的解.而由定理2求解二元一次