ペル方程式

Toru3

$x^2-ny^2=1$ をペル方程式という。
$(x, y) = (1, 0)$ は自明な解である。
$n$ が平方数でない場合は非自明な解を持つ。
以下 $n$ は平方数でない正の整数とする。

右辺の $1$ を $-1$ や $4$ , $-4$ などとしたものを考えることもある。

Toru3

ペル方程式は基本解を $x_1+y_1\sqrt{n}$ とすると全ての解は $x_k + y_k \sqrt{n} = (x_1+y_1\sqrt{n})^k$ と表せる。

$\sqrt{n}$ の連分数展開を使うとペル方程式の基本解が求まる。

Toru3

$\sqrt{n}$ の連分数展開を $[a_0; \overline{a_1, a_2, \dots, a_r}]$ ^[1]とする。

\frac{p_k}{q_k}:=[a_0; a_1, a_2, \dots, a_{k-1}]

とする。

$r$ が偶数のとき
- $x^2-ny^2=-1$ は解を持たない
- $(p_r, q_r)$ が $x^2-ny^2=1$ の基本解
$r$ が奇数のとき
- $(p_r, q_r)$ が $x^2-ny^2=-1$ の基本解
- $x_1+y_1\sqrt{n}=(p_r+q_r\sqrt{n})^2$ が $x^2-ny^2=1$ の基本解

脚注

$\sqrt{n}$ の連分数展開は必ず周期的になるのでこの形だけ考えればよい。また、 $a_0 = \lfloor \sqrt{n} \rfloor$ , $a_r = 2\lfloor \sqrt{n} \rfloor$ となる。また、 $a_1, a_2,..., a_{r-2}, a_{r-1}$ は回文となる。 ↩︎

Toru3

p_k, q_kはp_0=1, q_0=0, p_1=a_0, q_1=1, p_k=a_{k-1}p_{k-1}+p_{k-2}, q_k=a_{k-1}q_{k-1}+q_{k-2}という三項間漸化式で表せる。

よって、漸化式は2x2行列を使って以下のように書ける。

\begin{bmatrix}
p_k & q_k \\
p_{k-1} & q_{k-1}
\end{bmatrix}=
\begin{bmatrix}
a_{k-1} & 1\\
1 & 0
\end{bmatrix}
\begin{bmatrix}
p_{k-1} & q_{k-1}\\
p_{k-2} & q_{k-2}
\end{bmatrix}
繰り返し展開すると以下のようになる。

\begin{bmatrix}
p_k & q_k\\
p_{k-1} & q_{k-1}
\end{bmatrix}=
\begin{bmatrix}
a_{k-1} & 1\\
1 & 0
\end{bmatrix}
\begin{bmatrix}
a_{k-2} & 1\\
1 & 0
\end{bmatrix}\cdots
\begin{bmatrix}
a_1 & 1\\
1 & 0
\end{bmatrix}
\begin{bmatrix}
a_0 & 1\\
1 & 0
\end{bmatrix}

Toru3

途中の $p_k, q_k$ も $p_k^2-nq_k=(-1)^{k-1}\gamma_{k+1}$ となる。
ここで $\alpha_k=\dfrac{\sqrt{n}+\beta_k}{\gamma_k}$ , $\alpha_0 = \sqrt{n}$ , $\alpha_{k+1}=\dfrac{1}{\alpha_k-\lfloor\alpha_k\rfloor}$ 。

Toru3

Amthor's solutionの項を読むとある整数 $m$ とsquare freeな整数 $n'$ を用いて $n=m^2n'$ と表せる $n$ の解を効率よく求めることが出来そう。

$n'$ での基本解 $(x', y')$ を求める
$x+my\sqrt{n'}=(x'+y'\sqrt{n'})^k$ と表せる $k$ を見つける
上の $(x, y)$ が解
- $x+my\sqrt{n'}=x+y\sqrt{m^2n'}=x+y\sqrt{n}$

Toru3

Smooth numbersの項を見ると2次ふるい法と似たような手法で高速化出来そう。(あとでちゃんと読む)

Toru3

x^2-ny^2=1の解は求まるが、x^2-ny^2=-1の解は求まらなさそう

Toru3

$x^2-4ny^2=\pm4$ の解と $x^2-ny^2=\pm1$ の解は $(x, y)\mapsto(x/2, y)$ で1対1対応する。^[1]

脚注

整数論1 第1版のp.94 定理4.2.3 ↩︎

Toru3

https://wkmath.org/gen-pell-f.html

Toru3

$n \not\equiv 0 \pmod 4$ かつ $x^2-ny^2=\pm 4$ の解が存在する $\Rightarrow$ $u^2-nv^2=\pm 1$ の解が存在して $u+v\sqrt{n}=\left(\dfrac{x+y\sqrt{n}}{2}\right)^3$

$u^2-nv^2=\pm 1$ の解が存在する $\Rightarrow$ $x^2-ny^2=\pm 4$ の解が存在して $(x, y)=(2u, 2v)$

Toru3

証明
\dfrac{x+y\sqrt{n}}{2}\cdot\dfrac{x-y\sqrt{n}}{2}=\dfrac{x^2-y^2n}{4}=\pm 1 より(有理数)解である.
ここでyが偶数であるとすると\pm 4 + ny^2は4の倍数となる。よってxも偶数となる。

また、xが偶数であるとするとx^2\mp 4は4の倍数となる。ここでn \not\equiv 0 \pmod{4}よりy^2は少なくとも偶数である必要がある。よってyは偶数となる。

よって、(x, y)の組としては(偶数, 偶数)あるいは(奇数, 奇数)しかない。

(偶数, 偶数)の場合、\dfrac{x+y\sqrt{n}}{2}\in \mathbb{Z}[\sqrt{n}]. よって\left(\dfrac{x+y\sqrt{n}}{2}\right)^3\in \mathbb{Z}[\sqrt{n}]. 従って整数解となる。

よって、以下では(奇数, 奇数)の場合のみ考える。
\left(\dfrac{x+y\sqrt{n}}{2}\right)^3=\dfrac{x(x^2+3y^2n)}{8}+\dfrac{y(y^2n+3x^2)}{8}\sqrt{n}.
x^2+3y^2n=x^2+3(x^2\mp 4)=4x^2\mp 12=4(x^2\mp 3).

よってx(x^2+3y^2n)=4x(x^2\mp 3).

ここでxは奇数なのでx^2\mp 3は偶数. よって8 \mid 4x(x^2\mp 3).
y^2n+3x^2=(x^2\mp 4)+3x^2=4x^2\mp 4=4(x^2\mp 1).

よってy(y^2n+3x^2)=4y(x^2\mp 1).

ここでxは奇数なのでx^2\mp 1は偶数. よって8 \mid 4y(x^2\mp 1).
以上より\left(\dfrac{x+y\sqrt{n}}{2}\right)^3=\dfrac{x(x^2+3y^2n)}{8}+\dfrac{y(y^2n+3x^2)}{8}\sqrt{n}\in \mathbb{Z}[\sqrt{n}].

Toru3

$(x,y)=(奇数, 奇数)$ の場合, $x^2 \equiv 1 \pmod{4}$ , $y^2 \equiv 1 \pmod{4}$ より $n\equiv 1\pmod{4}$ である必要がある.

Toru3

§2. Nearest square continued fraction
§7. Midpoint criteria for determining $A_{k−1}$ and $B_{k−1}$