循環連分数

要点：2 次方程式の解の公式で、$D$ を判別式にとる。

要点：$k$ に関する帰納法で、$1/(\alpha_k-a_k)$ の分母を有理化する。

要点：1 は $\alpha_{k+1}'=1/(\alpha_k'-a_k)$ と $a_k\ge1$ から、2 は $\alpha\pm\alpha'$ の符号から従う。

$\alpha$ を lem-pcf-standard-form の形に書き、$\sigma$ をその $\mathbb{Q}(\sqrt D)$ の共役とする。$k\ge2$ とし、$c_n:=p_n/q_n$ とおく。$\alpha=\frac{\alpha_kp_{k-1}+p_{k-2}}{\alpha_kq_{k-1}+q_{k-2}}$ を $\alpha_k$ について解くと（$\alpha q_{k-1}-p_{k-1}\neq0$ は $\alpha$ が無理数であることによる）
$$ \alpha_k=-\frac{\alpha q_{k-2}-p_{k-2}}{\alpha q_{k-1}-p_{k-1}} $$
であり、両辺に $\sigma$ を施すと
$$ \alpha_k'=-\frac{\alpha'q_{k-2}-p_{k-2}}{\alpha'q_{k-1}-p_{k-1}}=-\frac{q_{k-2}}{q_{k-1}}\cdot\frac{\alpha'-c_{k-2}}{\alpha'-c_{k-1}} $$
となる（$k\ge2$ なので $q_{k-2},q_{k-1}>0$）。$c_n\to\alpha$ であり（連分数 の記事の定理「無理数の連分数展開」）、$\alpha'\neq\alpha$ なので、最後の分数は $k\to\infty$ で $1$ に収束する。よって、ある $K_0\ge2$ があって $k\ge K_0$ で $\alpha_k'<0$ である。このとき $k\ge K_0$ について $\alpha_{k+1}>1$、$a_k\ge1$ であり、prf-pcf-reduced の 1 と同じ計算で $\alpha_{k+1}'=1/(\alpha_k'-a_k)\in(-1,0)$ となる。$K:=K_0+1$ とすればよい。$\square$

循環するなら 2次無理数． $k\ge m$ で $a_{k+h}=a_k$ とし、$\beta:=\alpha_m$ とおく。$\beta=\alpha_{m+h}=[a_m;\dots,a_{m+h-1},\beta]$ である。有限列 $a_m,\dots,a_{m+h-1}$ の収束子の分子・分母を $P,P',Q,Q'$（第 $h-1$・第 $h-2$ のもの）とすると、連分数 の記事の命題「収束子の漸化式」により $\beta=\frac{\beta P+P'}{\beta Q+Q'}$、すなわち
$$ Q\beta^2+(Q'-P)\beta-P'=0 $$
であり、$Q\ge1$ なので $\beta$ は 2次無理数である。2 次方程式の解の公式から、有理数 $u,w$（$w\neq0$）と平方数でない正の整数 $E$ で $\beta=u+w\sqrt E$ と書ける。$m=0$ なら $\alpha=\beta$ である。$m\ge1$ なら $\alpha=\frac{\beta p_{m-1}+p_{m-2}}{\beta q_{m-1}+q_{m-2}}$ は $\beta$ の有理式なので、体 $\mathbb{Q}(\sqrt E)$ に属し、$\alpha=r+s\sqrt E$（$r,s\in\mathbb{Q}$）と書ける。$\alpha$ は無理数なので $s\neq0$ であり、$\alpha$ は $(t-r)^2-s^2E=0$ の根である。分母を払えば整数係数の 2 次方程式を得るので、$\alpha$ は 2次無理数である。
2次無理数なら循環する． $\alpha$ を lem-pcf-standard-form の形に書き、lem-pcf-pq により $\alpha_k=(P_k+\sqrt D)/Q_k$ とする。lem-pcf-eventually-reduced により $k\ge K$ の $\alpha_k$ は被約で、lem-pcf-reduced の 2 により組 $(P_k,Q_k)$（$k\ge K$）は有限個の値しかとらない。よって $K\le m< m+h$ で $(P_m,Q_m)=(P_{m+h},Q_{m+h})$、すなわち $\alpha_m=\alpha_{m+h}$ となるものがあり、展開は $m$ から周期 $h$ で循環する。$\square$

要点：$\beta_k'=b_k+1/\beta_{k+1}'$ が $(-1,0)$ にあることから $b_k$ が決まる。

純循環なら被約で、2 が成り立つ． $\alpha=[\overline{a_0;\dots,a_{h-1}}]$ とする。$a_0=a_h\ge1$ なので部分商はすべて正で、$\alpha=a_0+1/\alpha_1>a_0\ge1$ である。列 $a_0,\dots,a_{h-1}$ の収束子を $p_n/q_n$ とすると、$\alpha=[a_0;\dots,a_{h-1},\alpha]$ から $f(\alpha)=0$、ここで
$$ f(t):=q_{h-1}t^2+(q_{h-2}-p_{h-1})t-p_{h-2} $$
である。$q_{h-1}>0$ であり、$\alpha$ は無理数なので 2次無理数で、$\alpha'$ は $f$ のもう一つの根である。部分商がすべて正なので、$n\ge-1$ で $p_n\ge1$ であり、$q_n$ は $n\ge-1$ で減少しない（$q_{-1}=0< q_0=1$、$n\ge1$ で $q_n\ge q_{n-1}$）。また $p_{h-1}-p_{h-2}=(a_{h-1}-1)p_{h-2}+p_{h-3}$ は、$h\ge2$ なら $p_{h-3}$ 以上なので $1$ 以上であり、$h=1$ なら $a_0-1\ge0$ である。よって
$$ f(0)=-p_{h-2}<0,\qquad f(-1)=(q_{h-1}-q_{h-2})+(p_{h-1}-p_{h-2})>0 $$
であり（$h=1$ でも $f(-1)=1+(a_0-1)>0$）、$f$ は $(-1,0)$ に根をもつ。もう一つの根は $\alpha>1$ なので、$-1<\alpha'<0$ であり、$\alpha$ は被約である。
逆順の展開 $\gamma:=[\overline{a_{h-1};\dots,a_0}]$ は、上の等式により $\gamma=\frac{p_{h-1}\gamma+q_{h-1}}{p_{h-2}\gamma+q_{h-2}}$、すなわち $g(\gamma)=0$、$g(s):=p_{h-2}s^2+(q_{h-2}-p_{h-1})s-q_{h-1}$ を満たし、前段と同じ理由で $\gamma>1$ である。$s\neq0$ について $f(-1/s)=-g(s)/s^2$ なので、$g$ の 2 つの根は $-1/\alpha\in(-1,0)$ と $-1/\alpha'>1$ である。よって $\gamma=-1/\alpha'$ であり、2 が成り立つ。
被約なら純循環する． $\alpha$ が被約なら、lem-pcf-reduced の 1 によりすべての完全商が被約である。thm-pcf-lagrange により $\alpha_m=\alpha_{m+h}$ となる $m\ge0$、$h\ge1$ がある。$m\ge1$ なら、lem-pcf-predecessor により $\alpha_{m-1}=\alpha_{m+h-1}$ であり、これを繰り返すと $\alpha_0=\alpha_h$ を得る。よって展開は純循環する。$\square$

$\beta:=\sqrt d+a_0$ は、$\beta>1$、$\beta'=a_0-\sqrt d\in(-1,0)$ なので被約であり、thm-pcf-galois により純循環する。$\beta$ の部分商を $b_k$、完全商を $\beta_k$ とする。$2a_0<\beta<2a_0+1$ から $b_0=2a_0$、$\beta-b_0=\sqrt d-a_0=\alpha-a_0$ なので $\beta_1=\alpha_1$ であり、$k\ge1$ で $b_k=a_k$、$\beta_k=\alpha_k$ である。$\beta$ が周期 $h$ で純循環すれば $a_{k+h}=a_k$（$k\ge1$）なので、$(a_k)_{k\ge1}$ は $k=1$ から循環する。
逆に $\ell$ について、$\beta_1=\beta_{1+\ell}$（展開が等しい）である。すべての $\beta_k$ は被約なので、lem-pcf-predecessor により $\beta_0=\beta_\ell$、すなわち $a_\ell=b_\ell=b_0=2a_0$ である。よって $b$ は周期 $\ell$ で純循環し、上の段落から $b$ の周期は $(a_k)_{k\ge1}$ の周期でもあるので、$\ell$ が $b$ の最小の周期である。これで 1 が示された。
2：$-1/\beta'=1/(\sqrt d-a_0)=\alpha_1=[\overline{a_1;\dots,a_{\ell-1},2a_0}]$ である。一方 thm-pcf-galois の 2 を $\beta=[\overline{2a_0;a_1,\dots,a_{\ell-1}}]$ に使うと $-1/\beta'=[\overline{a_{\ell-1};a_{\ell-2},\dots,a_1,2a_0}]$ である。展開は一意なので、部分商を比べて $a_k=a_{\ell-k}$（$1\le k\le\ell-1$）を得る。$\square$

1：$\sqrt d=\frac{\alpha_kp_{k-1}+p_{k-2}}{\alpha_kq_{k-1}+q_{k-2}}$ に $\alpha_k=(P_k+\sqrt d)/Q_k$ を代入して分母を払うと、$\sqrt d\bigl((P_k+\sqrt d)q_{k-1}+Q_kq_{k-2}\bigr)=(P_k+\sqrt d)p_{k-1}+Q_kp_{k-2}$ である。$1$ と $\sqrt d$ の係数を比べて
$$ dq_{k-1}=P_kp_{k-1}+Q_kp_{k-2},\qquad p_{k-1}=P_kq_{k-1}+Q_kq_{k-2} $$
を得る。前者に $q_{k-1}$、後者に $p_{k-1}$ を掛けて引くと、$p_{k-1}^2-dq_{k-1}^2=Q_k(p_{k-1}q_{k-2}-p_{k-2}q_{k-1})=(-1)^kQ_k$ である（連分数 の記事の命題「隣り合う収束子の行列式」）。
2：$k\ge1$ の $\alpha_k=\beta_k$ は被約なので、lem-pcf-reduced の 2 により $Q_k>0$ である。$Q_k=1$ なら $\alpha_k=P_k+\sqrt d$ で、$-1<\alpha_k'=P_k-\sqrt d<0$ から $P_k=a_0$、すなわち $\beta_k=\beta_0$ である。逆に $\beta_k=\beta_0$ なら、$\sqrt d$ の係数を比べて $Q_k=1$ である。$\beta_k=\beta_0$ は $b_k,b_{k+1},\dots$ と $b_0,b_1,\dots$ が一致すること、すなわち $k$ が $b$ の周期であることと同値で、$b$ の最小の周期は $\ell$ なので、これは $\ell\mid k$ と同値である（$k=q\ell+r$、$0\le r<\ell$ なら $r$ も周期になり、最小性から $r=0$）。
3：2 により $Q_k\ge2$ なので、$P_k<\sqrt d$（lem-pcf-reduced の 2）と合わせて $a_k=\lfloor(P_k+\sqrt d)/Q_k\rfloor<\sqrt d$、よって $a_k\le a_0$ である。$\square$

1：Pell方程式 の記事の命題「正の解は収束子である」により、正の解はある $n\ge0$ について $(p_n,q_n)$ である。$k:=n+1$ とすると prop-pcf-sqrt-pq の 1・2 により $p_n^2-dq_n^2=(-1)^kQ_k$、$Q_k>0$ なので、これが $1$ になるのは $Q_k=1$ かつ $k$ が偶数、すなわち $\ell\mid k$ かつ $k$ が偶数のときである。正の解 $(x,y)$ では $x+y\sqrt d$ は $x$ について増加し、$p_n$ は $n\ge0$ で狭義に増加する（$p_n-p_{n-1}=(a_n-1)p_{n-1}+p_{n-2}>0$）ので、基本解は条件を満たす最小の $k$、すなわち $\ell$ が偶数なら $k=\ell$、奇数なら $k=2\ell$ に対応する。
2：$(x,y)$ を正の解とすると、$x^2=dy^2-1\ge2y^2-1\ge y^2$ から $x\ge y$ で、$\gcd(x,y)=1$ である。$\sqrt d-x/y=1/\bigl(y(y\sqrt d+x)\bigr)$ と $y\sqrt d+x\ge(\sqrt2+1)y>2y$ から $|\sqrt d-x/y|<1/(2y^2)$ なので、Pell方程式 の記事の補題「収束子であるための十分条件」により $(x,y)=(p_n,q_n)$ となる $n$ がある。1 と同様に、値 $-1$ をとるのは $\ell\mid k$ かつ $k$ が奇数のときで、そのような $k$ があることと $\ell$ が奇数であることは同値である。$x$ か $y$ が $0$ の整数解はない（$y=0$ なら $x^2=-1$、$x=0$ なら $dy^2=1$）ので、整数解があれば符号を変えて正の解が得られる。$\square$