[數論] 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}$ 是完全平方數.