[數論] 不定方程

參考資料：
不定方程，凡異出版社，1996年1月初版，ISBN：9576942225

二元一次不定方程
二元一次不定方程式 $ax+by=c$, 其中 $a,b,c$ 都是已知整數, 且 $a,b$ 不全為 $0$.

 $ax+by=c$ 有整數解 $\Leftrightarrow \left ( a,b \right )\mid c$

實際求解的方法，有「誤試法(Trial and Error)」、「歐基里德算法(輾轉相除法)」，有時候解題方法不只一種。

誤試法(Trial and Error)：當 $\left | a \right |,\left | b \right |$ 不大時可以試試看, e.g. $7x+15y=1989$.
歐基里德算法：e.g. $5767x+4453y=-1679$.

設 $(a,b)=1$, $x=x_{0}$, $y=y_{0}$ 是方程式 $ax+by=c$ 的一組解(特解), 則全部的整數解(通解)為 $\left\{\begin{matrix}x=x_{0}+bt\\ y=y_{0}-at\end{matrix}\right.$, $t$ 是任何整數.

<pf> 設 $(x',y')$ 是方程式的一組解, 則 $ax'+by'=c$. 再由 $ax_{0}+by_{0}=c$, 兩式相減得到 $a(x_{0}-x')+b(y_{0}-y')=0$, 由此知 $a\mid b(y_{0}-y')$. 但 $(a,b)=1$, 所以 $a\mid (y_{0}-y')$. 可寫成 $y_{0}-y'=at$, 其中 $t$ 為整數, 即 $y'=y_{0}-at$. 把 $y'=y_{0}-at$ 代回 $a(x_{0}-x')+b(y_{0}-y')=0$, 得到 $x'=x_{0}+bt$.


例10 設 $a,b,n$ 都是正整數, $(a,b)=1$. 當 $n>ab-a-b$ 時, 方程 $ax+by=n$ 有非負整數解; 當 $n=ab-a-b$ 時, 則無非負整數解. 換句話說, 凡大於 $ab-a-b$ 的整數必可表示為 $ax+by$ $(x\geq 0, y\geq 0)$ 的形式, 但 $ab-a-b$ 不能表示為此種形式.

<pf1> 因為 $(a,b)=1$, 所以必有整數 $x,y$ 使得 $ax+by=n$ 成立. 我們總可以選擇 $0\leq x< b$(思考一下,why?).
當 $n>ab-a-b$ 時, $by=n-ax>(ab-a-b)-ax\geq ab-a-b-a(b-1)=-b$. 因此 $y>-1$, 證明了 $y$ 也是非負整數.

當 $n=ab-a-b$ 時, 則 $ax+by=n=ab-a-b$, $x=\frac{ab-a-b-by}{a}=b-1-\frac{b}{a}(y+1)$. 若要使 $x\geq 0$, 因為$(a,b)=1$, 所以 $(y+1)$ 須為 $a$ 的倍數, 且 $\frac{b}{a}(y+1)<b$, 得到 $(y+1)<a$.
且假設 $y$ 也為非負整數, 所以 $(y+1)>0$. 整理得到 $0<(y+1)<a$, 亦即 $a\cdot 0<(y+1)<a\cdot 1$, 顯然 $(y+1)$ 不是 $a$ 的倍數, 與假設矛盾. 故 $x,y$ 無非負整數解.

<pf2>
首先證明方程 $ax+by=n$ 當 $n>ab-a-b$ 時有非負整數解.
方程式的一般解為 $\left\{\begin{matrix}x=x_0+bt\\ y=y_0-at\end{matrix}\right.$, $t\in \mathbb{Z}$. 取 適當的 $t$ 使得 $0\leq y=y_0-at\leq a-1$. 對於此 $t$, 有 $ax=a(x_0+bt)=n-b(y_0-at)>ab-a-b-b(a-1)=-a$. 而 $a>0$, 故 $x=x_0+bt>-1$, 亦即 $x\geq 0$.

其次證明 $n=ab-a-b$ 時, $ax+by=n$ 無非負整數解.
假設方程有解, $x\geq 0, y\geq 0$. 由 $ax+by=n=ab-a-b$ 得 $a(x+1)+b(y+1)=ab$. 因為 $(a,b)=1$, 所以 $a\mid (y+1), b\mid (x+1)$. 於是有 $y+1\geq a, x+1\geq b$. 所以 $ab=a(x+1)+b(y+1)\geq ab+ab=2ab$, 但 $a>0, b>0$, 所以上式矛盾.

例4 若 $a>0$, $b>0$, 且 $(a,b)=1$, 試證：
1. 方程 $ax+by=n$ 的非負整數解之個數為 $\left [ \frac{n}{ab} \right ]$ 或 $\left [ \frac{n}{ab} \right ]+1$.
2. 在 $0\leq n\leq ab-a-b$ 中, 恰有 $\frac{(a+1)(b+1)}{2}$ 個整數 $n$ 能(或不能)表示成 $ax+by$ 的形式, 這裡的 $x,y$ 都是非負整數.


三元一次不定方程
例13 求不定方程 $6x+20y-15z=23$ 的全部整數解.(hint: 從係數小的著手)


一次不定方程組
消元法
例2 《張丘建算經》的百雞問題. 公雞5元一隻, 母雞3元一隻, 小雞1元一隻. 現在用100元買100隻雞, 問公雞, 母雞, 小雞應各買多少隻?
解 設公雞, 母雞, 小雞的隻數分別為 $x,y,z$. 由題意, 得 $\left\{\begin{matrix}x+y+z=100\\ 5z+3y+\frac{z}{3}=100\end{matrix}\right.$. 相應的 $(x,y,z)$ 有 $(0,25,75)$, $(4,18,78)$, $(8,11,81)$ 和 $(12,4,84)$.