ax+by=1对整数

方程ax+by=1有两个未知数，只有一个方程，所以它的解必有无数个。我们首先要限定在整数范围，否则不用玩了。其次这个方程在整数范围内还不一定有解，例如2x+4y=1显然没有解；

3x+6y=1也显然没有解；

6x+9y=1也是没有解的。所以还需要限定一个条件，使得这个不定方程必有解，这个条件是：a,b互质。

题目：已知a,b,x,y都是整数，且a,b互质，解方程ax+by=1

直接讨论有点难，我们先猜几个数字小点的方程。

1、2x+3y=1

解法1：因为2x=-3y+1，所以3×(-y)除以2的余数为1

记作3(-y)≡1 (mod 2)（参见《第五种运算》）

所以-y的最小值就是1，即y=-1

代入原方程可得x=2

所以第一组解（x=2,y=-1）

显然其他形如x=3k+2,y=-2k-1的解都满足方程（呃，每一次我说显然的时候都是惴惴不安，我看起来很显然的结论，您看起来显然不？）

不定方程的解有……(-1,1),(2,-1),(5,-3)……

解法2：因为3÷2=1……1所以3=2×1+1

即3×1-2×1=1，一组解为(-1,1)

其他解由x=3k-1,y=-2k+1推出

我们分析一下两种解法，解法1虽然很简洁漂亮，但是求y的时候必须观察得出，对于数字比较小，是很容易实现的，对于数字比较大，这个观察并不容易。解法2实际上是把带余除法换个形式，比较容易实现。我们重点介绍这个解法，因为这个解法还有一些未解之谜。

从题1我们还可以发现一个特点，此类一次不定方程只要求出一个解，其他解可以代公式计算出来。

2、5x+18y=1

数字大了点方法照旧。

因为18÷5=3……3所以3=18-5×3

因为5÷3=1……2所以2=5-3×1

因为3÷2=1……1所以1=3-2×1

所以1=3-2×1=3-（5-3×1）=-5+3×2

=-5+（18-5×3）×2=5×(-7)+18×2

其中一组解为x=-7,y=2

这个方法其实高中生都见过，就是求两个数最大公约数的辗转相除法，不过是将除法算式写成另一种形式而已。我们称之为扩展辗转相除法。（标准说法叫扩展欧几里得法）

为了便于编写程序，我们发现

5x+18y=1即5x+(5×3+3)y=1即5(x+3y)+3y=1

原方程相当于求解5X+3Y=1（X=x+3y,Y=y）

因为5=3×1+2所以2X+3(X+Y)=1

原方程相当于求解2X’+3Y’=1（X’=X,Y’=X+Y）

而这个方程我们是会猜的，X’=-1,Y’=1逐渐代回即可