Pell方程式

1：$d=0$ なら方程式は $x^2=1$ である。$d=k^2$、$k\geq1$ とすると $(x-ky)(x+ky)=1$ であり、整数の積が $1$ なので $x-ky=x+ky=\pm1$ である。よって $2ky=0$、すなわち $y=0$、$x=\pm1$ である。
2：$d<0$ なら $x^2-dy^2=x^2+|d|y^2$ である。$d=-1$ では $x^2+y^2=1$ の整数解は 4 つである。$d\leq-2$ で $y\neq0$ なら左辺は $|d|\geq2$ 以上になるので $y=0$、$x=\pm1$ である。

$\alpha\beta=(ac+dbe)+(ae+bc)\sqrt d$ であり、$\alpha'\beta'=(a-b\sqrt d)(c-e\sqrt d)=(ac+dbe)-(ae+bc)\sqrt d=(\alpha\beta)'$ である。よって $N(\alpha\beta)=\alpha\beta\,(\alpha\beta)'=\alpha\alpha'\,\beta\beta'=N(\alpha)N(\beta)$ であり、これを $a,b,c,e$ で書いたものが恒等式である。

鳩の巣原理 の記事の定理「Dirichlet の近似定理」により、任意の整数 $N\geq1$ について $1\leq Y\leq N$、$|Y\sqrt d-X|<1/N$ を満たす整数 $X,Y$ がある。このとき $|X-Y\sqrt d|<1/N\leq1/Y$ である。
このような組が無限にあることを示す。組 $(X,Y)$ が得られたとすると、$\sqrt d$ は無理数なので $\delta:=|X-Y\sqrt d|>0$ である。$N>1/\delta$ として同じ定理を使うと $|X_1-Y_1\sqrt d|<1/N<\delta$ を満たす組 $(X_1,Y_1)$ が得られ、これは $(X,Y)$ と異なる。これを繰り返すと、$|X-Y\sqrt d|<1/Y$ を満たす相異なる組 $(X,Y)$（$Y\geq1$）が無限に得られる。$X>Y\sqrt d-1/Y\geq\sqrt2-1>0$ なので $X$ も正である。
各組について、三角不等式から $|X+Y\sqrt d|\leq|X-Y\sqrt d|+2Y\sqrt d<\dfrac1Y+2Y\sqrt d$ なので
$$ |X^2-dY^2|=|X-Y\sqrt d|\,|X+Y\sqrt d|<\frac1Y\Bigl(\frac1Y+2Y\sqrt d\Bigr)=\frac{1}{Y^2}+2\sqrt d\leq1+2\sqrt d $$
である。

lem-pell-equation-small-values の無限個の組 $(X,Y)$ について、$m:=X^2-dY^2$ は $|m|< M$ を満たす整数であり、$\sqrt d$ が無理数なので $m\neq0$ である。$m$ のとりうる値は有限個なので、ある $m\neq0$ について $X^2-dY^2=m$ を満たす正の整数の組が無限に存在する。これらの組の $(X\bmod|m|,\ Y\bmod|m|)$ は高々 $m^2$ 通りなので、相異なる 2 つの組 $(X_1,Y_1)$、$(X_2,Y_2)$ で $X_1\equiv X_2$、$Y_1\equiv Y_2\pmod{|m|}$ を満たすものがある。
$\alpha:=X_1+Y_1\sqrt d$、$\beta:=X_2+Y_2\sqrt d$ とおき、$\alpha\beta'=X+Y\sqrt d$ と書くと
$$ X=X_1X_2-dY_1Y_2,\qquad Y=X_2Y_1-X_1Y_2 $$
である。合同式で $X_2,Y_2$ を $X_1,Y_1$ に置き換えると
$$ X\equiv X_1^2-dY_1^2=m\equiv0,\qquad Y\equiv X_1Y_1-X_1Y_1=0\pmod{|m|} $$
となるので、$X=mx$、$Y=my$ となる整数 $x,y$ がある。lem-pell-equation-composition より $X^2-dY^2=N(\alpha)N(\beta')=m\cdot m=m^2$ であり（$N(\beta')=\beta'\beta=N(\beta)$）、一方 $X^2-dY^2=m^2(x^2-dy^2)$ なので、$m^2\neq0$ で割って $x^2-dy^2=1$ を得る。
$y\neq0$ を示す。$y=0$ なら $X_2Y_1=X_1Y_2$ であり、$r:=X_1/X_2>0$ とおくと $Y_1=rY_2$ である。すると $m=X_1^2-dY_1^2=r^2(X_2^2-dY_2^2)=r^2m$ から $r^2=1$、$r=1$ となり、$(X_1,Y_1)=(X_2,Y_2)$ となって 2 つの組が相異なることに反する。よって $y\neq0$ であり、$(|x|,|y|)$ は正の解である。

$(x,y)$ が正の解なら $\alpha\geq1+\sqrt d>1$ である。逆に $\alpha>1$ とすると、$\alpha\alpha'=1$ より $0<\alpha'=1/\alpha<1$ である。よって $x=(\alpha+\alpha')/2>1/2$、$y\sqrt d=(\alpha-\alpha')/2>0$ であり、$x,y$ は整数なので $x\geq1$、$y\geq1$ である。

1：$\varepsilon^{-1}=\varepsilon'=x_1-y_1\sqrt d$ であり、$\varepsilon$ と $\varepsilon^{-1}$ はどちらも $\mathbb{Z}[\sqrt d]$ に属して $N=1$ を満たす。lem-pell-equation-composition により $N=1$ の元の積は $N=1$ の元なので、$\varepsilon^n$（$n\in\mathbb{Z}$）と $-\varepsilon^n$ は $N=1$ の元であり、その係数は解を与える。
2：$(x,y)$ を解とし、$\alpha=x+y\sqrt d$ とおく。$\alpha\alpha'=1$ なので $\alpha\neq0$ であり、必要なら $-\alpha$（解 $(-x,-y)$ に対応）に取り替えて $\alpha>0$ としてよい。$\varepsilon>1$ なので、$\varepsilon^n\leq\alpha<\varepsilon^{n+1}$ を満たす整数 $n$ がある。$\gamma:=\alpha\varepsilon^{-n}$ は 1 と同じ理由で $\mathbb{Z}[\sqrt d]$ に属して $N(\gamma)=1$ を満たし、$1\leq\gamma<\varepsilon$ である。$\gamma>1$ なら lem-pell-equation-sign により $\gamma$ は正の解に対応し、$\gamma<\varepsilon$ は基本解の最小性に反する。よって $\gamma=1$、$\alpha=\varepsilon^n$ である。
正の解では lem-pell-equation-sign により $\alpha>1$ なので $n\geq1$ である。逆に $n\geq1$ なら $\varepsilon^n>1$ なので $(x_n,y_n)$ は正の解である。$\varepsilon>1$ より $\varepsilon^n$ は $n$ について狭義に増加するので、これらは相異なる。

$\varepsilon^{n+1}=\varepsilon\cdot\varepsilon^n=(x_1+y_1\sqrt d)(x_n+y_n\sqrt d)$ を展開して係数を比べると漸化式を得る。また $(\varepsilon^n)'=(\varepsilon')^n=\varepsilon^{-n}$（lem-pell-equation-composition）なので $x_n-y_n\sqrt d=\varepsilon^{-n}$ であり、$x_n+y_n\sqrt d=\varepsilon^n$ と足したり引いたりすると一般項を得る。$0<\varepsilon^{-n}/2<1/2$ なので $x_n$ は $\varepsilon^n/2$ にもっとも近い整数である。

$\alpha$ は無理数なので $\alpha-p/q\neq0$ である。連分数 の記事の定理「有理数の連分数展開」の 3 により、$p/q$ は長さが $1$ だけ異なる 2 通りの単純連分数で表せるので、そのうち $(-1)^n$ が $\alpha-p/q$ と同じ符号になる表示 $p/q=[b_0;b_1,\dots,b_n]$ を選ぶ。この表示の収束子を $P_k/Q_k$ とする。$P_n/Q_n=p/q$ で、単純連分数の収束子は既約分数であり $Q_n>0$ なので、$P_n=p$、$Q_n=q$ である。
$\alpha-p/q=(-1)^n\theta/q^2$、$0<\theta<\frac12$ と書き、$\omega:=\dfrac1\theta-\dfrac{Q_{n-1}}{q}$ とおく。$Q_{n-1}\leq Q_n=q$（$n=0$ なら $Q_{-1}=0$）なので $\omega>2-1=1$ である。連分数 の記事の命題「隣り合う収束子の行列式」の $P_{n-1}Q_n-P_nQ_{n-1}=(-1)^n$ を使うと
$$ \frac{\omega P_n+P_{n-1}}{\omega Q_n+Q_{n-1}}-\frac{P_n}{Q_n}=\frac{(-1)^n}{q(\omega q+Q_{n-1})}=\frac{(-1)^n}{q\cdot q/\theta}=\frac{(-1)^n\theta}{q^2}=\alpha-\frac pq $$
であり、$\alpha=\dfrac{\omega P_n+P_{n-1}}{\omega Q_n+Q_{n-1}}$ である。$\omega$ が有理数なら $\alpha$ も有理数になるので、$\omega$ は無理数である。
$\omega$ の連分数展開を $\omega=[c_0;c_1,c_2,\dots]$ とすると、$\omega>1$ より $c_0\geq1$ である。$t_k:=[c_0;c_1,\dots,c_k]>0$ とおくと、連分数の定義から $[b_0;\dots,b_n,t_k]=[b_0;\dots,b_n,c_0,\dots,c_k]$ であり、連分数 の記事の命題「収束子の漸化式」により
$$ [b_0;\dots,b_n,c_0,\dots,c_k]=\frac{t_kP_n+P_{n-1}}{t_kQ_n+Q_{n-1}} $$
である。$k\to\infty$ で $t_k\to\omega$ であり、右辺は $t$ の関数として $t=\omega$ で連続（分母が正）なので、右辺は $\alpha$ に収束する。したがって $\alpha$ は無限単純連分数 $[b_0;b_1,\dots,b_n,c_0,c_1,\dots]$ の値である。連分数 の記事の定理「無理数の連分数展開」の 2 により、$\alpha$ の連分数展開の部分商はちょうど $b_0,\dots,b_n,c_0,c_1,\dots$ であり、その第 $n$ 収束子は $[b_0;\dots,b_n]=p/q$ である。収束子は既約分数で分母が正なので $p=p_n$、$q=q_n$ である。

$x$ と $y$ の公約数は $x^2-dy^2=1$ を割り切るので $\gcd(x,y)=1$ である。$x-y\sqrt d=\dfrac{1}{x+y\sqrt d}>0$ なので $x>y\sqrt d$、したがって $x+y\sqrt d>2y\sqrt d$ であり、
$$ 0<\frac xy-\sqrt d=\frac{1}{y(x+y\sqrt d)}<\frac{1}{2y^2\sqrt d}<\frac{1}{2y^2} $$
である。lem-pell-equation-legendre により $x=p_n$、$y=q_n$ となる $n$ がある。
後半：正の解では $x=\sqrt{1+dy^2}$ なので、$x+y\sqrt d$ は $y$ について狭義に増加し、基本解は $y$ が最小の正の解である。基本解を $(p_j,q_j)$ とする。$k< j$ で $p_k^2-dq_k^2=1$ となるものがあったとすると、$\sqrt d>1$ より $a_0\geq1$ なので $p_k\geq1$、$q_k\geq1$ で、$(p_k,q_k)$ は正の解である。$q_k\leq q_j$（分母は $n$ について減少しない）と $y$ の最小性から $q_k=q_j$、したがって $p_k=p_j$ となり、$p_k/q_k=p_j/q_j$ となる。ところが無理数の相異なる収束子は相異なる値をもつので（連分数 の記事の定理「無理数の連分数展開」の直後の段落）$k=j$ となり、矛盾する。