ペル方程式と平方数和分解の話

ペル方程式を解く手続き。$D$は$2$以上の平方でない整数とし、
$$x^2-Dy^2=1$$
の解を考えてみる。
$$N=\lfloor\sqrt{D}\rfloor$$
とおく（整数部分）。3つ組：
$$f=(1,~ N,~ N^2-D)$$
を取る。次の操作を繰り返す。
$$(a,~b,~c)~～~(c,~b',~a').$$
ここに、まず$b'$はどう求めるかというと、$N+b~~\mathrm{mod}|c|$で得られる$0$以上$|c|$未満の整数を取ってこれを$N$から引いたものを$b'$とする。
$$D={b'}^2-a'c,~~~a'=-\frac{D-{b'}^2}{c}$$
として$a'$が決まる。これを繰り返していくとき、もし、
$$(-1,~N,~D-N^2)$$
に到達するなら、
$$x^2-Dy^2=-1$$
が最小の整数解を持つことになる。この場合の最小の整数解$(x_0,~y_0)$を$x_0+\sqrt{D}y_0$であらわすとき、
$$(x_0+\sqrt{D}y_0)^2=({x_0}^2+D{y_0}^2+2x_0y_0\sqrt{D})$$
みたいになって$x^2-Dy^2=1$の最小整数解は$({x_0}^2+D{y_0}^2,~2x_0y_0)$になる。
　$(-1,~N,~D-N^2)$に到達することなく
$$(1,~N,~N^2-D)$$
に戻ってくる場合には、そのまま計算すると$x^2-Dy^2=1$の解が出る。
　その計算方法について述べる。まず、
$$(a,~b,~c)~～~(c,~b',~a')$$
において$b+b'$を$|c|$で割る。この値を、
$$(1,~N,~N^2-D)~～~(N^2-D,~b',~c')~～\cdots～~(\pm 1,~N,~\pm(N^2-D))$$
の隣接部分すべてに対して計算し、これを
$$h_0,~h_1,~\cdots,~h_m$$
とおいて行列の積：
$$\bsq{0}{1}{1}{h_0}\bsq{0}{1}{1}{h_1}\cdots\bsq{0}{1}{1}{h_m} = \bsq{p}{\cdot}{q}{\cdot}$$
を計算する。こうして得られる$p,q$について、
$$p+q(N+\sqrt{D})$$
を計算するとき$(p+qN,~q)$が最小解になる。$-1$に到達するなら$-1$の解が出るし、$-1$が出ないまま$1$に戻るならそのまま$+1$の解が出る。

$x^2-199y^2=1$

解く。$D=199,~N=14.$
\begin{align*} (1,~14,~-3)&~～~(-3,~13,~10)~~~~(14-(14+14~~\mathrm{mod}~3)=13)\\[5pt] &~～~(10,~7,~-15)~~~~(14-(14+13~~\mathrm{mod}~10)=7)\\[5pt] &~～~(-15,~8,~9)~~~~(14-(14+7~~\mathrm{mod}~15)=8)\\[5pt] &~～~(9,~10,~-11)~~~~(14-(14+8~~\mathrm{mod}~9)=10)\\[5pt] &~～~(-11,~12,~5)~~~~(14-(14+10~~\mathrm{mod}~11)=12)\\[5pt] &~～~(5,~13,~-6)~~~~(14-(14+12~~\mathrm{mod}~5)=13)\\[5pt] &~～~(-6,~11,~13)~~~~(14-(14+13~~\mathrm{mod}~6)=11)\\[5pt] &~～~(13,~2,~-15)~~~~(14-(14+11~~\mathrm{mod}~13)=2)\\[5pt] &~～~(-15,~13,~2)~~~~(14-(14+2~~\mathrm{mod}~15)=13)\\[5pt] &~～~(2,~13,~-15).~~~~(14-(14+13~~\mathrm{mod}~2)=13)\\[5pt] \end{align*}
ここで、実は$(a,~b,~c)~～~(c,~b,~a)$を満たす形式はアンビグという名前が付いているんだけど、ここから先は折り返しになる。ここの$h=2b/|c|$を中心としてこの先はここまで作ったものの逆配列が現れる。そして$(-3,~14,~1)$まで戻った後で$(1,~14,~-3)$が出てきて終了する。これで$h$を求めてみる。
$$(1,~14,~-3)と(-3,~13,~10)について\frac{14+13}{3}=9.$$
以下同様に、
$$9,~2,~1,~2,~2,~5,~4,~1,~1,~13$$
で$13$はアンビグ隣接：$(-15,~13,~2)~～~(2,~13,~-15)$だからその先は
$$1,~1,~4,~5,~2,~2,~1,~2,~9,~28$$
になる。$28$は戻るとき。これより行列は、
$$A=\bsq{0}{1}{1}{9}\cdots \bsq{0}{1}{1}{1}~とおいて~A\bsq{0}{1}{1}{13}{}^tA\bsq{0}{1}{1}{28}$$
となるが、最後にできる行列の左半分が欲しいので、最後の行列は要らなくて、
$$A\bsq{0}{1}{1}{13}{}^t\!A = \bsq{\cdot}{p}{\cdot}{q}$$
を計算して右半分を取ればいい。計算により、
$$A=\bsq{534}{965}{5003}{9041}$$
がわかるので、
$$A\bsq{0}{1}{1}{13}{}^tA =\bsq{\cdot}{123075134}{\cdot}{1153080099}$$
となる。これらに対して$(p+14q,~q)$を計算すると、
$$\left\{\begin{align*}p+14q &= 16266196520 \\[5pt] q &=1153080099 \end{align*}\right.$$
になるから、結局$x^2-199y^2=-1$の整数解は存在せず、$x^2-199y^2=1$の最小解として、
$${16266196520}^2 - 199\cdot {1153080099}^2=1$$
を得る。実際、
\begin{align*}{16266196520}^2&=264589149227260110400,\\[5pt] 199\times{1153080099}^2&=264589149227260110399\end{align*}
が確かめられる。
もうひとつやってみたい。

$x^2-61y^2=-1$

$D=61,~N=7$でやってみる。
\begin{align*} (1,~7,~-12)&~～~(-12,~5,~3)~~~~(7-(7+7~~\mathrm{mod}~12)=5)\\[5pt] &~～~(3,~7,~-4)~~~~(7-(7+5~~\mathrm{mod}~3)=7)\\[5pt] &~～~(-4,~5,~9)~~~~(7-(7+7~~\mathrm{mod}~4)=5)\\[5pt] &~～~(9,~4,~-5)~~~~(7-(7+5~~\mathrm{mod}~9)=4)\\[5pt] &~～~(-5,~6,~5).~~~~(7-(7+4~~\mathrm{mod}~5)=6)\\[5pt] \end{align*}
ここでそのまま進んでもいいんだけど、実は、
$$(a,~b,~-a)~～~(-a,~b,~a)$$
が現れるとそのあとはそのまま両端の符号が逆転したものが展開される。そして$(12,~7,~-1)$まで戻った後、最後に$(-1,~7,~12)$となり、そこから先は両端の符号が逆なだけで同じ流れになる。先程の議論で2つだったところがひとつになるイメージ。その区切りまで$h=(b+b')/|c|$を計算すると、
$1,~4,~3,~1,~2$
となりそこからは$2,~1,~3,~4,~1,~14$みたいになる。行列も、やっぱり最後のやつは計算しなくてよくて、
$$A=\bsq{0}{1}{1}{1}\bsq{0}{1}{1}{4}\bsq{0}{1}{1}{3}\bsq{0}{1}{1}{1}\bsq{0}{1}{1}{2}としてA~{}^t\!A=\bsq{\cdot}{p}{\cdot}{q}$$
を出せばいい。
$$A=\bsq{17}{47}{21}{58},~~~A~{}^t\!A=\bsq{\cdot}{3083}{\cdot}{3805},~~\left\{\begin{align*}x&=3083+3805N = 29718,\\[5pt] y&= 3805.\end{align*}\right.$$
$$x^2=883159524,~~~61y^2=883159525,~~~x^2-61y^2=-1.$$
$x^2-61y^2=1$の最小の整数解は、この$x$と$y$から出すのだが、めちゃんこ大きくなる。
$(x+\sqrt{61}y)^2=(x^2+61y^2)+2xy\sqrt{61}=1766319049+226153980\sqrt{61}$
だからこの$2$数になる。すごい大きい・・。

まとめ

結局、最初の形式まで戻る必要はなくて、
$$(a,~b,~c)~～~(c,~b,~a)$$
となるか、
$$(a,~b,~-a)$$
が現れるところまで計算すればいい。そして前者の場合はそこまでの$h$に対する行列$A$と中央のひとつと$A$の転置を順番に掛けて右半分を見て$N$をかませていじる、後者の場合は普通にそこまでの$h$に対する$A$に対しその転置を掛けてやはり右半分を見て$N$をかませていじればいい。そうすると$-1$の方の解が出るので$+1$が欲しい場合は最後みたいにする。以上。
　ちなみに$(a,~b,~-a)$が現れる場合、すべての$(a,~b,~c)$は$b^2-ac=D$を満たしているので、
$$D=a^2+b^2$$
が成立する。実は平方数和分解できるすべての$D$はこの方法で平方数和分解することができる。