第六章:线性方程与最大公因数(2)

现在,我们知道方程

ax+by=gcd(a,b)

总有整数解xy,那么方程有多少个解,解该怎样表述呢 ?
我们由互素ab开始,即让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整除ab,故(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})

###线性方程定理
ab是非零整数,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 协议》,转载必须注明作者和本文链接
Hacking
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!