毕业论文-线性丢番图方程.doc

线性丢番图方程赵冲1. 线性丢番图方程的问题背景不定方程的整数解问题是数论的一个重要课题，在现实生活中,该问题有很强的实用意义.一个简单的例子是求用给定面值的邮票凑成所需邮资的全部解法。一个较为复杂的例子是为判定某未知蛋白质分子组成,需将其分子量表为种氨基酸的已知分子量，的线性组合，显然及其待求组合系数都是非负整数,而且只给出一种或几种可能的分解是不够的,必须提供全部可能的分解,以供生物学家们选择。Def1 （1）称为元一次线性丢番图方程。求一个仅与有关的整数，在时，方程（1）有非负整数解，而在时，方程（1）无非负整数解。Def2 称为整系数线性型的最大不可表数，称为Frobenius数。求的问题就是历史上著名的Frobenius问题。当时，该问题已彻底解决。在有解的情况下，本文将详细讨论二元一次和三元一次线性丢番图方程的Frobenius问题。2. 元一次线性丢番图方程何时非负整数解定理2.1 设，是不全为零的正整数，对任意的整数，都存在，使得方程成立当且仅当。特殊的，方程（1）对每个有解当且仅当【1】。证明 设因为，如果方程（1）有整数解，那么则存在某个整数使得由得存在整数，使得（2）再令则方程（2）可化为（3）即特殊的，当时，方程（1）对任意整数都有解。定理2.2 ，均为正整数，如果，方程存在非负整数解，【1】。证明 由定理1知存在整数，使得又由带余除法得 令，那么此时可能为负整数，为了保证它的非负性，令则有，从而，故得证。定理2.3 ，均为正整数，不妨设，则证明 作差比较法与作差故得证。定理2.2简化成，均为正整数，只需，方程存在非负整数解，3. Frobenius问题设，均为正整数，记为线性丟番图方程 (1)的Frobenius数，即1. 当时，方程（1）有非负整数解；2. 当时，方程（1）无非负整数解。3.1二元的Frobenius问题定理3.1.1 设，为正整数，则【1】。证明 由定理2.1,2.2,2.3知，对，存在， 使得且 （*）假设表示法不唯一，则且则即又故又因为所以同理可得从而（*）式的表示唯一。如果不能表成，和，的组合，则有则（*）式变为 所以另一方面，若 （*）则又因为则，故，故（*）式变为，这是不可能的综上可得定理3.1.2 设，为正整数，则无非负整数解得充要条件为存在正整数，使得，且该表示唯一【2】。定理3.1.3 设，为正整数，则。（其中表示不超过的最大整数）类似的，也有根据（其中表示的小数部分）有以下推论：推论 设，为正整数，则【2】设，为正整数，令是且无非负整数解的这样的的个数。求证：证明：由定理3.1.2，定理3.1.3，可得 从而。例1 求一元二次丟番图方程的所以非负整数解。解：首先， 满足定理3.1.2，则该方程一定有非负整数解 又 则 即有四组非负整数解，和例2 求一元二次丟番图方程的所以非负整数解。解：首先，不满足定理3.1.2，则该方程不一定有非负整数解但无论取上述值中的任何值，都不满足非负整数的条件于是无非负整数解3.2三元的Frobenius问题在四川大学学报上，柯召教授证明了下面一个定理定理3.2.1 设，为正整数，则。且当时，有【3】。陆文瑞把定理3.2.1推广，得到一个充要条件定理3.2.2 设，为正整数，则的充要条件是（，为非负整数）能表出【4】。定理3.2.2包含了定理3.2.1，因为当时，由定理3.1.1知可经表出而即时1956年，陈重穆把这个定理推广到任意上，即有定理3.2.3 设，为正整数，且，则有，当时，【3】。定理3.2.1有以下特殊情形推论1 若，为正整数，则。且当时，有证明 此定理的证明直接由定理3.2.1和定理3.2.2可得。定理3.2.3也有以下特殊情形推论2 设，为正整数，且，则有，当时，。证明 当时，由定理3.1.1知，方程（1）存在非负整数解，事实上取即可。故假设时，方程（1）也存在非负整数解，则由条件可知此时有，即存在非负整数解，使与定理3.1.1矛盾。综上可知定理3.2.2又较定理3.2.1更为广泛，可由下面的例子说明例3 求解 由定理3.2.1 ， ， 均不能成立，即不能满足定理3.2.1的条件，但满足定理3.2.1的条件且，因而例4 求解 又 故满足推论1的条件 从而类似的运用推论1可以计算10以内的的满足推论1的条件的这些另外还有一些10以内的的但不满足推论1的条件的这些如，故不满足推论1的条件，但是仍有是肯定的。于是采用列举法求它的Frobenius数。有非负整数解，则有非负整数解，则有非负整数解，则无非负整数解，则但是这样的算法在所给的数较大时比较麻烦，我们急于寻求更简单更直接的方法来计算，于是就有了下面的定理。定理3.2.4 设，为正整数，如不能表为的形状。即下列二种情况必有一种成立：i）有正整数存在，适合ii）有正整数存在，适合【4】。定理3.2.5 设，为正整数，为非负整数，不能表出，而（或）其中，则（或）（或）的充要条件是（，为非负整数）能表出【4】。定理3.2.2和定理定理3.2.5结合，有以下特殊情况的推论推论3 若，为正整数，则当（，为非负整数）能表出时，在（，为非负整数）不能表出时，可以表成（或）其中如果能表出，则（或）例 运用推论3再来计算前面已经算过的解 ，故不满足推论1的条件由定理3.1.1，则（，为非负整数）不能表出，则推论3的前一种情况不符合但是其中，且能表出，从而满足推论3的后一种情况。于是类似的方法可以算出10以内其它的不符合推论1但符合推论3的数组参考文献【1】 Melvyn B.Nathanson.Elementary Methods in Number TheoryM.37-40【2】 林源洪.关