线性方程定理

2021-01-16  本文已影响0人  摇摆苏丹

引言

由裴蜀定理可得,ax+by=gcd(a,b)总有解(x,y)。但该方程有多少解,以及这些解如何表示还是有待解决的问题。

描述

a,b \in \mathbb{N}, n=gcd(a,b),方程ax+by=n的一个特解是(x_1,y_1),那么该方程的所有解为:
(x_1+k\frac{b}{n},y_1-k\frac{a}{n}), k \in \mathbb{Z}

证明

首先验证gcd(a,b)=1,即a,b互质时,该定理成立。
数对(x_1+kb,y_1-ka)ax+by=1的解。因为a(x_1+kb)+b(y_1-ka)=1 \iff ax_1+by_1=1
数对(x_1+kb,y_1-ka)ax+by=1的所有解。任取(x_1,y_1),(x_2,y_2)为方程的两个解,即:
ax_1+by_1=1, ax_2+by_2=1
左式两边同乘以y_2,右式y_1,得:
ax_1y_2+by_1y_2=y_2, ax_2y_1+by_1y_2=y_1
两式相减得a(x_1y_2-x_2y_1)=y_2-y_1
左式两边同乘以x2,右式x1,得:
ax_1x_2+by_1x_2=x_2, ax_2x_1+bx_1y_2=x_1
两式相减得b(x_2y_1-x_1y_2)=x_2-x_1
k=x_2y_1-x_1y_2,得:
x_2=x_1+bk, y_2=y_1-bk
也就是说,方程的任意两个解都满足上述等式。即给定(x_1,y_1),所有的(x_2,y_2)都能使用上述等式表示。这是比数对(x_1+kb,y_1-ka)ax+by=1的解更强的证明。
然后验证gcd(a,b)>1时该定理成立。
n=gcd(a,b),显然n|a,n|b,那么:
ax+by=n \iff \frac{a}{n}x+\frac{b}{n}y=1
(x_1,y_1)是上式的一个特解,那么方程的所有解都可以用下式表示,定理得证。
(x_1+k\frac{b}{n},y_1-k\frac{a}{n}), k \in \mathbb{Z}

上一篇 下一篇

猜你喜欢

热点阅读