[數論] 不定方程

參考資料：
不定方程，凡異出版社，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)$.

[數論] Pell's equation(佩爾方程，二元二次不定方程)

參考資料：
HW Lenstra Jr(2002), Solving the Pell Equation, Volume 49, Number 2

D Djukic(2007), Notes on Pell's equation - Usc
單樽, 余紅兵(1996), 不定方程, 凡異出版社

$\sqrt{2}=[1,\dot{2}]$, $1+\sqrt{5}=[3,\dot{4}]$, 週期都是 $1$; $\frac{3}{\sqrt{7}}=[1,\dot{7},\dot{2}]$, 週期是 $2$.

定理1 拉格朗日(1770)證明一個數字能表示成循環連分數，若且唯若此數為二次無理數(即整數係數的二次方程的實數解)

形如 $x^2-dy^2=1$ 的方程, 其中 $d$ 是整數, 這種方程稱為 Pell's equation. 當 $d$ 是完全平方數時, 方程式只有 $(\pm 1,0)$ 解. 以下僅探討當 $d$ 不是完全平方數的情況.

$x^2-dy^2=1$ 總是有解, 但 $x^2-dy^2=-1$ 就不一定有解.

定理6 若 $x_{0}$, $y_{0}$ 是不定方程 $x^{2}-dy^{2}=1$ 的一組正整數解, 且 $x_{0}+\sqrt{d}y_{0}$ 是形如 $x+\sqrt{d}y$ 的最小數, 則該不定方程的全部正整數解 $x$, $y$ 可由下式表示：$x+\sqrt{d}y=(x_{0}+\sqrt{d}y_{0})^{n}$, $n=1,2,...$.

一個線上解 Pell's equation 的網頁：http://www.had2know.com/academics/pell-equation-calculator.html

定理7 設 $d$ 是非平方的正整數, 且 $\sqrt{d}=[a_{1},\dot{a_{2}},...,\dot{a_{t+1}}]$, $\frac{p_{t}}{q_{t}}=[a_{1},a_{2},...,a_{t}]$ 是它的第 $t$ 個漸近分數,
(1) 當 $t$ 是偶數,
$x^2-dy^2=-1$ 無解;
$x^2-dy^2=1$ 的全部正整數解 $x_{n}$, $y_{n}$ 可由下式確定：$x_{n}+\sqrt{d}y_{n}=(p_{t}+\sqrt{d}q_{t})^{n}$, $n=1,2,3,...$

(2) 當 $t$ 是奇數,
$x^2-dy^2=-1$ 的全部正整數解 $x_{n}$, $y_{n}$ 是 $x_{n}+\sqrt{d}y_{n}=(p_{t}+\sqrt{d}q_{t})^{n}$, $n=1,3,5,...$.
$x^2-dy^2=1$ 的全部正整數解 $x_{n}$, $y_{n}$ 是 $x_{n}+\sqrt{d}y_{n}=(p_{t}+\sqrt{d}q_{t})^{n}$, $n=2,4,6,...$.

例3 試求兩個不定方程的全部正整數解: $x^{2}-8y^{2}=-1$, $x^{2}-8y^{2}=1$.
[方法一] 利用同餘的概念
$\because x^{2}\equiv 0,1(mod\; 4)$, $\therefore x^{2}-8y^{2}\equiv x^{2}\equiv 0,1\not\equiv -1(mod\; 4)$.
所以 $x^{2}-8y^{2}=-1$ 無整數解.

由觀察法, 得到 $x_{0}=3$, $y_{0}=1$ 是方程 $x^{2}-8y^{2}=1$ 中, 使 $x+\sqrt{8}y$ 最小的一組正整數解, 故按照公式, 全解可由下式確定：$x_{n}+\sqrt{8}y_{n}=(3+\sqrt{8})^{n}$, $n=1,2,3,...$
依次取 $n=1,2,3,...$, 可得 $(x,y)$ 為 $(3,1),(17,6),(99,35)$.

[方法二] 利用循環連分數的概念
將 $\sqrt{8}$ 表示成循環連分數, 得到 $\sqrt{8}=[2,\dot{1},\dot{4}]$, 週期 $t=2$ 為偶數, 故對於 $x^{2}-8y^{2}=-1$ 而言無解; 對於 $x^{2}-8y^{2}=1$, 此時第 $t$ 個, 亦即第 $2$ 個漸近分數為 $[2,1]=2+\frac{1}{1}=\frac{3}{1}$, 取 $(x_{0},y_{0})=(3,1)$, 全解可寫為 $x_{n}+\sqrt{8}y_{n}=(3+\sqrt{8})^{n}$, $n=1,2,3,...$

解答題
2. 試證: $\sqrt{d}$ 能表示成週期 $1$ 的循環連分數的充分必要條件式 $d=m^{2}+1$, $m$ 是正整數.
6. 試求 $\sqrt{8}$ 的分母最小的漸近分數, 使其誤差小於等於 $10^{-6}$.
10. 試按 $a^{2}$, $b$ 的大小情況, 分別討論方程 $x^{2}+2axy+by^{2}=1$ 的整數解.
11. 設直角三角形的三邊長為整數 $a=2mn$, $b=m^{2}-n^{2}$, $c=m^{2}+n^{2}$, 且 $b=a+1$, 試求出所有這樣的三角形, 並寫出其中邊長為最小的兩個.
12. 試證: 不定方程 $x^{2}+(x+1)^{2}=y^{2}$ 的全部正整數解可表示為 $x=\frac{1}{4}\left ( (1+\sqrt{2})^{2k+1}+(1-\sqrt{2})^{2k+1}-2 \right )$, $y=\frac{1}{2\sqrt{2}}\left ( (1+\sqrt{2})^{2k+1}+(1-\sqrt{2})^{2k+1} \right )$, $k=1,2,...$
13. 試證: 若且為若 $3(a^{2}-1)$ 是平方數時, 以 $2a-1$, $2a$, $2a+1$ 為三邊之三角形的面積是整數, 並找出三個這樣的三角形.
14. 若 $a,b$ 是方程 $x^{2}-dy^{2}=1$ 的一組正整數解, 試證: $0<a-\sqrt{d}b$<1.
16. 若 $x_{1},y_{1}$ 是方程 $x^{2}-dy^{2}=-1$ 的一組最小正整數解, 則方程 $x^{2}-dy^{2}=1$ 的所有正整數解 $u_{k},v_{k}$ 可由 $u_{k}+\sqrt{d}v_{k}=(x_{1}+\sqrt{d}y_{1})^{2k}$, $k=1,2,3,...$ 表示.
17. 設 $d$ 是非平方的正整數, 試證: 若方程 $x^{2}-dy^{2}=k$ 有一組整數解, 它就有無窮多組整數解.
19. 設 $d$ 是非平方的正整數, $a$ 是任意的正整數, 試證: 方程 $x^{2}-a^{2}dy^{2}=1$ 有無窮多組正整數解滿足 $a\mid y$.
20. 有無窮多個三角形數也是平方數.
21. 試求下列不定方程的正整數解: (1) $x^{2}-11y^{2}=1$; (2) $x^{2}-11y^{2}=-1$.
22. 試利用連分數求出下列不定方程的正整數解, 並分別算出最小的一組正整數解: (1) $x^{2}-41y^{2}=-1$; (2) $x^{2}-41y^{2}=1$.
23. 設 $x_{1}, y_{1}$ 和 $x_{2},y_{2}$ 是如下方程的兩組整數解: $x^{2}-dy^{2}=4$, 試證: 由下式確定的 $u,v$ 也是這個方程的整數解: $\frac{u+\sqrt{d}v}{2}=\frac{x_{1}+\sqrt{d}y_{1}}{2}\cdot \frac{x_{2}+\sqrt{d}y_{2}}{2}$.
24. 試求不定方程 $x^{2}-3y^{2}=4$ 的全部正整數解.
25. 設整係數不定方程 $ax^{2}+bxy+cy^{2}=k$ 的判別式 $D=b^{2}-4ac$ 是非平方的正整數, $k\neq 0$, 試證: 如果該方程有整數解, 則必有無窮多個整數解.
27. 試求方程 $x^{2}+xy-y^{2}=19$ 的整數解.
29. 試求方程 $x^{2}-229y^{2}=4$ 的 $y$ 值最小的一組正整數解.
30. 試求方程 $3x^{2}-2xy+3y^{2}=72$ 的整數解.
31. 若 $m$ 為正整數, 試證: 有無窮多個正整數 $n$, 使 $mn+1$ 與 $(m+1)n+1$ 都是完全平方數.
33. 試證: 有無窮多個正整數 $n$, 使平均數 $\frac{1^{2}+2^{2}+...+n^{2}}{n}$ 是完全平方數.