二元一次不定方程的解法及其应用
2022-03-02龚子明
摘 要:不定方程是数论中一个古老的分支,本文主要研究不定方程中最常见的二元一次不定方程的解法及其在实际生活中的应用。
关键词:二元一次不定方程;整解;解法;应用
不定方程作为数论中最古老的一个分支,其求解方法被无数喜好数学的人所研究。对于方程中未知数的个数比方程的个数多的这类方程(组),我们称之为不定方程(组),例如ax+by=c就为最简单的二元一次不定方程,其中的未知数如无特殊说明,其解限制在整数范围内。
中国古代数学家们对不定方程的研究很早,公元初的“五家井井”问题就是一个不定方程的问题。公元5世纪,张丘建就已经解答了“百钱买百鸡”的问题,“百鸡问题”作为不定方程中典型的例题一直流传至今。本文除了介绍解不定方程常用的方法之外,还利用同余式和连分数对不定方程进行求解。同余是数论中最基本的概念,连分数是一种新形式的“分数”,数学史上,人们对三者的研究已经非常深入,但将三者联系在一起讨论得却非常少。在很多文献中只提到二元一次不定方程和一次同余式的解法是等价的,利用连分数研究不定方程的更是少之又少。
提到不定方程的应用,很对人都局限在商业中求最大利润,本文还阐述了不定方程在线性规划问题中的应用,以及不定方程在化学物质结构求解中的应用。
对不定方程的学习,不仅可以提升我们的数学水平,提高解题能力,还可以很好地培养中学生的思维能力。
1 二元一次不定方程的定义及有整数解的条件
1.1 定义
ax+by=c(1)
式(1)叫做二元一次不定方程,其中a,b,c为整数,且a,b不为0。求方程(1)的整数解x,y的问题叫做解二元一次不定方程。
1.2 有整数解的条件
定理1.1 设ax+by=c有一组整数解x=x0,y=y0,且a,b=d,a=a1d,b=b1d,则(1)式的所有解可以表示成:
x=x0-b1ty=y0-a1tt=0,±1,±2,±3,…(2)
定理1.2 二元一次不定方程ax+by=c有整数解的充要条件是a,b|c。
2 二元一次不定方程的解法
2.1 观察法
当二元一次不定方程中的系数比较简单时,可通过观察直接得到方程的一组特殊整数解,然后据此写出方程的整数解。
2.2 辗转相除法
当二元一次不定方程中的系数比较大时,可以通过辗转相除法求出方程的一组整数解,从而写出方程的全部整数解。
在不定方程ax+by=c有整数解的情况下,设a,b=d,则ax+by=c与方程aa,bx+ba,by=ca,b即adx+bdy=cd同解,令a/d=a1,b/d=b1,c/d=c1,得a1x+b1y=c1,此方程中未知数x和y的系数是互质的,所以只需求出a1x+b1y=1的一组整数解为x=x0,y=y0,则x=c1x0,y=c1y0为方程a1x+b1y=c1的一组整数解,也即为ax+by=c的一组整数解。
假定a>0,b>0。利用辗转相除法易得:
a-1n-1Qn+b-1nPn=1
因此ax+by=1,a,b=1有一组特殊解:
x=-1n-1Qny=-1nPn(3)
其中P0=1,P1=q1,Pk=qkPk-1+Pk-2,Q0=0,Q1=1,Qk=qkQk-1+Qk-2k=2,3,…,n。
依次求出P2,Q2,P3,Q3,…,Pn,Qn,即可得到(3)式。
2.3 降低系數法(逐步取整法)
当方程的系数较大时,以较小的系数作除数辗转相除,根据不定方程的解是整数这一条件,把所求不定方程分解成几个整数的和,从而使系数之绝对值逐步减小,易于观察求出不定方程的解。
设给定一个二元一次不定方程适合下列条件:
ax+by=c,a>b>0,a,b=1(4)
则有整数q1,q′1,r1,r′1满足条件:
a=bq1+r1,0<r1<b
c=bq′1+r′1,0<r′1<b
则b,r1=a,b=1,故方程:
by′+r1x′=r1′(5)
有整数解。设x=x0,y=y0是ax+by=c,a>b>0,a,b=1的一组整数解,则有y=c-ax0b=q′1-q1x0+r′1-r1x0b但y0,q′1-q1x0都是整数,所以r′1-r1x0b也是整数,令r′1-r1x0b=y0′,则x′=x0,y′=y0′是(5)的一组整数解,即(4)的任意一组整数解可以表示为:
x=x′,y=q′1-q1x′+y′(6)
其中x′,y′是(5)的某一组整数解,反之,如果x′,y′是(5)的任意一组整数解,则由(6)式所求出的x,y是(4)的一组解,这是因为由(5)和(6)可以得出:
y=q′1-q1x′+y′=q′1-q1x+r′1-r1xb=c-axb
2.4 矩阵法
将不定方程中的系数进行分离写成矩阵的形式,然后根据矩阵的行初等变换进而求出不定方程的一组特殊解。如若求不定方程ax+by=c的一组特殊解,可以先写出矩阵10a01b,然后对该矩阵施行一系列行初等变换(将其中某一行乘以某个非零整数加到另一行),最终将上述矩阵变换为以下这种形式c(可以变换两行的位置)。我们就可以从变换后的矩阵中的第二行里读出原不定方程的一组特殊解(x0,y0,c)了。
2.5 不等式估算法
利用不等式确定不定方程中某些变量的取值范围,从而求出满足条件的不定方程的解。
2.6 同余式求解法
二元一次不定方程ax+by=c(a,b,c为整数,且a,b不为0)与一次同余式by≡cmoda(a不为0)具有等价关系,当不定方程的系数较大时,可以先利用同余理论使方程简化,最后再根据以上所介绍的方法求出不定方程的整数解。
2.7 连分数求解法
若连分数[a1,a2,…,an]的渐进连分数分别为P1Q1,P2Q2,…,PnQn,则在这些渐进连分数中有下列關系式:
P1=a1,P2=a2a1+1,Pk=akPk-1+Pk-2,(3n)
Q1=1,Q2=a2, Qk=akQk-1+Qk-2,(3n)
PkQk-1-Pk-1Qk=-1k。k2
在有解的条件下,不定方程的求解问题往往取决于求出方程的一组特解x0,y0,如果x′、y′满足不定方程ax+by=1,(其中a,b=1,b>0)则cx′、cy′就是不定方程ax+by=c,(其中a,b=1,b>0)的一组特解,所以要求此方程的特解,关键是要求出x′、y′。
设ab=[q1,q2,…,qn,qn+1],得:
(a,b)(Pn+1Qn-PnQn+1)=-1n+1(a,b)
在条件a,b=d=1下,上式可以化简为:
Pn+1Qn-PnQn+1=-1n+1
当n取奇数时,ax+by=1,(其中a,b=1,b>0)的一组特解是Qn,-Pn。
当n取偶数时,ax+by=1,(其中a,b=1,b>0)的一组特解是-Qn,Pn。
因此,不定方程ax+by=c,(其中a,b=1,b>0)的一组特解是cQn,-cPn,或-cQn,cPn。于是其整数解就可以表示出来了。那么如何求Qn和Pn呢?只需将ab写成连分数[q1,q2,…,qn,qn+1]的形式,再求出其第n个渐进连分数PnQn即可。
3 二元一次不定方程的应用
3.1 二元一次不定方程在古代的应用
中国古代数学家们很早就开始研究不定方程了,约1500年前,张丘建就曾经解答了不定方程中流传千古的典型例题—“百钱买百鸡”的问题。
3.2 二元一次不定方程在线性规划中的应用
例:设x、y满足约束条件10x+4y
360x、y∈N求z=600x+1000y的最大值。
解:由题意设z=600x+1000y=2003x+5y=200z′,即z′=3x+5y,要求z的最大值,只需求出z′的最大值。对以上约束条件运算得到:
15x+8ySymbolcB@
5009x+13ySymbolcB@
56012x+27ySymbolcB@
10800SymbolcB@
ySymbolcB@
40,x、y∈Nz′=3x+5y5z′-17ySymbolcB@
500①3z′-2ySymbolcB@
560②4z′+7ySymbolcB@
1080③0SymbolcB@
ySymbolcB@
40,y、z′∈N
7×②+2×③得:
29z′SymbolcB@
6080,z′SymbolcB@
608029=2091929
由于z′∈N,则z′的最大可能值是209。当z′=209时,由①、②、③知y=34,将z′、y值代入z′=3x+5y得x=13;再将x、y的值代入5x+4y=201,不符合条件5x+4ySymbolcB@
200。
z′的最大可能值是208。当z′=208时,由①、②、③知32SymbolcB@
ySymbolcB@
35,而不定方程3x+5y=208的整数解可以表示为:
x=1+5ty=41-3t(t=0,±1,±2,…)
又由32SymbolcB@
ySymbolcB@
35,即32SymbolcB@
41-3tSymbolcB@
35,则t=2或t=3,因此:
x=11y=35或x=16y=32
经检验,x=11,y=35满足所有约束条件,而x=16,y=32不满足约束条件5x+4ySymbolcB@
200。故z′的最大值是208,即可得z=200z′的最大值是41600。
3.3 二元一次不定方程在商业中求最大利润的应用
例:某公司计划在今年销售冰箱和洗衣机两种产品,这两种产品在市场上非常受欢迎,生产出来的产品都可以销售完,但该公司在资金和劳动力上有一定的限制,因此,该公司要根据实际情况来确定这两种产品的月供应量。调查显示,与这两种产品相关的数据如下表:
问:每月应生产这两种产品多少台,才能使公司获得最大利润?并求最大利润。
解:每月生产冰箱x台,洗衣机y台,总利润为z。
根据表格可得x、y满足约束条件:
30x+20y66②y、z′∈Nx0,y0
目标函数为z=6x+8y。
将目标函数z=6x+8y变形为y=-34x+z8,这是斜率为-34,截距为z8,随z变化而变化的一族平行线,在可行域中,当z8取得最大值时z也取到最大值,由图可知当直线过M点时,z8的值最大,此时z取到最大值。求出M点坐标x=4y=9代入目标函数中求得z=6×4+8×9=96(百元)。
3.4 二元一次不定方程在解化学题中的应用
例:已知某种气体为氮的氧化物,且这种气体共78ml,现将其与过量的氢气混合在一起,在一定的条件下可发生化学反应,生成液态水和氮气,在同温同压下,剩余气体比原混合气体减少了234ml,求该氮的氧化物的分子式。
解:由题意可设该氮的氧化物的分子式为NxOy,根据题中数据可列式子:
NxOy+yH2→x2N2+yH2O液态 ΔV 1 y x2 (1+y-x2) 78 ; 234
整理計算得:78y-x2=156,即:y-x2=2。
此不定方程的解为:x=2,y=3。综上可知,该氮的氧化物的分子式为N2O3。
结语
本文分别运用观察法、辗转相除法、同余式法、连分数法等七种不同的方法来研究二元一次不定方程的解法,其中观察法、辗转相除法和降低系数法是解不定方程的基本方法,矩阵法、不等式估算法、同余式法和连分数法应用矩阵、不等式、同余式和连分数的知识解决不定方程问题,拓展了不定方程的解法。古代的“百鸡问题”已经将不定方程应用于生活中,文中就运用不定方程的基本解法解决了“百鸡问题”,实际上不定方程在实际生活中的应用很广,却不被人们所熟知,很多人大都局限于商业中求最大利润,本文阐述了不定方程在古代生活中、线性规划、商业中求最大利润及化学物质结构求解中的应用。
参考文献:
[1]戎士奎.十章数论[M].贵州:贵州教育出版社,1994.
[2]闵嗣鹤,严士健.初等数论[M].北京:北京高等教育出版社(第三版),2003.
[3]李长明,周焕山.初等数学研究[M].北京:北京高等教育出版社,1995,6.
[4]郑克明.数论基础[M].西南:西南师范大学出版社,1993.
[5]张晓鹏.不定方程[J].中学数学教学参考,2011,11.
[6]周晓锋.求解二元一次不定方程的一种新方法—同余式解法[J].数学教育研究,2012,39.
[7]姚惠.浅谈简单连分数形式的一种推广[J].黔南民族师范学院学报,2004,06.
[8]王凯成.充分利用目标函数解整数规划问题[J].陕西省艺术师范学校数学教学,2004,09.
[9]李复中.初等数论选讲[M].东北:东北师范大学出版社,1984.
[10]孙春竹.二元一次不定方程在解化学题中的应用[J].黑龙江省理科考试研究综合版,2003,05.
[11]陈建本.一次不定方程的应用[J].浙江省青少年日记教育教学研究,2015,03.
[12]袁明豪,严培胜,张清芳.有限简单连分数的几个应用[J].黄冈师范学院学报,2003,6.
作者简介:龚子明(1991— ),女,布依族,贵州都匀人,本科,研究方向:职业教育数学教学。