第六章：线性方程与最大公因数（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可为任意整数。

本作品采用《CC 协议》，转载必须注明作者和本文链接