丢番图方程整数解方法.docx
- 文档编号:10314289
- 上传时间:2023-05-25
- 格式:DOCX
- 页数:15
- 大小:60.35KB
丢番图方程整数解方法.docx
《丢番图方程整数解方法.docx》由会员分享,可在线阅读,更多相关《丢番图方程整数解方法.docx(15页珍藏版)》请在冰点文库上搜索。
丢番图方程整数解方法
求不定方程整数解的常用方法
不定方程是指未知数的个数多于方程的个数,且未知数受到某些限制(如要有理数,整数或正整数等)的方程或方程组。
不定方程也称丢番图方程,是数论的重要分支学科,也是数学上最活跃的数学领域之一。
我国对不定方程的研究已延续了数千年,
“百钱白鸡问题”等一直流传至今,“物不知其数”的解法被称为中国剩余定理。
一般常用的求不定方程整数解的方法包括:
⑴分离整数法
此法主要是通过解未知数的系数中绝对值较小的未知数,将其结果中整数部分分离出来,则剩下部分仍为整数,则令其为一个新的整数变量,以此类推,直到能直接观塞出龔的不定方程为止,再追根溯源,求出原方程的特解.
例1求不定方程耳-y=0的整数解
x+2
解已知方程可化为
x+5x+2+3x+23.3
V===F=1+
x+2x+2x+2x+2x+2
因为y是整数,所以一」一也是整数.
x+2
由此
x+2二一1,3,一3,即
x二一1,一3,1,-3,
相应的>,=4,020.
所以方程的整数解为(-1,4),(-3,0),(1,2),(-5,0).
(2)辗转相除法
此法主要借助辗转相除式逆推求特解,具体步骤如下:
第一步,化简方程,尽量化简为简洁形式(便于利用同余、奇偶分析的形式);
第二步,缩小未知数的圉,就是利用限定条件将未知数限定在某一圉,便于下一步讨论;
第三步,用辗转相除法解不定方程.
例2求不定方程37x+107y=25的整数解.
解因为(37,107)=1|25,所以原方程有整数解.
用辗转相除法求特解:
107=37x2+33,37=33x1+4,33=4x8+1
从最后一个式子向上逆推得到
37x(-26)+107x9=1
所以
37x(-26x25)+107x(9x25)=25
则特解为
斗)=-26x25=-650
\>'(,=9x25=225通解为
x=-650-107r=-8-l07(/+6)
y=225+37/=3+37(/+6)
或改写为
x=-8-107/
.y=3+37t (3)不等式估值法 先通过对所考查的量的放缩得到未知数取值条件的不等式,再解这些不等式得到未知数的取值围. 例3求方程丄+丄+丄=1适合a>>>z的正整数解. Z 解因为 x>y>z 所以 111 xyz 所以 1A11一111 —〈F151F— zxyzzzz 即 2 所以 l(z<3 所以乙=2或? =3. 当乙=2时有 111 —+—=—xy2 所以 丄〈―丄 y%yyy 所以 i(ia y2y 所以2〈yS4 所以y=3或y=4,相应地x=6或4; 当z=3时有 112 —I——=—xy3 所以 丄〈丄+丄丄丄 y%yyy 所以 所以yS3,y=3;相应土也x=3・ 所以g,z)=(632),(442),(333). (4)逐渐减小系数法 此法主要是利用变量替换,使不定方程未知数的系数逐渐减小,直到岀现一个未知量的系数为±1的不定方程为止,直接解出这样的不定方程(或可以直接能用观察法得到特解的不定方程为止,再依次反推上去)得到原方程的通解. 例4求不定方程37x+107y=25的整数解. 解因为(37,107)=1|25,所以原方程有整数解. 有37(107,用y来表示心得 =2? -10冬=]_3、+」2+乜 37°“37 则令 ill4<37,用m来表示y,得 令! ! L=te乙得加=4r.将上述结果一一带回,得原方程的通解为 4 x=-8-107r y+3=37/ 注①解一元二次不定方程通常先判定方程有无解.若有解,可先求ax^by=c的一个特解,从而写出通解.当不定方程系数不大时,有时可以通过观察法求得其解,即引入变量,逐渐减小系数,直到容易求得其特解为止. ②对于二元一次不定方程ax+by=c来说有整数解的充要条件是(a,b)\c. x=x^-bty=儿+〃 (5)分离常数项的方法 对于未知数的系数和常数项之间有某些特殊关系的不定方程,如常数项可以拆成两未知数的系数的倍数的和或差的不定方程,可采用分解常数项的方法去求解方程. 例5求不定方程3x+5y=143的整数解. 解原方程等价于 3x+5y=143o3x+5y=140+3o3(x-l)+5(y-28)=0 因为 (3,5)=1 所以 x—1=5/ eZ y—28=3/ 所以原方程的通解为(X=1_5\reZ. V=28+3/ (6)奇偶性分析法 从讨论未知数的奇偶性入手,一方面可缩小未知数的取值围,另一方面乂可用加 或2/2+l(//eZ)代入方程,使方程变形为便于讨论的等价形式. 例6求方程疋+b=328的正整数解. 解显然不妨设 x〉y〉O 因为328是偶数,所以八y的奇偶性相同,从而x±y是偶数. 令 x+y=2urx-y=2vl 则©、V,u乙且旳〉"]〉0・ 所以 x=u}+Vpy=«! _片 代入原方程得 +X=164 同理,令 uA+Vj=2“2皿一V)=2v2(u2>v2e且w2)v2)0) 于是,有 u;+v;=82 ■■ 再令 U2+v2=2“3,“2_V2=2v3 得 +£=41 此时,心、”3必有一奇一偶,且 取”3=123,4,5,得相应的 居=40,37,32,25,16 所以,只能是«3=5,v3=4. 从而 x=1&y=2 结合方程的对称性知方程有两组解(18,2).(248} (7)换元法 利用不定方程未知数之间的关系(如常见的倍数关系),通过代换消去未知数或倍数,使方程简化,从而达到求解的目的. 例7求方程丄+丄的正整数解. xy1 解显见,x〉7,y〉7・为此,可设x=7+=7+其中〃八川为正整数・ 所以原方程丄+丄=丄可化为 xy7 111 整理得 7+Hl7+777 7(7+〃? )+7(74-«)=(7+m^7+n),即mn=49. 所以 =49,®==7;加3==49 相应地 Xj=56」=&兀2=14宀=14;兀3=&儿=56 所以方程正整数解为(56,8).(14,14),(&56> (8)构造法 构造法是一种有效的解题方法,并且构造法对学生的创造性思维的培养有很重要的意义,成功的构造是学生心智活动的一种探求过程,是综合思维能力的一种体现,也是对整个解题过程的一种洞察力、预感力的一种反映•构造体现的是一种转化策略,在处理不定方程问题时可根据题设的特点,构造出符合要求的特解或者构造一个求解的递推式等. 例8已知三整数b、c•之和为13且2=2,求“的最大值和最小值,并求出此ab 时相应的b与c的值. 解由题意得f+/'+C=1\消去D得(13-^-c^^ b,=cic 整理得到关于C•的一元二次方程 c2+(a-26)c+(a-13)'=0. 因为 △=(a-26)2-4(a-13)2>0,解得0<« 因心0,若“=1,则有疋-25c+144=0,解得C=16或c=9,符合题意,此时 a=1 方=3; c=9 a=1 Vb=7或< c=16 若“=17时,则有疋_%+16=0,无实数解,故心17; 若&=16时,则有c2-10c+9=0,解得c=l或c=9,符合题意,此时 <方=-4或初=_12; c=1c=9 综上所述,"的最大值和最小值分别为16和1,相应的b与c的值分别为 b=-4 c=16 [/? =-4v.或<c=1 (9)配方法 把一个式子写成完全平方或完全平方之和的形式,这种方法叫做配方法•配方法是式子恒等变形的重要手段之一,是解决不少数学问题的一个重要方法•在初中阶段,我们已经学过用配方法解一元二次方程,用配方法推到一元二次方程的求根公式,用配方法把二次函数化为标准形式等等,是数学中很常用的方法. 例9若X2+y2+-=2x+y\^xy+yx的值. 4 解由题意 x2-2x+y2-y+—=0 4 即 (I\2 (x-1)2+y——=0 <2丿 所以 [1 x=^y=- 13 所以xv+/=l+-=- 「22 (10)韦达定理 韦达定理是反映一元二次方程根与系数关系的重要定理,广泛应用于初等代数、三角函数及解析儿何中,应用此法解题时,先根据已知条件或结论,再通过恒等变形 或换元等方法,构造出形如a+b.形式的式子,最后用韦达定理. 例10已知/八g都是质数,且使得关于x的二次方程x2-(8^-10^>+5/^=0至少有一个正整数根,求所有的质数对(〃4). 解设方程的两根分别为E、x2(x} 山根与系数关系得 Xj+x2=8/? 一10g < X\X? =5pq 因为°、§都是质数,且方程的一根为正整数,可知方程的另一根也是正整数.所以 Xx=1,5,阳,5〃,5§ < X2=5pq、pq、5q、5p,q、p 所以xx+x2=5pq+\,pq+5t5q+p,5p+q. 1当+x2=5pq+\时,即5/m+I=8〃-10§,因为八q均是质数,所以 5pq+1)10/? )8/? -10q,故此时无解. 2当Xi+x2=5pq+5时,即pq+5=8p_10q,所以(p+10)-(t/-8)=-85,因为p、q都是质数,且〃+10〉§-&所以 “+10=17,85 解得符合条件的质数对为0")=(7,3). ③当xi+x2=5q+p时,即5q+p=8p-\0q,所以7p=15q,满足条件的质数对. @X]+耳=5”+。 时,即5/? +^=8/? -10q,所以3p=1lg,于是 (p,q)=(7,3)或(",q)=(11,3> 综上所述,满足条件的质数对为(/“)=(7,3)或(/“)=(11,3). (11)整除性分析法 用整除性解决问题,要求学生对数的整除性有比较到位的把握. 例11在直角坐标系中,坐标都是整数的点称为整点,设k为整数,当直线 y=x-3或y=kx+k的交点为整数时,k的值可以取() A.2个B.4个C.6个D.8个 解当"1时,直线>,=—3与y=x+l平行,所以两直线没有交点; 当R=0时,直线>,=—3与尸0(11哄轴)交点为整数; Y=X—3当"1、"0时,直线y=x^y=kx+k的交点为方程组.,,的解,解得y=kx+k ■-3—k X= k— —4k y= •k_\ 因为X、y均为整数, 所以k-1只能取±1,±2,±4 解得 k=2,0,3,—1,5,3. 综上,答案为C. (12)利用求根公式 在解不定方程时,若因数分解法、约数分析均不能奏效,我们不妨将其中一个未知数看成参数,然后利用一元二次方程的求根公式去讨论. 例12已知k为整数,若关于兀的二次方程^+(2^+3)^+1=0有有理根,求k值. 解因为"0,所以kx2+(2k+3)x+\=0的根为 _-(2k+3)±J4“+弘+9_-(2k+3)±J(2k++5 X== 2k2k 由原方程的根是有理根,所以(2£+2『+5必是完全平方式.可设(2£+2『+5=〃,,则加2_(2&+2『=5,即 (加+2上+2X^-2上一2)=lx5, 因为加、&均是整数,所以 m-2k—2=5 解得k=-2或0,因为RH0,所以k的值是-2. (13)判别式法 一元一-次方程根的判别式是中学阶段重要的基础知识,也是一种广泛应用的数学解题方法.该法根据一元二次方程的判别式△=,-4仇・的值来判定方程是否有实数根,再结合根与系数的关系判定根的正负.熟练掌握该法,不仅可以巩固基础知识,还可以提高解题能力和基础知识的综合运用能力. 例13求方程丄+丄+-L=2的整数解. xyxy^4 解已知方程可化为 (4一3x)y2+4xy-4=0 因为x、y均为整数,所以 A=16x2-48x+64>0,且为完全平方数. 于是,令 16F—4&Y+64=(4"尸,其中"为正整数 所以 x2-3x+(4-n2)=0 因为X、"均为整数 所以 △=9-4(4-〃2卜0,且为完全平方数, 即有,4h2-7为完全平方数. 于是,再令 4w2-7=肿,其中m为正整数 所以 (2n+m^n-m)=7 因为2n+“? 与2”-m奇偶性相同,且2/z+m)2n-m 所以 2n+in=7,2“—m=\ 由Jtn=2. 相应的x2-3x=0,解得/=3或%=0涪去),所以x=3 把x=3代入已知方程中得y=2或y=|(舍去)所以y=2所以(x,y)=(3,2) (14)因式分解法 因式分解也是中学阶段重要的基础知识之一•它应用广泛,在多项式简化、计算、方程求根等问题中都有涉及•因式分解比较复杂,再解题时,根据所给题U的特点,灵活运用,将方程分解成若干个方程组来求解•这种方法的U的是增加方程的个数,这样就有可能消去某些未知数,或确定未知数的质因数,进而求出其解.利用因式分解法求不定方程ax+by=cxy(abcH0)整数解的基本思路: 将ax+by=cxy(abcH0)转化为 G-a\cy-b)="b后,若ab可分解为ab=°心=…=aibie乙则解的一般形式为 q+a x~bc+b^再取舍得其整数解. y=— c 231 例14方程二-二=丄<、方都是正整数,求该方程的正整数解. ab4 解已知方程可化为 8/? —12d=ab 所以 (ab+12o)-(8b+96)=-96 即 (g_8X〃+12)=—96 因为“、b都是正整数 所以 b〉0,b+12〉12 这样 /? +12=16或24或32或48或96 所以 b=4或12或20或36或84相应地 "=2或4或5或6或7 所以方程的正整数解为: (2,4),(4,12),(5,20),(6,36),(7,84). 丢番图(Diophantus): 古代希腊人,代数学的鼻祖,早在公元3世纪就开始研究不定方程,因此常称整系数的不定方程为丢番图方程。 口鸡白•钱: 我国古代数学家丘建在《算经》一书中提岀的数学问题: “鸡翁一值钱五,鸡母一值钱三,鸡雏三值钱一。 百钱买百鸡,问鸡翁、鸡母、鸡雏各儿何? ”解: 设母鸡X只,公鸡y只,小鸡(100-x-y)只, 所以3x+5y+(100-x-y)/3=100 且X,y为整数。 化简: X+7y/4=25 公鸡五文一只,所以公鸡数量要至少小于20. 有四种情况符合要求: 辗转相除法,乂名欧儿里德算法,是求两个正整数的最大公因子的算法。 设两数为&、b(a>b),求&和b最大公约数(d,b)的步骤如下: 用&除以b,得&宁b=qrl(OWrl)。 若rl二0,则(a,b)=b;若rlHO,则再用b除以rl,得bF rl=qr2(0^r2).若r2=0,则(a,b)=rl: 若r2#=0,则继续用rl除以r2, 如此下去,直到能整除为止。 其最后一个余数为0的被除数的除数即为(a,b)。 例如: a=25,b=15,a/b=l余10,b/10二1余5,10/5=2余0,最后一个余数为0的被除数的除数就是5,5就是所求最大公约数。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 丢番图 方程 整数 方法