§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$である。▨

証明. 完全商$\alpha_{k+1}=(\sqrt D+P_{k+1})/Q_{k+1}$に§A4.11 命題 3.2を適用すると

となる。$\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$となる。二つの小さい場合でも添字は一致する。▨

証明.$\theta=[a_0;a_1,a_2,\ldots]$の近似分数の分子と分母を、§A4.11 命題 3.2の漸化式によって$p_k,q_k$と定める。$q_0=1$、$q_1=a_1\ge1$であり、$k\ge0$では$q_{k+2}\ge q_{k+1}+q_k$である。したがって、$q_k$は広義に増加し、上に有界でない。$q_j\le d$を満たす最大の添字$j\ge0$を取ると、$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$とおく。§A4.11 命題 3.2により

であり、$0\le R\le Q$である。$p_jR-p_{j-1}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$であり、$a\ge2$である。$V\ge1$では$UQ+VR>0$、$Vt-U\ge t-U>0$であり、前者は$V$とともに減少せず、後者は狭義に増加する。したがって、$2(UQ+VR)(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$は近似分数である。▨

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

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

である。補題 3.1により、ペル方程式のすべての正整数解$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)$であるから、より小さい解はより小さい分母をもつ。近似分数の分母は漸化式により添字とともに広義に増加し、指定された近似分数より小さい分母はそれより前の添字にしか現れない。したがって、そのような解は存在しない。

定理 1.2の合成式により、$\varepsilon$のすべての正整数乗は正整数係数をもち、$N(\varepsilon^n)=1$（$n\ge1$）を満たす。$\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$である。$\alpha>1$なので、$r\ge1$である。

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