说说一次不定方程的那些事儿

本文作者：刘瑞祥，【遇见数学】 感谢刘老师的投稿支持！

所谓不定方程，是由于方程的个数少于未知数的个数，因此不能完全确定解的方程。据说最早研究这种方程的是古希腊的丢番图（一译丢藩都），所以也叫做丢番图方程。和我们常见方程相同的一点是，不定方程未知数的最高次数叫做不定方程的次数。常见的不定方程只求整数解，所以和数论有密切的关系。

具体到一次不定方程来说，一般形式为 ax+by=c，其中 a、b、c 往往都是整数，而要求的解（x，y）也是整数。这是初等数论的重要课题，虽然早就有了系统、完整的解法，但仍有一定趣味。要注意的是，c 只能是 a 和 b 最大公约数的整数倍。这一结论就是所谓的裴蜀定理。那么，聪明的你能不能给出证明呢？

至于原方程的具体解法，对于只想从科普角度了解的朋友，可以参考别莱利曼的《趣味代数学》，而想更深入了解的朋友，可以参阅《美国大学生数学竞赛例题选讲》。前者是我第一次接触到不定方程的书，但不是下图这个版本，而后者并非是我对它有什么偏爱，只是恰好看过并且能看懂而已。

下面说几个和一次不定方程有关的问题。

一、韩信分油问题

这是一道传统题目：两个老汉要平分一桶十斤的油，但手头只有容积为七斤和三斤但没有刻度的两个篓，这时韩信——就是评书里经常提到的那个韩信——从此路过，三下五除二就为老汉解决了难题。现在要问你怎样才能平分？

这个问题用不定方程的角度来看，就是求 7x+3y=5 的整数解。即使单凭观察，也可以看出其中一组整数解是 x=2 且 y=-3。所以显然过程如下：

1. 用 7 斤的篓从桶中取出 7 斤油 相当于令 x=1；

2. 从 7 斤的篓向 3 斤的篓里倒满油，再把 3 斤篓里的油都倒回桶里，重复两次，此时 7 斤的篓里还剩余 1 斤，桶里有 9 斤油 相当于令 y=-2，此时 x 不变；

3. 把 7 斤篓里剩余的 1 斤油倒在 3 斤的篓里 此时 x、y 都不变；

4. 再用 7 斤的篓把 3 斤的篓倒满，此时桶里还剩 2 斤 相当于 x=2，y 仍然不变；

5. 把 3 斤篓里的油向桶里倒净 相当于 y=-3，x 不变，仍然是 2。

可见，解韩信分油问题的过程就是一步步实现不定方程解的过程，其中的正数是倒出油，负数是倒回油。这里要注意过程的安排，既不能使某个容器里的油超过其容积，也不能让某个容器里的油量为负数。现在问你，如果两人不是平分，而是按照别的方案分配这 10 斤油（限正整数分配），你会吗？或者两个老汉手里的油篓是其它容量的呢？或者要求其中一个老汉取走的油必须在篓里（或者桶里）呢？

在我推荐的第二本书里就有一个类似的题目，我也是看了书里的那个题目后才意识到韩信分油问题和不定方程之间关系的。所谓“后知后觉”，其此之谓乎？

二、正等分圆

三等分圆所有人都会，五等分圆很多人会，那么十五等分圆呢？这是《几何原本》里的一个命题。我们容易想到 15 是 3 和 5 的最小公倍数。所以，如果把整个圆周长看作 15，三等分圆的每份长度就是 5，五等分圆的每份长度就是 3，于是需要解不定方程 5x+3y=1，其中 x 代表三等分弧的数目，y 代表五等分弧的数目，很容易看出 x=-1 且 y=2 是其中一个解。

我们来看这个图示，点 A 既代表圆周起点的 0，也代表终点的 15，然后逆时针旋转下来，B、C 两个五等分点到 A 的弧长分别是 3 和 6，三等分点 D 到 A 点的弧长则是 5。显然，C D 之间的弧长就是 1，也就是圆的十五等分弧，这正好印证了前面说的 x=-1 且 y=2，因为从 A 点逆时针过来后取了两个五等分弧，又去掉一个三等分弧。

当然你肯定已经看出，本例所说的不定方程不止这一组解，比如继续逆时针旋转到 E、F，这相当于 x 和 y 各取什么呢？你能借助这个图理解不定方程的通解吗？

类似的，从点 B 到点 D 对应于 5x+3y=2 的一个（或者一组）解，从点 D 到点 E 对应于 5x+3y=4 的一个（或者一组）解，等等。

三、编程求一次不定方程的解

你会编写一次不定方程的求解程序吗？当然，因为这种方程已经有了通用的解法，看起来是很容易的，但是如果你不知道这个解法呢？我就记不住，原因是嫌公式背起来麻烦，当然归根到底还是不常用，偶尔遇到不定方程就凭观察了，好在一般也不难。不过最好还是编个程序，让程序帮助你对一个个的数值进行试验，此即“遍历法”，是解决很多问题的最终大法。

本文不会真的给出代码的，那会显得过于无趣。不过如果真要编程的话，要注意这么几点，学过编程的人自然能看懂我的意思，其他人就请略过：

1. 各个变量都要用整型数，不能用浮点数，以避免误差；

2. 你可以用公式或者遍历法求解，如果是后者，要注意所给数据是不是有整数解，循环体里面要有退出语句；

3. 仍然是关于遍历法的忠告：对于含有两个变量的一次不定方程，你打算用单循环还是双循环？最好是前者，程序效率高一些。

我能想到的关于编程要注咐的就这么多，希望读者自己编出好的程序。

接下来轻松一下。关于编程，网上有个段子：你学编程的话最好是在中午，因为你学的语言早晚会被淘汰。读者大概也能从前面所列的三条嘱咐里看出本人的思想很老旧了。事实上我从 GWBASIC 一路走来（暴露年龄），大学里学过 C 但没有学到指针就结课了，毕业后自学过 VB 和 Flash 自带的 AS，用两者都作过课件，现在我还用着自编的帮助排课表和考场的 VBA 代码，不过自从 VB 升级到 VB。net 后我再也无力跟随，而 Flash 也基本被淘汰了，无情地验证了那个段子。所以，年轻的你不要得意太早哦。

如果读者还满意这篇文章，就点个赞吧。