ぺル方程式の問題 - k56737kagawa’s blog

[問題]　 $D$ を素数の平方を因数にもたない正の整数とする。
このとき $p^2-D q^2= \pm 1$ を満たす正の整数 $p,q$ を求めよ。

この問題はぺル方程式の問題とよばれている。実際にはぺルは無関係で、

研究したのは主にオイラーである。ぺル方程式の一般解は、「最小解」を求めることで全て求めることができる。ぺル方程式の「最小解」とは、 $p+q\sqrt{D}$ の値が最小となる正の整数 $p,q$ のこととする。解が存在すれば、最小解も存在することが分かる。

[命題１]　 $p^2-D q^2= 1$ の最小解を $p_0,q_0$ とする。

他の解を $p,q$ とすると、ある整数 $k$ が存在して、 $p+q\sqrt{D}=(p_0 + q_0 \sqrt{D})^k$ を満たす。

（証明）最小解の性質から、

$(p_0 + q_0 \sqrt{D})^k \leqq p+q\sqrt{D}$ $\lt(p_0 + q_0 \sqrt{D})^{k+1}$ を満たす整数 $k$ が存在する。

したがって、 $1 \leqq \displaystyle\frac{p+q\sqrt{D}}{(p_0 + q_0 \sqrt{D})^k}$ $\lt$ $p_0 + q_0 \sqrt{D}$ となる。

ノルムを $N(p+q\sqrt{D})=p^2-D q^2$ で定めると、ブラーマグプタの恒等式を使って $N(xy)=N(x)N(y)$ が成り立つ。

ブラーマグプタの恒等式から、 $\displaystyle\frac{p+q\sqrt{D}}{(p_0 + q_0 \sqrt{D})^k} = a+b \sqrt{D}$ となる整数 $a,b$ が存在することも分かる。

$N(a+b \sqrt{D}) = 1$ となるが、 $p_0,q_0$ が最小解であると仮定しているので、 $a+b \sqrt{D} = 1$ でなければならない。よって、 $p+q\sqrt{D}=(p_0 + q_0 \sqrt{D})^k$ が成り立つ。（終）

◇連分数展開のアルゴリズム

$\sqrt{D}$ の整数部分を $a_0$ とする。

$A_0=a_0$ , $B_0=D-A_0^2$ , $x_0=\displaystyle\frac{\sqrt{D}+A_0}{B_0}$ とおく。

$x_0$ の整数部分を $a_1$ とする。

$A_1=a_1 B_0 - A_0$ , $B_1=1+a_1 (A_0 - A_1)$ , $x_1=\displaystyle\frac{\sqrt{D}+A_1}{B_1}$ とおく。

$n \geqq 2$ について、

$x_{n-1}$ の整数部分を $a_n$ とする。

$A_n=a_n B_{n-1} - A_{n-1}$ , $B_n=B_{n-2}+a_n (A_{n-1} - A_n)$ , $x_n=\displaystyle\frac{\sqrt{D}+A_n}{B_n}$ とおく。

[Lemma]

$a_n,A_n,B_n$ は正の整数である。
$0 \leqq \displaystyle\frac{1}{x_n} \leqq 1$
$D-A_n^2 =B_n B_{n-1}$
$\sqrt{D} \lt A_n + B_n$
$\sqrt{D}=a_0+\displaystyle\frac{1}{a_1+\displaystyle\frac{1}{a_2+ \cdots }}$

[系] $\sqrt{D}$ に対して $x_n,a_n,A_n,B_n$ の候補は有限個である。

[定理１] $x_0=\displaystyle\frac{1}{\sqrt{D}-A_0}$ を連分数展開すると、 $x_N=x_0$ を満たす $N$ >0 が存在する。すなわち連分数が「循環」する。

$a_0+\displaystyle\frac{1}{\cdots +\displaystyle\frac{1}{a_n}}=\displaystyle\frac{p_n}{q_n}$ と表すことにする。（ $p_n,q_n$ は正の整数）

これを $n$ 階近似分数とよぶことにする。このとき、
$\displaystyle\frac{p_{n+1}}{q_{n+1}}=\displaystyle\frac{a_{n+1}p_{n}+p_{n-1}}{a_{n+1}q_{n}+q_{n-1}}$ が成り立つ。（ $n \geqq 1$ ）

[Lemma] $C_n=p_n^2-Dq_n^2 , E_n=p_n p_{n-1} - D q_n q_{n-1}$ とおく。
このとき、 $C_n=(-1)^{n+1}B_n ,E_n=(-1)^n A_n$ 　が成り立つ。

[定理2] $p^2-Dq^2=1$ を満たす正の整数 $p,q$ が存在する。
（証明） $x_0=x_N$ となる $N \geqq 1$ が存在するので、正の整数 $n$ について $x_n=x_{n+N}$ が成り立つ。
$A_0=A_N,B_0=B_N$ であるから、 $D-A_N^2=B_N B_{N-1}$ と $D-A_0^2=B_0$ より、 $B_{N-1}=1$ となる。したがって、
$p_{N-1}^2-Dq_{N-1}^2=(-1)^N B_{N-1}=(-1)^N$
なので、 $N$ が奇数であれば、 $p_{N-1}^2-Dq_{N-1}^2=(-1)^N B_{N-1}=-1$ の解が存在する。
また、 $x_0=x_{2N}$ より、 $B_{2N-1}=1$ であるから、
$p_{2N-1}^2-Dq_{2N-1}^2=(-1)^{2N} B_{2N-1}=1$ となる。（終）