二元一次不定方程

在數論中，二元一次不定方程是形如 $$a x + b y = c$$ 的不定方程，其中$a, b$是整數，這個方程是關於整數變量$x, y$的方程。

解法

定理：上述方程有解的充要條件是$(a, b) \mid c$，在有解時，若已知方程有一組特解$(x_0, y_0)$，那麼它的所有解的形式是 $$\begin{cases} x = x_0 + \dfrac{b}{(a, b)}s, \\ y = y_0 - \dfrac{a}{(a, b)}s, \end{cases} \quad s \in \Z.$$

因此，我們僅需求出一組特解即可，如果方程有解，我們總可以將上述方程先做化簡，為 $$\dfrac{a}{(a, b)} x + \dfrac{b}{(a, b)} y = \dfrac{c}{(a, b)}$$ 下面，我們總假設$(a, b) = 1.$ 做變換$x = c x', y = c y'$，於是，原方程等價於 $$a x' + b y' = 1.$$ 當式子簡單時可以直接看出一組解，其實，注意到這就是在輾轉相除法中介紹的貝祖等式，它可以由輾轉相除的方法求出一組特解$(x' _0, y'_0)$，進而帶入所作的變換中，有原方程的特解$(x_0, y_0) = (c x' _0, c y'_0)$

示例

求方程$28x+92y=52$的所有整數解。

因為$(28, 92) = 4 \mid 52$，所以原方程有解。原方程化為$7x+23y=13$，先解方程$7x'+23y'=1$，對$(23, 7)$做輾轉相除，有$23 = 3 \times 7 + 2 \qquad 7 = 3 \times 2 + 1.$
於是$1 = 7 - 3 \times 2 = 7 - 3 \times (23 - 3 \times 7) = 10 \times 7 - 3 \times 23.$
於是題目中的方程一組特解為$(x_0, y_0) = 13 (10, -3) = (130, -39)$，所有的解為 $$\begin{cases} x = 130 + 23s, \\ y = -39 - 7s, \end{cases} \quad s \in \Z.$$ 當數字過大時，可以不用先找$(a,b)$，也不用判斷是否有解，直接做輾轉相除即可。

正解（非負解）問題

在實際應用場合中，有時要求方程的解取正數或非負數，這時由以上方法取得的解有一部分可能不適用，這時就要對方程做更精細的討論。對於方程 $$a x + b y = c$$ 當$a, b$異號（不妨假設$a>0$）時，方程總有無窮多組非負解，只需要在解的通式 $$\begin{cases} x = x_0 - \dfrac{b}{(a, b)}s, \\ y = y_0 + \dfrac{a}{(a, b)}s, \end{cases} \quad s \in \Z.$$ 中取充分大的$s$即可。

當$a, b$同號時，只有$a,b,c$同號時才有可能存在非負解，實際上可以證明：當$c > ab - a - b$時不定方程有非負解，解的個數為$\left[\dfrac{c}{ab}\right]$或$\left[\dfrac{c}{ab}\right] + 1$（需驗證不同情形），而當$c = ab$時不定方程無非負解。要求出這些解，只需在解的通式中令兩個未知元大於等於零即可。

而如果$x = 0$或$y=0$，必須滿足$b \mid c$或$a \mid c$。同樣假設$a,b,c$同號，那麼當$c > ab$時原不定方程有正解，且解數為$- \left[-\dfrac{c}{ab}\right]-1$或$-\left[-\dfrac{c}{ab}\right]$，而當$c = ab$時不定方程無正解。要求出這些解，只需在解的通式中令兩個未知元大於零即可。

$n$元一次的不定方程可以化為$n-1$個二元一次不定方程求解，其自由因子有$n-1$個。求解的相關方法參看上一節。

上下節

• 上一節：不定方程
• 下一節：Pythagoras 方程