Pell 方程

二次整數

對於二次有理數 \(a+b\sqrt{D}\)，此處要求 \(D\) 是不含平方因子的整數。當以下情形成立時：

\(a\) 與 \(b\) 是整數，\(D \equiv 2 \pmod 4\) 或 \(D \equiv 3 \pmod 4\)。
\(a\) 與 \(b\) 是整數，或者 \(a\) 與 \(b\) 同時是半整數，\(D \equiv 1 \pmod 4\)。

此時稱該二次有理數 \(a+b\sqrt{D}\) 是二次整數。二次整數與首一整係數二次方程的解構成對應關係。

如果二次整數 \(a+b\sqrt{D}\) 的範數 \(a^2-Db^2\) 為 \(1\) 或 \(-1\)，則它的倒數也是二次整數，恰好是它的共軛或者共軛的相反數。此時稱它為整環 \(Z(\sqrt{D})\) 的 單位數，簡稱單位數。

可以證明，存在 基本單位數，使得全體單位數都可以表示成為基本單位數的冪（或冪的相反數）。它也就是對應 Pell 方程的 基本解，通解可以表示為基本解的冪（或冪的相反數）。

我們用 Dirichlet 逼近定理來逼近二次根式 \(\sqrt{D}\)。即有無窮個有理數（顯然為正有理數）滿足：

\[ \left|\frac{x}{y}-\sqrt{D}\right|\leqslant\frac{1}{y^2} \]

於是，下面的範數就有：

\[ \left|N(x+y\sqrt{D})\right|=|x-y\sqrt{D}||x+y\sqrt{D}|\leqslant\frac{1}{y}(\frac{1}{y}+2y\sqrt{D})\leqslant2\sqrt{D}+1 \]

這是對範數拆出的兩項進行估值。這也直觀地説明只要有理數與 \(\sqrt{D}\) 越接近，範數越小。

因此，範數較小的二次整數有無限個，進而採用一些手段，就可以推出範數為 \(\pm 1\) 的單位數存在，也存在無限個。

進而可以發現，對於所有 \(\sqrt{D}\) 的漸進分數，配上係數之後得到的二次整數的範數都落在非常小的區間。由於 \(\sqrt{D}\) 的漸進分數是餘數循環的，只要其中出現使得範數為 \(\pm 1\) 的漸進分數，經過一個循環之後新的漸進分數湊成的二次整數也應當滿足範數為 \(\pm 1\)，即這個新漸進分數也是單位數。由於第 \(-1\) 個漸進分數規定為 \(\frac{1}{0}\)，對應的二次整數範數為 \(1\)，那麼只要計算每個循環節處前一個漸進分數即可。

根據上逼近與下逼近的結論，第奇數個漸進分數得到的範數為負，偶數個為正。即是否存在範數為 \(-1\) 的二次整數取決於循環連分數的循環節長度是否為奇數。

最後還有一個結論，每經過一個循環，相當於舊的二次整數乘上了一個單位數，得到新的二次整數。因此上面得到的單位數是基本單位數。這樣，就提供了一種 Pell 方程通解的直接計算方法。

連分數過渡到 Pell 方程的一些定理

定理：記 \(x^2−Dy^2=s\)。如果有 \(|s|<\sqrt{D}\)，則 \(\frac{x}{y}\) 一定是 \(\sqrt{D}\) 的漸進分數。

證明：分情況討論。

當 \(s>0\) 時，根據 \(x^2−Dy^2>0\)，有 \(x>y\sqrt{D}\)。並且有

\[ \left|\frac{x}{y}-\sqrt{D}\right|=\frac{s}{y(x+y\sqrt{D})}<\frac{s}{2y^2\sqrt{D}}<\frac{1}{2y^2} \]

此時根據勒讓德判別法，\(\frac{x}{y}\) 是 \(\sqrt{D}\) 的漸進分數。

當 \(s<0\) 時，原始方程 \(x^2−Dy^2=s\) 可以變形為 \(y^2−\frac{1}{D}x^2=-\frac{s}{D}\)。變回上一種情況。於是 \(\frac{y}{x}\) 是 \(\frac{1}{\sqrt{D}}\) 的漸進分數。由倒數定理，\(\frac{x}{y}\) 是 \(\sqrt{D}\) 的漸進分數。

定理：

\[ {p_k}^2-D{q_k}^2={(-1)}^{k+1}Q_{k+1} \]

式中的 \(Q_{k+1}\) 也是拉格朗日連分數定理中的 \(r_k\) 分母。

證明：根據

\[ r_{k+1}=\frac{P_{k+1}+\sqrt{D}}{Q_{k+1}} \]

\[ \sqrt{D}=\frac{r_{k+1}p_k+p_{k-1}}{r_{k+1}q_k+q_{k-1}} \]

消去 \(r\) 可以得到

\[ p_k P_{k+1}+p_{k-1}Q_{k+1}+p_k\sqrt{D}=q_k D+(q_k P_{k+1}+q_{k-1}Q_{k+1})\sqrt{D} \]

根據有理項和無理項對應相等，有

\[ p_k=q_k P_{k+1}+q_{k-1}Q_{k+1} \]

\[ q_k D=p_k P_{k+1}+p_{k-1}Q_{k+1} \]

分別乘以 \(p_k\)、\(q_k\)，再相減，得到

\[ {p_k}^2−D{q_k}^2=(p_kq_{k−1}−p_{k−1}q_k)Q_{k+1}={(−1)}^{k−1}Q_{k+1}={(−1)}^{k+1}Q_{k+1} \]

證畢。

定理：當且僅當 \(k=nL\)，其中 \(n\) 是正整數，\(L\) 是最短循環週期時，有 \(Q_k=1\)。

證明：

已經知道

\[ \Delta+\sqrt{D} \]

是純循環連分數。並且有

\[ r_1(\sqrt{D})=r_1(\Delta+\sqrt{D}) \]

\[ Q_0(\sqrt{D})=Q_0(\Delta+\sqrt{D})=1 \]

因此 \(\sqrt{D}\) 和 \(\Delta+\sqrt{D}\) 從第 \(1\) 項起餘項相同，第 \(0\) 項起分母相同。後續的 \(Q_k\) 完全一致。

因為 \(Q_0=1\)，並且有純循環的週期性，所以 \(Q_{nL}=1\)。

純循環連分數的餘項也純循環。當 \(Q_k=1\) 時，有

\[ r_k=P_k+\sqrt{D}>1 \]

\[ -1<P_k-\sqrt{D}<0 \]

\[ P_k<\sqrt{D}<P_k+1 \]

\[ P_k=\lfloor\sqrt{D}\rfloor=\Delta \]

\[ r_k=\Delta+\sqrt{D}=r_0 \]

根據 \(L\) 為最短週期，有 \(k=nL\)。證畢。

定理：如果 \((x_1, y_1)\) 和 \((x_2, y_2)\) 都是 \(x^2-Dy^2=1\) 的一組整數解，那麼

\[ X=x_1x_2+y_1y_2D \]

\[ Y=x_1y_2+x_2y_1 \]

也是方程的一組整數解。這是因為

\[ X+Y\sqrt{D}=(x_1+y_1\sqrt{D})(x_2+y_2\sqrt{D}) \]

Pell 方程

我們給出兩個不定方程：\(x^2-Dy^{2}=1\) 和 \(x^2-Dy^{2}=-1\)，若 \(D\) 為完全平方數，則第一個方程只有解 \((\pm1,0)\)，第二個方程無解。

若 \(D\) 不為完全平方數，稱形如此類的方程為 Pell 方程。根據相應的二次整環不同，一般研究的 Pell 方程分為 \(1\)、\(-1\)、\(4\)、\(-4\) 四類。

設 \(\xi_{0}=\sqrt{D}\)，它的循環連分數週期為 \(l\)，漸近分數為 \(\frac{p_{n}}{q_{n}}\)，則：

當 \(l\) 為偶數時，第一個方程的全體正解為 \(x=p_{jl-1},y=q_{jl-1},j=1,2,3,\cdots\)，第二個方程無解。
當 \(l\) 為奇數時，第一個方程的全體正解為 \(x=p_{jl-1},y=q_{jl-1},j=2,4,6,\cdots\)，第二個方程的全體正解為 \(x=p_{jl-1},y=q_{jl-1},j=1,3,5,\cdots\)。

還有另一種更加簡單的表示方法：

當 \(l\) 為偶數時，第一個方程的全體解為 \(x+y\sqrt{D}=\pm(p_{l-1}\pm q_{l-1}\sqrt{D})^{j},j=0,1,2,\cdots\)，第二個方程無解。
當 \(l\) 為奇數時，第一個方程的全體正解為 \(x+y\sqrt{D}=\pm(p_{l-1}\pm q_{l-1}\sqrt{D})^{j},j=0,2,4,\cdots\)，第二個方程的全體正解為 \(x+y\sqrt{D}=\pm(p_{l-1}\pm q_{l-1}\sqrt{D})^{j},j=1,3,5,\cdots\)。

這是循環連分數漸進分數與二次有理數乘法的對應關係。該結論由下面的定理給出。

定理：記 Pell 方程 \(x^2-Dy^2=1\) 使得 \(x+y\sqrt{D}\) 最小的一組正整數解為基本解 \((x_1, y_1)\)，則方程的全部正整數解為

\[ x_n+y_n\sqrt{D}=(x_1+y_1\sqrt{D})^n \]

證明：

假如有一組正整數解 \((X, Y)\) 不出現在上述序列中。因為 \(x_1+y_1\sqrt{D}>1\)，所以必然有

\[ (x_1+y_1\sqrt{D})^n<X+Y\sqrt{D}<(x_1+y_1\sqrt{D})^{n+1} \]

兩邊同時乘 \(x_n-y_n\sqrt{D}\)，也就是除以 \((x_1+y_1\sqrt{D})^n\)，有

\[ 1<S+T\sqrt{D}<x_1+y_1\sqrt{D} \]

並且 \((S, T)\) 也是一組整數解。有

\[ 0<S-T\sqrt{D}=\frac{1}{S+T\sqrt{D}}<1 \]

\[ 2S=S+T\sqrt{D}+S-T\sqrt{D}>0 \]

\[ 2T\sqrt{D}=S+T\sqrt{D}-(S-T\sqrt{D})>0 \]

因此 \((S, T)\) 是一組正整數解。這與 \((x_1, y_1)\) 的選取矛盾。證畢。

定理：對於具有奇數位循環節的 \(\sqrt{D}\)，記最小的一組滿足 \(x^2-Dy^2=-1\) 的正整數解為 \((x_1, y_1)\)，則滿足 \(x^2-Dy^2=\pm 1\) 的所有解由

\[ x_n+y_n\sqrt{D}=(x_1+y_1\sqrt{D})^n \]

給出。並且 \((x_{2n}, y_{2n})\) 滿足 \(x^2-Dy^2=1\)，\((x_{2n-1}, y_{2n-1})\) 滿足 \(x^2-Dy^2=-1\)。

證明完全同上。

方程 \(x^2-Dy^2=1\) 必然有解，而方程 \(x^2-Dy^2=-1\) 不一定有解，有解等價於連分數循環節長度為奇數。

定理：如果 \(\sqrt{D}\) 連分數循環節長度為奇數，並且 \(D\) 存在唯一的平方和表示 \(D=r^2+s^2\)，則兩個方程 \(x^2-Dy^2=r\)、\(x^2-Dy^2=s\) 至少有一個有解。

如果瞭解高斯整數的知識，只有當一個數所有的 \(4k+3\) 型素因子均成對，這個數才能進行平方和表示，此時平方和表示的個數就是這個數含有的 \(4k+1\) 型素因子數的個數。

證明：

根據伽羅瓦連分數定理，對稱的餘項 \(r_k\) 和 \(r_{l+1-k}\) 循環部分恰好相反，因此互為倒數負共軛。

因為循環節是奇數，連分數展開中對稱部分最中間的餘項與自己互為倒數負共軛。記對稱部分最中間位置下標為 \(v\)。於是有

\[ \left(\frac{P_v-\sqrt{D}}{Q_v}\right)=-\frac{1}{\left(\frac{P_v+\sqrt{D}}{Q_v}\right)} \]

\[ D={P_v}^2+{Q_v}^2 \]

因為 \(D\) 的平方和表示是唯一的，所以下標 \(v\) 必然有 \(P_v=r\)、\(Q_v=s\)，或者 \(P_v=s\)、\(Q_v=r\)。

由於得到餘項的前面的操作為取倒數，即負共軛，再前面為取整，下標 \(v-1\) 的餘項 \(\left\lfloor\frac{P_{v-1}+\sqrt{D}}{Q_{v-1}}\right\rfloor\) 分母應當與下標 \(v\) 這項相同，即 \(Q_v=Q_{v-1}\)。

由於連分數的結論有 \(x^2-Dy^2=(-1)^vQ_v\) 的解為相應漸進分數，因此上述兩個方程必然存在一個解，為下標 \(v\) 或 \(v-1\) 的漸進分數。證畢。

如果直接對方程 \(x^2-Dy^2=-1\) 兩端取模 \(8\)，能夠知道 \(D\equiv 1 or 2 \pmod 8\)。然而，這只是一個充分條件，而非必要條件。通過取模的方式確定什麼時候方程有解，基本做不到。例如，可以給出一個無解的充分條件：

定理：如果 \(D\) 存在唯一的平方和表示 \(D=r^2+s^2\)，並且 \(r, s\equiv\pm 3 \pmod 8\)，則方程 \(x^2-Dy^2=-1\) 無解。

例如對於 \(34\) 有 \(34=3^2+5^2\)，於是 \(x^2-34y^2=-1\) 無解。

證明：

如果方程 \(x^2-Dy^2=-1\) 有解，則兩個方程 \(x^2-Dy^2=r\)、\(x^2-Dy^2=s\) 至少有一個有解。模 \(8\) 就得到了矛盾。證畢。

對於 \(D\) 為 \(4k+1\) 形式的時候，有可能相應基本單位數的係數是半整數。此時有結論：如果 \(D\) 為 \(4k+1\) 形式時，相應基本單位數的係數是半整數，則基本單位數的三次方係數為整數。

此時，上述方法求出的基本解不是基本單位數，而是基本單位數的三次方。

如果想直接求解 \(D\) 為 \(4k+1\) 形式時的基本單位數，改令 \(\xi_{0}=\frac{\sqrt{D}}{2}\)，並規定這裏的連分數第零項為半整數，重複上述操作，並將結果乘 \(2\)（提出二分之一）。

例如當 \(D\) 為 \(5\) 的時候，\(\frac{\sqrt{5}}{2}\) 的半整數連分數表示為：

\[ \frac{\sqrt{5}}{2}=[\frac{1}{2},\overline{1}] \]

\[ \frac{1}{2}=\frac{1}{2}\frac{1}{1} \]

於是解得基本單位數 \(\frac{1}{2}+\frac{\sqrt{5}}{2}\)。

但是 \(D\) 為 \(17\) 的時候，\(\frac{\sqrt{17}}{2}\) 的半整數連分數表示為：

\[ \frac{\sqrt{17}}{2}=[\frac{3}{2},\overline{1,1,3}] \]

\[ \frac{3}{2}+\frac{1}{1+\frac{1}{1}}=\frac{3}{2}+\frac{1}{2}=\frac{1}{2}\frac{4}{1} \]

於是解得基本單位數 \(4+\sqrt{17}\)。它不屬於半整數形式。

在 \(1\) 到 \(100\) 中，\(5\)，\(13\)，\(29\)，\(53\)，\(61\) 和 \(85\) 的基本單位數屬於這種分母中含 \(2\) 的半整數形式，而 \(17\)，\(37\)，\(41\)，\(65\)，\(73\)，\(89\) 和 \(97\) 的基本單位數屬於非半整數形式。

如果快速求解第 \(n\) 個解（或第 \(n\) 個單位數），只需要求出基本解（或基本單位數），然後藉助快速冪的想法去乘就可以了。注意乘一個二次有理數的時候，\(a\) 與 \(b\) 的變化是一個遞推關係。

如果要求從頭開始連續若干個解（或連續若干個單位數），\(a\) 與 \(b\) 的變化就是一個固定的遞推關係，相鄰三項一定滿足特徵方程，即基本解（或基本單位數）對應的二次三項式。即：

如果基本解（或基本單位數）\(a+b\sqrt{D}\) 是對應的二次方程 \(x^2+px+q=0\) 的解，則有遞推：

\[ \begin{aligned} a_n+pa_{n-1}+qa_{n-2}&=0\\ b_n+pb_{n-1}+qb_{n-2}&=0 \end{aligned} \]

事實上，斐波那契數列（的一半）與盧卡斯數列（的一半）恰好組合成了基本單位數 \(\frac{1}{2}+\frac{1}{2}\sqrt{5}\) 的全體冪，即使引入負下標也成立。這是它們的很多性質的來源。

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用