2元1次不定方程解法新论.docVIP

2. 二元一次不定方程解法新论 二元一次不定方程的一般形式是ax + by = c，ab≠0。因不定方程有无穷多解，而实际问题中常要考虑它的整数解或正整数解。本文中出现的a、b、c、d、……，x、y、z、t、……等字母都表示整数，Z表示整数集合，（a，b）与[a，b]分别表示a和b的最大公约数和最小公倍数。 定理一：二元一次不定方程ax + by = c有整数解（a，b）| c。 其证明见中等师范学校《代数与初等函数》第二册p81—83。其他谈及二元一次不定方程的书籍都有证明，这里从略。 利用定理一，可以判断所给的二元一次不定方程ax + by = c是否有整数解。在有解的情况下，我们不妨假定a、b、c都是正整数，且（a，b）=1。 定理二：若正整数a、b、c、d满足：ab = cd且（b，c）=1，那么一定有：。 证明：∵（b，c）=1，故存在整数m与n使得：mb + nc = 1成立，从而： 令md + na = t，则。 我们可以把二元一次不定方程恒等变形为ab = cd的形式，再应用上述定理解之。 若a、b、c是正整数，（a，b）=1，求二元一次不定方程ax + by = c的所有整数解。 解：对ax + by = c ……（1），不妨设a ≥ b， 当b = 1时，ax + y = c为：ax = c y，因（a，1）=1，由定理二有：。 故ax + y = c的所有整数解为。 当a b 1时，设a = bq + r, 0 r b, 那么(bq + r)x + by = c b(qx+y) = cry。设（c，r）= d， 则c = dc′， r = dr′，从而有： b(qx+y) = d(c′r′) ……（2） 因（a，b）=1，从而（b，r）=1，，故（b，d）=1，由定理二及（2）有： 若r′= 1，则（1）式的所有整数解为： 。 若r′≠1，则继续解二元一次不定方程（3），而（3）的解法与（1）的解法相同，即重复前述步骤一次或数次，可以求出（3）的所有整数解。进而求出（1）的所有整数解。 从以上可知，利用定理二解二元一次不定方程的技巧在于想方设法使（2）式中的r′尽可能地小。若能使（2）式中的r′=1，则求解非常简捷。 求11x + 15y = 7的所有整数解。 解：11(x+2y) = 7(1+y), (注意：而不变为11(x+y) = 74y)因（11，7）=1，故 。 求407x 2816y = 33的所有整数解。 解：因（407，2816）= 11 | 33，原方程可以简化为 37x 256y = 3 37（x7y）= 3（1y），而（37，3）= 1，故 。 求13x 9y = 17的最小正整数解。 解：13（x2y）= 17（1y），因（13，17）= 1，故 。 当t = 0时，就是13x 9y = 17的最小正整数解。 有两种书，甲种每本0.28元，乙种每本0.19元，问5元钱恰可买甲、乙两种书 几本。（西安市1978年数学竞赛试题） 解：设分别买甲、乙两种书x本和y本，则原问题就是求0.28x + 0.19y = 5即28x + 19y = 500的非负整数解。 因19（2x + y）= 10（50 + x），且（19，10）= 1，由定理二有： 。 又x≥0，y≥0，。 答：5元钱恰可买甲种书7本，乙种书16本。 求被3除余a，5除余b，7除余c的正整数。 解：由题意有： 由与= ，3（x2y）= b a y。因（3，1）= 1， 。所以：N = 6（ba）15t + a = 6b 5a 15t。 再由= 6b 5a 15t，7z + 15t = 6b 5a c。 7（z + 2t）= 6b 5a c t，又（7，1）= 1，由定理二有： t = 6b 5a c = 7（b）b 5a c = 7mb 5a c 故N = 6b 5a 15（7mb 5a c）= 70a + 21b + 15c 105m。但 N0, 。那么所求正整数 N = 70a + 21b + 15c 105m 。 定理三：的所有整数解为：。 证明：因， 。 证明与定理三类似，从略。 利用定理三及推论求某些二元一次不定方程组的解是非常简便的。 一支总人数是5的倍数且不少于1000的游行队伍，若按每横排4人编队，最后 差3人；若按每横排3人编队，最后差2人；若按每横排2人编队，最后差1人。求这支游行队??的人数最少是多少？（1978年武汉市数学竞赛题） 解：有题意有 其中N、都是正整数。对、、应用定理三有： N = [4，3，2]x + 1 = 12x + 1（x∈Z）。 再由有：。 那么。 故符合条件的最小正整数N是1045（m = 17）