我国古代有过一个著名的“百鸡问题”： “今有鸡翁一，值钱伍；鸡母一，值钱三；鸡雏三，值钱一。凡百钱买鸡百只，问鸡翁、母、雏各几何？” ——《张邱建算经》 大概意思是说公鸡五元一只，母鸡三元一只，小鸡一元三只，问100元如何买100只鸡?
若设公鸡x只，母鸡y只，小鸡z只，则有：
x+y+z=100
5x+3y+z/3=100
消去未知数z，得到 -14x -8y = -200,化简后得 7x + 4y = 100
这个方程未知数个数多于方程数，而且要求整数解，应该如何解决呢？
像这样的未知数个数多于方程个数的方程，我们称作不定方程。(又叫丢番图方程,求解不定方程又叫丢番图分析)
本篇文章将向大家介绍二元一次不定方程的整数解的求法并将给出推导过程和证明。先向大家介绍一些基本概念。
不定方程：
未知数个数多于方程个数的方程叫不定方程。
二元一次不定方程是指形如 ax + by = c的方程。其中x、y为未知数，a、b、c皆为整数。
整除：
若存在一个整数q，使得整数a、b 满足：a=bq，就称b整除a，记作b|a。
最大公因数：
能整除a、b的最大正整数叫a、b的最大公因数。记作(a,b)。例如：(15,33)=3。
特别的，如果(a,b)=1,我们就称a、b互质。一般互质就记作(a,b)=1,有时互质也记作a⊥b。
【引论】二元一次不定方程 ax + by = c 有整数解的充要条件为(a,b)|c。
证：必要性：设(a,b)=d,并设a=Ad,b=Bd.此时显然有(A,B)=1.
此时我们有 Adx+Bdy = c
则d(Ax+By)=c，故只有当d|c时，原方程才有整数解。
关于其充分性，我们将在下面证明。
另外，对于ax+by=c,一般我们总是假设有(a,b)=1,否则就两边同时除以(a,b)=d 使(a/d,b/d)=1.如果c/d不为整数，我们讨论过了，原方程一定无整数解。
【引理 2】（辗转相除法）
a、b、r皆为正整数，如果存在整数q，使得a=bq+r，且0≤r＜b,就称这个r为最小非负剩余，也叫a除以b的余数。
此时一定有(a,b) = (b,r)。
证：设(a, b)=d, 则 d|a, d|b, 故有d|(a-bq)
又a - bq = r,得到d|r.又因为d|b,则d是b、r的公因数但不一定是最大公因数 ，有d≤(b, r)。
设(b,r)=D, 则 D|b, D|r, 故D|a.则D是a、b的公因数但不一定是最大公因数，有D≤(a, b)。
即d≤D, 且D≤d, 此时只能有D=d,证毕。
这是一种求两个数的最大公因数的方法，叫做辗转相除法或Euclid(欧几里得)算法。
【引理 1】（引论的证明）：若(a,b)=1,则 ax + by = 1 一定有整数解。
证：①：若M、N是两个能写成ax+by的数，那么 jM + kN 一定也能写成ax+by的形式。其中j、k为非0整数。
证①：
设M = ax + by, N = aX + bY
则jM + kN = jax + jby + kaX + kbY = a(jx + kX) + b(jy + kY),其中jx+kX、jy+kY也是整数。①证毕。
②：不妨假设a>b, 此时有
a = b×q1 + r1 (0≤r1 ＜b )
b = r1×q2 + r2 (0≤r2 ＜r1)
r1 = r2×q3 + r3 (0≤r3＜r2)
r2 = r3×q4 + r4 (0≤r4＜r3)
r3 = r4×q5 + r5 (0≤r5＜r4)
……
r(n-1) = r(n)×q(n+1)
由于b>r1>r2>r3>r4>r5>……>r(n)，余数是不断减小的，所以经过有限步骤后余数总会为0。
又由辗转相除法得到(a,b)=(b,r1)=(r1,r2)=(r2,r3)=……=(r(n-1),r(n))=r(n)，又由(a,b)=1,则r(n)=1.
③：改写上面的式子：
r1 = a - b×q1
r2 = b - r1×q2
r3 = r1 - r2×q3
……
r(n) = r(n-2) - q(n)×r(n-1)
a、b本身是形如ax+by的数（因为a=a*1+b*0，b=a*0+b*1），故易知r1也是形如ax+by的数。那么r2也是。以此类推，得到r(n)也是形如ax+by的数，而r(n)=1，故存在一组x、y，使得ax+by=1,证毕。
【引理 3】如果{x=X, y=Y}是 ax + by = c的一组解，那么{x = X-bt, y = Y+at}是方程的所有解。其中t是任意整数。
证：代入原方程即可。
【引理 4】如果a、b互质，则 ax+by=c 一定有整数解。
证：考虑 ax+by = 1,由于(a,b)=1,以及引理1，知道一定存在一对x、y使得ax+by=1.
那么两边同时相乘以c，则
a(cx) + b(cy) = c，其中cx、cy均为整数，证毕。
也就是说，要求ax+by=c的解，应该先求ax+by=1的解。
下面我将向大家说明求出ax+by=1中的x、y的具体方法。
【例1】7x+4y=100 (百鸡问题中的方程)
解：
先解7x+4y=1.由于(7,4)=1,知道方程一定有整数解。
用引理1中介绍的方法，对7和4进行辗转相除：
7 = 4*1 + 3, 4 = 3*1 + 1
则 1 = 4 - 3 = 4 - (7 - 4) = 4*2 - 7 = -7 + 4*2
故 x = -1, y = 2 是7x+4y=1的一组解。故 x = -100, y = 200 是7x+4y=100的一组解。
则 {x = -100 - 4t, y = 200 + 7t} 是7x+4y=100的所有解。其中t为任意整数。
根据原题目，得到 z = 100 - x - y = -3t，又因为鸡的数量不可能是负数，故得到不等式：
-100 - 4t ≥0
200 + 7t ≥0
- 3t ≥0
结合t是整数，解得 -28 ≤t≤ -25，即 t = -25,-26,-27,-28.
则我们得到这个问题的4组解答：
{x = 0, y = 25, z = 75}
{x = 4, y = 18, z = 78}
{x = 8, y = 11, z = 82}
{x = 12, y = 3, z = 85}
这个方法适用于所有这样的一次不定方程（组）。
同时还适用于求一次同余方程 ax ≡ b (mod m) 的整数解。其中若(a,m)=1,则该同余方程实际上可化为 ax + my = -b 。
（@曹曹無敵 这个方法可以用来写那个解同余方程的计算机程序。。）
这篇文章如有错误和遗漏，欢迎大家提出指正。
|
