第六章：线性方程与最大公因数（2）

现在，我们知道方程

$ax+by=gcd(a,b)$

总有整数解 $x$ 与 $y$ ，那么方程有多少个解，解该怎样表述呢？
我们由互素 $a$ 与 $b$ 开始，即让 $gcd(a,b)=1$ ，假设 $(x_1,y_1)$ 是方程 $ax+by=1$ 的一个解。通过 $x_1$ 减去 $b$ 的倍数和 $y_1$ 加上 $a$ 的相同倍数，可得到其他解。换句话说，对任何整数 $k$ ，我们得到新解 $(x_1+kb,y_1-ka)$ ，通过计算

$a(x_1+kb)+b(y_1-ka)=ax_1+akb+by_1-bka=ax_1+by_1=1$

仍旧观察 $gcd(a,b)=1$ 情形，可证明这种方法给出所有解，假设 $(x_1,y_1)$ 与 $(x_2,y_2)$ 是方程 $ax+by=1$ 的两个解，即

$ax_1+by_1=1 与 ax_2+by_2=1$

我们用 $y_1$ 乘以第一个方程，用 $y_2$ 乘以第二个方程，再相减就得到了 $b$ ，整理后得到 $ax_1y_2-ax_2y_1=y_2-y_1$
类似的，如果用 $x_2$ 乘以第一个方程，用 $x_1$ 乘以第二个方程，再相减便得到 $bx_2y_1-bx_1y_2=x_2-x_1$
如果令 $k=x_2y_1-x_1y_2$ ，则得到

$x_2=x_1+kb\\ y_2=y_1-ka$

所以，由初识解 $(x_1,y_1)$ 通过去不同的 $k$ 值可得到 $ax+by=1$ 的每个解 $(x_1+kb,y_1-ka)$
如果 $gcd(a,,b)>1$ 情况会怎么样？
我们令 $g=gcd(a,b)$ ，由欧几里得算法知方程 $ax+by=g$ 至少一个解 $(x_1,y_1)$ , 而 $g$ 整除 $a$ 与 $b$ ，故 $(x_1,y_1)$ 是简单方程

$\frac{a}{g}x+\frac{b}{g}y=1$

的解。通过将 $k$ 的值代入

$(x_1+k·\frac{b}{g},y_1-k \frac{a}{g})$

### 线性方程定理
设 $a$ 与 $b$ 是非零整数， $g=gcd(a,b)$ , 方程 $ax+by=g$ 总有一个整数解 $(x_1,y_1)$ ，它可由前面的欧几里得算法得到，则方程的每个解可由 $(x_1+k·\frac{b}{g},y_1-k \frac{a}{g})$ 得到，其中 $k$ 可为任意整数。