§A4.16ペル方程式と連分数

証明.$\alpha_1=x_1+y_1\sqrt D$、$\alpha_2=x_2+y_2\sqrt D$とおく。積を展開すると

となる。共役をとると

である。したがって

が成り立つ。仮定より$N(\alpha_1)=N(\alpha_2)=1$であるから、$N(\alpha_1\alpha_2)=1$である。これは主張の整数の組が$x^2-Dy^2=1$を満たすことを意味する。▨

証明.$P_0=0$、$Q_0=1$とし、表示された漸化式によって各項を順に定める。$Q_0$は$D-P_0^2$を割る。$Q_k\mid D-P_k^2$が成り立つとき、$P_{k+1}\equiv-P_k\pmod{Q_k}$であるから、$Q_k\mid D-P_{k+1}^2$である。したがって$Q_{k+1}$は整数である。

$\alpha_k=(\sqrt D+P_k)/Q_k$とおく。$a_k=\lfloor\alpha_k\rfloor$と$P_{k+1}=a_kQ_k-P_k$を用いて分母を有理化すると

となる。$k=1$では$P_1=a_0$、$Q_1=D-a_0^2>0$であり、

は$-1$より大きく$0$より小さい。また$\alpha_1=1/(\sqrt D-a_0)>1$である。$\alpha_k>1$かつ$-1<(P_k-\sqrt D)/Q_k<0$と仮定する。$\alpha_k-a_k$は$0$より大きく$1$より小さいので、

である。また$(P_k-\sqrt D)/Q_k-a_k<-1$であるから$\sqrt D+P_{k+1}>Q_k>0$である。よって$|P_{k+1}|<\sqrt D$であり、$Q_{k+1}=(D-P_{k+1}^2)/Q_k>0$である。さらに

である。右辺の分母は$-1$より小さいので

となる。$\alpha_{k+1}>1$と最後の不等式を加え、$Q_{k+1}>0$を用いると$P_{k+1}>0$が得られる。帰納法により、主張した整数性、正値、整除関係がすべての$k$で成り立つ。

$k\ge1$では、整数$P_k$は$0<P_k<\sqrt D$を満たし、正整数$Q_k$は$D-P_k^2$の約数である。したがって、現れる組$(P_k,Q_k)$の候補は有限個しかない。さらに$-1<(P_k-\sqrt D)/Q_k$から$P_k+Q_k>\sqrt D$である。次の状態$(P',Q')$が分かれば、直前の状態の第二成分は

によって定まる。直前の第一成分$P$は$P\equiv-P'\pmod Q$と$\sqrt D-Q<P<\sqrt D$を満たす。この長さ$Q$の区間には、同じ剰余をもつ整数は高々一つしかない。したがって、状態の移り方には逆向きにも分岐がない。有限個の状態を進む列は、最初の状態$(P_1,Q_1)$へ戻ってから同じ列を繰り返す。

$(P_1,Q_1)=(a_0,D-a_0^2)$の直前の状態では$Q=(D-a_0^2)/Q_1=1$である。また$\sqrt D-1<P<\sqrt D$を満たす整数は$P=a_0$だけである。よって、ある最小の$\ell\ge1$で$(P_\ell,Q_\ell)=(a_0,1)$となり、その次に$(P_1,Q_1)$が再び現れる。$a_k$は状態から一意に定まるので、$a_1,\ldots,a_\ell$が繰り返される。最後に$a_\ell=\lfloor\sqrt D+a_0\rfloor=2a_0$である。▨

証明.$p_k,q_k$の漸化式から

が帰納的に得られる。完全商$\alpha_{k+1}=(\sqrt D+P_{k+1})/Q_{k+1}$を末尾に残して有限連分数を漸化式でまとめると

となる。$\alpha_{k+1}$を代入し、有理数部分と$\sqrt D$の係数を比較すると

を得る。したがって

$Q_{k+1}=1$なら、定理 2.1の証明で得た$\sqrt D-Q_{k+1}<P_{k+1}<\sqrt D$により$P_{k+1}=a_0$である。したがって$Q_{k+1}=1$となるのは$k+1$が$\ell$の正の倍数である場合に限る。$(-1)^{k+1}=1$も必要なので、条件を満たす最小の$k+1$は、$\ell$が偶数なら$\ell$、$\ell$が奇数なら$2\ell$である。

$D=2$では$(P_1,Q_1)=(1,1)$で$\ell=1$であり、指定された添字$k=1$では$p_1/q_1=[1;2]=3/2$、$3^2-2\cdot2^2=1$となる。$D=3$では$(P_1,Q_1)=(1,2)$、$(P_2,Q_2)=(1,1)$で$\ell=2$であり、指定された添字$k=1$では$p_1/q_1=[1;1]=2/1$、$2^2-3\cdot1^2=1$となる。二つの小さい場合でも添字は一致する。▨

証明.定理 2.2が指定する近似分数を$p/q$とすれば、$p^2-Dq^2=1$であり、$p,q$は正整数である。したがって非自明な正整数解が存在する。

正整数解$(x,y)$に対して$x^2-Dy^2=1$なら$\gcd(x,y)=1$であり、

である。ここで、無理数$\theta$、整数$c$、正整数$d$について、既約分数$c/d$が$|\theta-c/d|<1/(2d^2)$を満たすなら、$c/d$は$\theta$の近似分数であることを示す。$\theta$の近似分数を$p_j/q_j$とし、$q_j\le d$となる最大の$j$を取る。このとき$q_j\le d<q_{j+1}$である。$Q=q_j$、$R=q_{j-1}$、$t=[a_{j+1};a_{j+2},\ldots]$、$a=\lfloor t\rfloor$とおくと

かつ$0\le R\le Q$である。連続する近似分数の行列式は$\pm1$なので、ある整数$U,V$が存在して

と書ける。この表示と上の分数表示から

を得る。

$V=0$なら、$c/d$が既約で$d>0$であることから$U=1$であり、$c/d=p_j/q_j$である。$V\ne0$とする。$V<0$なら$d=UQ+VR\ge Q$から$U>0$であり、$2d|U-Vt|\ge2Q(1+t)>Qt+R$である。$V>0$かつ$U\le0$なら$2d|U-Vt|\ge2Qt>Qt+R$である。

$U,V>0$の場合には、$d<aQ+R$から$1\le U\le a-1$である。$2d(Vt-U)$は$V$とともに増加するので、$V=1$の場合を調べれば足りる。$r=R/Q$とおくと、必要な不等式は

である。左辺と右辺の差は$U$について下向きに開く二次式なので、$1\le U\le a-1$における最小値は端点で得られる。$t=a+f$、$0<f<1$と書けば、$U=1$での差は

$U=a-1$での差は

である。したがって$V\ne0$のすべての場合に

となる。仮定に反するので$V=0$であり、$c/d$は近似分数である。

この近似判定により、ペル方程式のすべての正整数解$x/y$は$\sqrt D$の近似分数に現れる。定理 2.2は値$1$を初めて与える添字を特定しているので、そこで得る解を$\varepsilon=x_1+y_1\sqrt D$とすれば、$x_1+y_1\sqrt D>1$は正整数解の中で最小である。実際、$t>1$に対して$(t-t^{-1})/(2\sqrt D)$は狭義に増加し、解では$y=(t-t^{-1})/(2\sqrt D)$であるから、より小さい解はより小さい分母をもつ。近似分数の分母は漸化式により添字とともに増加し、指定された近似分数より小さい分母はそれより前の添字にしか現れない。したがって、そのような解は存在しない。

$\alpha=x+y\sqrt D$を任意の正整数解とする。$\varepsilon>1$であり、$\varepsilon^n\ge1+n(\varepsilon-1)$であるから、ある整数$r\ge0$が存在して

となる。$\varepsilon^r=A+B\sqrt D$と書けば$\varepsilon^{-r}=A-B\sqrt D$であり、

は整数係数をもち、$1\le\beta<\varepsilon$かつ$\beta\bar\beta=1$を満たす。$\beta=X+Y\sqrt D$と書くと

である。$\beta>1$なら$(X,Y)$は基本解より小さい非自明な正整数解となるので、基本解の最小性に反する。よって$\beta=1$であり、$\alpha=\varepsilon^r$である。

最後に、非自明な整数解$(x,y)$では$x$と$y$はともに$0$でない。方程式は$x$と$y$のそれぞれの符号を変えても保たれるので、$(|x|,|y|)$に正整数解の分類を適用できる。これに自明解$(\pm1,0)$を加えると、主張した整数解全体が得られる。▨