整系数一次不定方程的解法
在我国的公务员考试中有不定方程的求解，难度颇大。不定方程是小学奥数五年级的知识点，今天来讨论下解法。
定义：形如下式的方程称为一次不定方程，其中未知量的个数大于方程的数量：
整系数一次不定方程的解法
其中方程的系数是整数，求方程的整数解或正整数解。
背景：不定方程早由丢番图(diophantus)进行研究，因此又称丢番图方程。它是数论中古老的分支之一，与代数数论、几何数论和集合数论有着密切的联系。
数论解法：数学解法分为以下三个步骤：
l 判断是否有解;
l 寻找一个特解;
l 构造出解的结构，即写出所有解。
1)整系数一次不定方程有解的充分必要条件是：a、b的大公约数可以整除c。一般记为(a,b)|c。
例如：对于方程3x+6y=8。(3,6)=3，系数a和b的大公约数是3，而8不能整除3，所以该方程没有整数解。
特别的，如果a、b是连续的正整数，由于连续的正整数必定为一个奇数和一个偶数，它们的公约数为1。而1可以被任何整数整除，所以一定有整数解。
2)特解的寻找，通常可以观察得到，或者代入特殊数。
例如：对于方程x+2y=4，很容易发现，(2，1)是其中一个解。或者令x=0，可以得到y=2，即(0,2)也是一个特解。或者令y=0，有x=4，即(4,0)也是特解。
3)有了特解以后，整系数一次不定方程的通解为：
整系数一次不定方程的解法
其中(a,b)表示a和b的大公约数，t为任意整数。
例如：对于方程x+2y=4而言，其通解为：x=2+2t，y=1-t。
4)当系数a和b较大时，不容易观察发现特解，可以采用类似“辗转相除”方法得到。
例如：对于方程37x+107y=25。
选择较小的系数37作为分母，有x=(25-107y)/37=-2y+(25-33y)/37。令(25-33y)/37=u，有33y+37u=25。
两边同时除以33，有y=(25-37u)/33=-u+(25-4u)/33。再令(25-4u)/33=v,有4u+33v=25。
两边再同时除以4，有u=(25-33v)/4=6-8v+(1-v)/4。令(1-v)/4=w，有v+4w=1。
该方程很容易就能观察得到v=1,w=0是一个解。
再进行回代，得到原方程的一个特解：x=-8，y=3。
于是原方程的所有解为：x=-8+107t，y=3-37t，t为任意整数。
需要说明的是，尽管通解的形式可能不同，但是经过代换后，其实质是一样的。
5)另外，对于应用问题，通常要求整数解为正整数。这时通过讨论变量的取值范围，可以得到有限组解。
6)对于连续自然数为系数的不定方程，由于a和b互质，辗转相除法不能进行简化，但是可以通过“凑数”的方法求得特解。
例如：对于方程120x+130y=1370。首先将方程两边同时除以10，化为12x+13y=137。
若采用辗转相除法，方程两边同时除以12，有x=11+(5-13y)/12。令(5-13y)/12=u，有12u+13y=5。可见特解依然不容易观察得到。
但是注意到137÷12=11……5，即137=11×12+5，将11个12中的5个变为13，可将余数5去掉，即137=6×12+5×12+5=6×12+5×13。因此x=6，y=5即为一组特解。
再例如：对于方程120x+110y=1820。首先将方程两边同时除以10，化为12x+11y=182。
182÷11=16……6，即182=16×11+6=10×11+6×12。因此x=10，y=6是一组特解。
程序解法：由于所求不定方程的解都是整数，应用问题都是正整数，因此可以采用多重循环，非常简单的予以实现。
对于方程12x+13y=137而言，137÷12=11.4x，137÷13=10.5x。因此设计一个二重循环，分别循环11次和10次即可。
程序清单如下：
整系数一次不定方程的解法
运行结果为：
整系数一次不定方程的解法
将该程序进行改写，就可以计算出任意整系数一次不定方程的解。
后记：不定方程在数学发展史上之所以重要，是因为它在没有计算机的洪荒年代是研究质数的手段。而人类终发现数论的本质就是研究质数。
真正属于编程领域的算法课题，是采用扩展的欧几里得法求解不定方程。其实质是运用辗转相除法求得系数a和b的大公约数，再进行回代。
上海童程童美少儿编程培训学校面向3-18岁青少年，依托达内教育集团16年编程教育经验，研发出一套系统的少儿编程课程体系，内容涵盖少儿启蒙编程(scratch)和少儿趣味编程(python、javascript、html、css、java)等，培养编程思维，提高中国孩子的综合能力和素质，教育培训品牌,执教、通俗易懂、深受广大学员所欢迎。

---