二元一次不定方程¶
二元一次不定方程的形式为
\[ ax+by=c \ (a,b,c \in \mathbb{Z} \wedge ab \ne 0) \]
有解条件¶
根据裴蜀定理，方程有整数解的充要条件为
\[ \gcd(a,b) \mid c \]
特解¶
先用扩展欧几里得算法计算
\[ ax+by=\gcd(a,b) \]
的一组解，再乘上 \(\dfrac{c}{\gcd(a,b)}\) 就是原方程的特解。
通解¶
设方程有一组特解 \(x=x_0,y=y_0\) 则通解的形式为
\[ \left\{\begin{matrix} x=x_0 - \dfrac{b}{\gcd(a,b)}t \\ y=y_0 + \dfrac{a}{\gcd(a,b)}t \end{matrix}\right. \tag{1} \]
其中 \(t \in \mathbb{Z}\)。
证明¶
记 \(d = \gcd(a,b)\)，将 \((1)\) 带入原方程
\[ a \left( x_0-\frac{bt}{d} \right) + b \left( y_0 + \frac{at}{d} \right) = ax_0+by_0 = c \]
所以，满足形式 \((1)\) 的都是原方程的解。
设 \(x=x_1,y=y_1\) 也是原方程的解，则
\[ a(x_1-x_0)+b(y_1-y_0)=0 \]
两边同时除以 \(d\) 得
\[ \frac{a}{d}(x_1-x_0) = -\frac{b}{d}(y_1-y_0) \tag{2} \]
因为 \(\dfrac{a}{d}\) 和 \(\dfrac{b}{d}\) 互质，所以 \(\exists t \in \mathbb{Z}\) 使得
\[ y_1-y_0=\frac{a}{d}t \]
将上式带回 \((2)\) 解得
\[ x_1-x_0=-\frac{b}{d}t \]
所以任意两组解都满足 \((1)\) 的形式。
综合前面两段证明，式 \((1)\) 就是原方程的通解。