ペル方程式の最小解の求め方
ペル方程式とは
ペル方程式は,
\(x^2 – Dy^2 = 1\)
但し, \(x, y\) は正の整数で, \(D\) は自然数の定数(平方数でない)です.
この方程式の最小解 \((x, y) = (x_0, y_0)\) が分かると, すべての解を求めることができます. このことについては, 以前の記事「ペル方程式とその解法」に詳しい事は書いてあります.
以前の記事の中では, 最小解を求めるために, \(y\) に小さい整数を実際に当てはめていきました. ところが, 例えば \(D = 13\) のとき, 最小解は
\begin{align*}
(x_0, y_0) = (649, 180)
\end{align*}
となり, 当てはめていく方法では最小解を見つけるのは大変です.
そこで, この記事では連分数を用いてペル方程式の最小解を求める簡単な方法を紹介します.
連分数とペル方程式の最小解
無理数の連分数表示
例として, \(\sqrt{2}\) の連分数表示を考えます.
\begin{align*}
\sqrt{2} &= 1+(\sqrt{2}-1)\\
&= 1+\dfrac{1}{1+\sqrt{2}}
\end{align*}
という変形をします. 分子の有理化といったところです.
次に, この右辺の分母にある \(\sqrt{2}\) の部分に, この式を代入すると,
\begin{align*}
\sqrt{2} &= 1+\dfrac{1}{1+\left(1+\frac{1}{1+\sqrt{2}}\right)}\\
&= 1+\dfrac{1}{2+\frac{1}{1+\sqrt{2}}}
\end{align*}
同様に代入をくり返すと,
\begin{align*}
\sqrt{2} = 1+\dfrac{1}{2+\frac{1}{2+\frac{1}{2+\ddots}}}
\end{align*}
この右辺の形を連分数といいます. ここでは, 分数の分子の部分はすべて1になるようにします. このとき, 分数の横に足されている数字を並べて,
\begin{align*}
\sqrt{2} &= [1;2, 2, 2, \ldots]\\
&= [1; (2)]
\end{align*}
と表します.
ここで, \((2)\) は2が繰り返し現れることを意味します.
同様に, 他の平方根では,
\begin{align*}
\sqrt{3} &= [1; 1, 2, 1, 2, \ldots]\\&= [1; (1, 2)]\\
\sqrt{5} &= [2; 4, 4, \ldots]\\&= [2; (4)]\\
\sqrt{6} &= [2; 2, 4, 2, 4, \ldots]\\ &= [2; (2, 4)]\\
\sqrt{7} &= [2; 1, 1, 1, 4, 1, 1, \ldots]\\ &= [2; (1, 1, 1, 4)]
\end{align*}
のようになります.
一般に, 自然数\(n\)に対して, \(\sqrt{n}\) の連分数表示は
\begin{align*}
\sqrt{n} = [a_0; (a_1, a_2, \ldots, a_k)]
\end{align*}
の形になります.
連分数を用いてペル方程式の最小解を求める
ペル方程式 \(x^2-Dy^2 = 1\) の最小解について, 以下のような定理があります.
定理.
\(D\) は平方数でない自然数とし, \(\sqrt{D}\) の連分数表示を \([a_0; a_1, a_2, \ldots]\) とします.
以下の漸化式によって生成される2つの数列\(\{X_n\}, \{Y_n\}\) を考えます.
\begin{align*}
X_0 = 1, X_1 = a_0, X_{n+2} = X_{n} + a_{n+1}X_{n+1}
\end{align*}
\begin{align*}
Y_0 = 0, Y_1 = 1, Y_{n+2} = Y_{n} + a_{n+1}Y_{n+1}
\end{align*}
また, \(\sqrt{D}\) の連分数展開の繰り返し部分の長さを \(k\) とします.
このとき,
1. \(k\) が奇数のとき
\((X_k, Y_k)\) は \(x^2-Dy^2=-1\) の最小解
\((X_{2k}, Y_{2k})\) が \(x^2-Dy^2=1\) の最小解
2. \(k\) が偶数のとき
\((X_{k}, Y_{k})\) が\(x^2-Dy^2=1\) の最小解
\(x^2-Dy^2=-1\) は解をもたない
この定理を使うと, ペル方程式の最小解を簡単に求められます.
例として, \(D=7\) のとき,
\begin{align*}
x^2-7y^2=1
\end{align*}
を考えます.
\(\sqrt{7}\) の連分数表示は
\begin{align*}
\sqrt{7} = [2; (1, 1, 1, 4)]
\end{align*}
なので, これをもとに数列 \(\{X_n\}, \{Y_n\}\) の項を第4項まで求めると,
\begin{align*}
(X_0, Y_0) &= (1, 0)\\
(X_1, Y_1) &= (2, 1)\\
(X_2, Y_2) &= (3, 1)\\
(X_3, Y_3) &= (5, 2)\\
(X_4, Y_4) &= (8, 3)
\end{align*}
実際, \(8^2-7\cdot 3^2 = 64-7\cdot 9 = 1\) が成り立ちます.
