扩展欧几里得算法方程整数解的非唯一性探究及解析表达

嘿，你的这个论断完全站得住脚！而且确实能通过已知的一组解$(x,y)$直接构造出无穷多组满足条件的$(x_1,y_1)$，我来给你一步步拆解清楚：

第一步：简化原方程 #

设$d = \text{gcd}(a,b)$，我们可以将$a$和$b$分解为：
$a = d \cdot a'$，$b = d \cdot b'$
此时$\text{gcd}(a',b') = 1$（因为我们已经提取了最大公约数）。原方程两边除以$d$后简化为：
$$a'x + b'y = 1$$

第二步：构造新的整数解 #

已知$(x,y)$是上述简化方程的一组解，对于任意非零整数$k$，我们可以构造新的解：
$$x_1 = x + k \cdot b'$$
$$y_1 = y - k \cdot a'$$

验证构造的有效性 #

把$(x_1,y_1)$代入简化后的方程：
$$
\begin{align*}
a'x_1 + b'y_1 &= a'(x + k \cdot b') + b'(y - k \cdot a') \
&= a'x + a'b'k + b'y - a'b'k \
&= a'x + b'y \
&= 1
\end{align*}
$$
显然等式成立，再乘回$d$就回到原方程，满足$a x_1 + b y_1 = d = \text{gcd}(a,b)$。

同时，因为$k \neq 0$，且$a',b'$是正整数（$a,b \in \mathbb{N}$），所以$x_1 = x + k b' \neq x$，$y_1 = y - k a' \neq y$，完全符合你要求的条件。

换回原变量的构造式 #

如果直接用原方程的$a,b,d$来写，构造式可以整理为：
$$x_1 = x + k \cdot \frac{b}{d}$$
$$y_1 = y - k \cdot \frac{a}{d}$$
这里$\frac{b}{d}$和$\frac{a}{d}$都是整数（因为$d$是$a,b$的公约数），所以$x_1,y_1$必然是整数。

内容的提问来源于stack exchange，提问作者Bazinga