毕业论文之线性丢番图方程

毕业论文之线性丢番图方程 线性丢番图方程 赵冲 1. 线性丢番图方程的问题背景 不定方程的整数解问题是数论的一个重要课题，在现实生活中,该问题有很强的实用意义.一个简单的例子是求用给定面值的邮票凑成所需邮资的全部解法。一个较为复杂的例子是为判定某未知蛋白质分子组成,需将其分子量为n种氨基酸的已知分子量，，的线性组合，显然及其待求组合系数都是aaa？1ni 非负整数,而且只给出一种或几种可能的分解是不够的,必须提供全部可能的分解,以供生物学家们选择。 s,2axaxaxnaa，，，,,？？,,,1Def1 (1)称为元一次线性丢番，，11221sss 图方程。 ais,1,,？gaa,,？求一个仅与有关的整数，在，，，，i1snGaagaa,,，,,,,1？？xis,1,,？时，方程(1)有非负整数解，而在，，，，，，11ssi ngaa,,,？时，方程(1)无非负整数解。 ，，1s gaa,,？Gaa,,？Def2 称为整系数线性型的最大不可表数，称为，，，，1s1sFrobenius数。 n,2Gaa,,？求的问题就是历史上著名的Frobenius问题。当时，该问，，1s 题已彻底解决。在有解的情况下，本文将详细讨论二元一次和三元一次线性丢番图方程的Frobenius问题。 s,2axaxaxn，，，,？2. 元一次线性丢番图方程何时非负整数解1122nn xis,1,,？，，i 定理2.1 设，，是不全为零的正整数，对任意的整数，都存在，aax？n1s1，使得方程成立当且仅当。特殊的，方aan,,|？xaxaxaxn，，，,？？，，1ss1122ss 程(1)对每个有解当且仅当【1】。 aa,,1？,n，，1s 证明 设 daa,,,？，，1s 因为，如果方程(1)有整数解，那么 dais|1,,,？xis,1,,？dn|，，，，ii 则存在某个整数使得 qndq, 由得存在整数，，，使得(2) daa,,,？yyayayayd，，，,？？，，1s1s1122ss再令xyqis,,1,,？则方程(2)可化为(3) ayqayqayqdq，，，,？，，ii1122ss即 axaxaxn，，，,？1122ss 特殊的，当aa,,1？,时，方程(1)对任意整数都有解。 n，，1s s,1 aa,,1？,定理2.2 ，，均为正整数，，如果，方aa？naa,,1，，，，,1s1ssii,1 程存在非负整数解，，【1】。 axaxaxn，，，,？xx？1122ss1s 证明 由定理1知存在整数z，，z使得azazazn，，，,？ ？1s1122ss 011,,1,,,,,xais？又由带余除法得 zaqx,， ，，isisii s,1 令，那么 xzaq,，,ssiii,1 nazazaz,，，，？ 1111ssss,, ,，，，，，aaqxaaqxaz？ ，，，，111111sssssss,,, s,1,,axaxazaq？ ,，，，，,1111ssssii,,,,i,1,, ,，，，axaxax？ 1111ssss,, s,1 ,,，aaax1，，,sissi,1 s,1此时可能为负整数，为了保证它的非负性，令 xnaa,,1，，,ssii,1则有，从而，故得证。 ax,0x,0sss 定理2.3 ，，均为正整数，，不妨设，aa,,1？,aa2,,,,aaa？？，，1s1s12s ssss,1,,,,则 min1,1,11aaaaaaaaa,,,,,,？，，，，，，，，,,,,,,1221iisii,,iiii,,,,2112,,,, 证明 作差比较法 ss,,与作差 aaa1,,,aa,1，，，，,,1jiji,,,1,2i,,i ss,, aaaaa11,,,,，，，，,,1jiji,,,,12ii,, ,,，，，，，,,，，aaaaaaaa11？？？，，，，，，，，jjjss11112,， ,,，，，，，，aaaaaa1？？ ，，，，jjjs1211,， ,0 故得证。 aa,,1？,定理2.2简化成a，，a均为正整数，，2,,,,aaa？？，，1s1s12s s axaxaxn，，，,？xx只需，方程存在非负整数解，？， naa,,1，，,1122ss1s1i,1i 3. Frobenius问题 aa,,1？,Gaa,,？aa？设，，均为正整数，，记为线性丟番图方，，，，1s1s1s 程 axaxaxn，，，,？ (1) 1122ss 的Frobenius数，即 1. 当时，方程(1)有非负整数解; nGaa,,,？，，1s 2. 当时，方程(1)无非负整数解。 nGaa,,,,1？，，1s 3.1二元的Frobenius问题 定理3.1.1 设，为正整数，，则【1】。 aa,1,Gaaaa,11,,,aa，，，，，，，，1212121s 证明 axaxnaa，,,,,1，，112212 ,n由定理2.1,2.2,2.3知，对，存在， 使得 xx12 且 (*) naxax,，01,,,xa112212 ,,,naxax,，01,,,xa假设表示法不唯一，则且 112212 ,,,,axaxaxax，,，则即 axxaxx,,,11221122，，111222，， ,又aa,1, aaxx|,，，12，2111， ,axx|,故 211 ,又因为 xxa,,,1112 ,xx,所以 11 ,xx,同理可得 22 从而(*)式的表示唯一。 aaxxx,,1如果n不能表成，和，的组合，则有 12122 ,,naxax,，则(*)式变为 1122 ,,，,aaa11 ，，，，122 ,,,,aa111 ，，，，12 Gaaaaaaaa,111,,,,,,，所以 ，，，，，，12121212 aaaaaxax,,,，另一方面，若 (**) 12121122 axaxaa，，，,11则 ，，，，112212 又因为 aa,1,，，12 则， ax|1，ax|1，1221 故， xa，,1xa，,12112 故(**)式变为，这是不可能的 aaaxaxaaaa,，，，,，11，，，，1211221221 综上可得 Gaaaa,11,,,，，，，，，1212 定理3.1.2 设，，为正整数，，则无非负整aa,1,aaaxaxn，,n，，121s1122 数解得充要条件为存在正整数，使得，且该表示唯一【2】。 kknabkakb,,,1212 a1定理3.1.3 设，为正整数，则。(其aaaaakaaaaa,2[/],,，,，，，，,1s12211221,1k 中表示不超过的最大整数) x[]x a2 类似的，也有 aaakaaaaa,2[/],,，,，，，，,12121212,1k 根据(其中表示的小数部分)有以下推论: x{}x[]{}xxx,, aa12推论 设，为正整数，则【2】 aaaaaakaaaka,2{/}2{/},,,,，，,,1s12121212,,11kk aa,1,Naa,设a，a为正整数，，令是0,,,,naaaa且，，，，12121s1212 naxax,，无非负整数解的这样的的个数。 n1122 Naa,，，112求证: ,Gaa,2，，12 证明:由定理3.1.2，定理3.1.3，可得 a,12 Naaaakaa,[/],,，，，，,121212k,1 a,12 ,[/]aka ,12k,1 ,，，,,aaaaaaa,/2 ，，，，1212121 ,,,aa11/2，，，，12 Naa,，，112从而。 ,Gaa,2，，12 例1 求一元二次丟番图方程的所以非负整数解。 2753xx，,12 n,,536解:首先， G2,721716,,,,，，，，，， 满足定理3.1.2，则该方程一定有非负整数解 x,0,1,2,3,4,5,6,72 537,x2 又 0,,,xZ12 则 x,1,3,5,72 即有四组非负整数解xx,23,1,，xx,16,3,，2753xx，,，，，，，，，，121212 xx,9,5,xx,2,7,和 ，，，，，，，，1212 例2 求一元二次丟番图方程的所以非负整数解。 2835136xx，,12 n,,136918G28,35281351918,,,,解:首先， ，，，，，， 不满足定理3.1.2，则该方程不一定有非负整数解 x,0,1,2,3, 2 但无论x取上述值中的任何值，x都不满足非负整数的条件 21 于是2835136xx，,无非负整数解 12 3.2三元的Frobenius问题 在四川大学学报上，柯召教授证明了下面一个定理 aaa,,1,aaa定理3.2.1 设，，为正整数，，则，，123123 aa12Gaaaaaaaaa,,,1,，,,,，。且当，，，，123312123aa,，，12 aaaa1212a,,,时，有32aaaa,,，，，，aa,，，121212 aa12【3】。 Gaaaaaaaaa,,,1,，,,,，，，，，123312123aa,，，12 陆文瑞把定理3.2.1推广，得到一个充要条件 定理3.2.2 设，，为正整数，，则aaa,,1,aaa，，123123 aa12Gaaaaaaaaa,,,1,，,,,，，，，，123312123aa,，，12 aa12,,Gaaaaaaaaa,,,1,，,,,，auav，的充要条件是，，，，12123312123aa,，，12 ,,aadaadaad,,,,,,(，，为非负整数)能表出【4】。 auv，，1211223定理3.2.2包含了定理3.2.1，因为当 ,,,,,,aaaaa,,,auav，时，由定理3.1.1知可经表出 a31212123 aaaa1212,,,,而 aaaa,,,,,12122aaaa,,，，，，aa,，，121212 aaaa1212即a,,,时 32aaaa,,，，，，aa,，，121212 aa12Gaaaaaaaaa,,,1,，,,,， ，，，，123312123aa,，，12 s,31956年，陈重穆把这个定理推广到任意上，即有 aa,,1？,定理3.2.3 设a，，a为正整数，且，da,，？，，1s1s11 daais,,,,,2,,1？？，则有，，，，ii1 dads,212,,1？？？,，，，，,,,,，，当Gaaaaaadaaa，，1231112sssss,,ddd231s, ,,ddadii,2123,,aaaaadaaais,，，，，,,,,,？？？时，，，,,iissi2311121,,,ddddii,,1231,, dads,212,,1？？？,，，，，,,,,，【3】。 Gaaaaaadaaa，，1231112sssss,,ddd231s, 定理3.2.1有以下特殊情形 aaij,1(),,aaa推论1 若，，为正整数，，则，，ij123 。且当时，有Gaaaaaaa,,1,,,，aaaaa,,,，，123121231212 Gaaaaaaa,,1,,,，，，1231212 证明 此定理的证明直接由定理3.2.1和定理3.2.2可得。 定理3.2.3也有以下特殊情形 推论2 设，，为正整数，且，，aaij,1(),,aada,？，，ij1s11 ，则有，当daais,,,,,2,,1？？Gaaaaaa,,1？,,,，，，，，，，ii111212s 时，。 aaaaais,,,,3,,？Gaaaaaa,,1？,,,，，，，，i121211212s 证明 当时，由定理3.1.1知，方程(1)存在非负整数解，naa,,,11，，，，12 事实上取即可。故 Gaaaa,,11？,,,xx,,,？0，，，，，，112s3s 假设naa,,,,111时，方程(1)也存在非负整数解，则由条件可知，，，，12 此时有axaxaa，,,,,111，即存在非负整数解，使xx,,,？0xx，，，，1122123s12 Gaaaaaa,,1？,,,，与定理3.1.1矛盾。综上可知 ，，11212s 定理3.2.2又较定理3.2.1更为广泛，可由下面的例子 G5,6,11例3 求 ，， 解 由定理3.2.1 611611， ， 549,,,,26,116,11，，，，6,11，， 511511， ， 639,,,,25,115,11，，，，5,11，， 5656， 1119,,,,25,65,6，，，，5,6，， aaa,,,5,6,11均不能成立，即不能满足定理3.2.1的条件，但满足定123 115161,，，，5,6,111,理3.2.1的条件且，因而 ，， 56，G5,6,11115,6115619,，,,,, ，，，，5,6，， 例4 求 G2,3,5，， 解 Gaa2,3,51121312,,,,,,,，，，，，，，，，，12 523231,，,,, 又 故满足推论1的条件 从而 G2,3,52,，， 类似的运用推论1可以计算10以内的的210,,1,,,,,,aaaaaij，，，，123ij 满足推论1的条件的这些 Gaaa,,，，123? GG2,3,52,32,,，，，， ? GG2,3,72,32,,，，，， ?GG2,5,72,54,, ，，，， ?GG2,5,92,54,, ，，，， GG2,7,92,76,,? ，，，， GG3,4,73,46,,? ，，，， GG3,5,83,58,,? ，，，， 210,,1,,,,,,aaaaaij另外还有一些10以内的的但不满足推论，，，，123ij Gaaa,,G3,4,51的条件的这些如 ，，，，123 534345,,,,，,,,aaaa，故不满足推论1的条件，但是仍有1212 Gaaaa3,4,51343416,,,，,，,,，,是肯定的。于是采用列举法求它的，，1212 Frobenius数。 xxx,,0,0,1,G3,4,55,3455xxx，，,有非负整数解，则 ，，，，，，123125 xxx,,0,1,0,G3,4,54,3454xxx，，,有非负整数解，则 ，，，，，，123125 xxx,,1,0,0,G3,4,53,3453xxx，，,有非负整数解，则 ，，，，，，123125 G3,4,53,3452xxx，，,无非负整数解，则 ，，125 但是这样的算法在所给的数较大时比较麻烦，我们急于寻求更简单更直接的 来计算，于是就有了下面的定理。 定理3.2.4 设，，为正整数，，如不能表为aa,1,aaaa，，121233 的形状。即下列二种情况必有一种成立: auavuv，,,,0,012 i)有正整数存在，适合 rs,aarasarasaa,,，,,3121212 ,,,,,,ii)有正整数存在，适合【4】。 aasararasaa,,，,,rs,3211212 ,aad,定理3.2.5 设，，为正整数，，，，aaa,,1,aad,,aaa，，，，1112312123 ,,,aad,auav，，，为非负整数，不能表出，而 auv22123 ,,,,,,,,aaras,,aasar,,arasaars，,,,,0,0(或)其中，则 3123211212 aa12Gaaaaaaaaaas,,,1,，,,,,，(或，，，，1233121232aa,，，12 aa12Gaaaaaaaaaar,,,1,，,,,,，)，，，，1233121231aa,，，12 aa12Gaaaaaaaaaas,,,1,，,,,,，(或，，，，1233121232aa,，，12 aa12,,Gaaaaaaaaaar,,,1,，,,,,，auav，)的充要条件是，，，，121233121231aa,，，12 (，为非负整数)能表出2a【4】。 uv3 定理3.2.2和定理定理3.2.5结合，有以下特殊情况的推论 aaij,1(),,aaaauav，推论3 若，，为正整数，，则当(u，v为，，ij12312 Gaaaaaaa,,1,,,，a非负整数)能表出时， ，，12312123 auav，aaaaras,,uv在(，为非负整数)不能表出时，可以表成(或1233312aasar,,arasaarasa，,,,,,,0,0)其中 321121221 Gaaaaaaaas,,1,,,,，auav，2a如果能表出，则(或，，12312122123 Gaaaaaaaar,,1,,,,，) ，，12312121 例 运用推论3再来计算前面已经算过的 G3,4,5，， 解 (3,4)3,54,51,,,，，，， ，故不满足推论1的条件 534345,,,,，,,,aaaa1212 34uv，由定理3.1.1，，则(，为非负整数)G3,431416,,,,uv，，，，，， 不能表出，则推论3的前一种情况不符合 a,53 014,,,r023,,,s但是其中，，aasar,,,，,，,42315321 ，且能表出，asaraa，,，，，,,,42311112auav，,，，，,324110210a,2112123 从而满足推论3的后一种情况。于是 Gaaaaaaaar,,134343113,,,,，,，,,,，，, ，，12312121 类似的方法可以算出10以内其它的不符合推论1但符合推论3的数组 ?G3,4,53, ，， G3,5,75,? ，， G3,7,86,? ，， G4,5,77,? ，， G4,5,912,? ，， G4,7,911,? ，， G5,6,710,? ，， G7,8,921,? ，， 参考文献 【1】 Melvyn B.Nathanson.Elementary Methods in Number Theory[M].37-40 【2】 林源洪.关于Frobenius问题及其相关问题.集美大学学报[J],2000 年，第5卷第1期:7-10 【3】 陈重穆.关于整系数线性型的一个定理.四川大学学报[J]，1956年， 第一期:57-59 *【4】 陆文瑞.论方程.四川大学学报[J]，1956年，第一期:axbyczn，，, 49-51