Legendreの定理(連分数)

$\alpha$ は無理数なので $\alpha-p/q\ne0$ である。連分数 の定理「有理数の連分数展開」の 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=p$、$Q_n=q$ である。
$\alpha-p/q=(-1)^n\theta/q^2$（$0< \theta< \frac12$）と書き、
$$ \omega:=\frac1\theta-\frac{Q_{n-1}}{q} $$
とおく。$Q_{n-1}\le Q_n=q$（$n=0$ では $Q_{-1}=0$）なので $\omega>2-1=1$ である。$P_{n-1}Q_n-P_nQ_{n-1}=(-1)^n$（連分数 の命題「隣り合う収束子の行列式」）と $\omega q+Q_{n-1}=q/\theta$ から
$$ \frac{\omega P_n+P_{n-1}}{\omega Q_n+Q_{n-1}}-\frac{P_n}{Q_n}=\frac{P_{n-1}Q_n-P_nQ_{n-1}}{Q_n(\omega Q_n+Q_{n-1})}=\frac{(-1)^n}{q\cdot q/\theta}=\alpha-\frac pq $$
となり、
$$ \alpha=\frac{\omega P_n+P_{n-1}}{\omega Q_n+Q_{n-1}} $$
である。$\omega$ が有理数なら右辺も有理数になるので、$\omega$ は無理数である。
$\omega$ の連分数展開を $\omega=[c_0;c_1,c_2,\dots]$ とすると、$\omega>1$ から $c_0\ge1$ である。$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>0$ の関数として連続（分母が正）なので、右辺は $\alpha$ に収束する。したがって $\alpha$ は無限単純連分数 $[b_0;b_1,\dots,b_n,c_0,c_1,\dots]$ の値である（$b_1,\dots,b_n\ge1$、$c_0\ge1$ なので単純連分数である）。連分数 の定理「無理数の連分数展開」の 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$ である。$\square$

Diophantus近似 の定義「Diophantus 近似の基本用語」の意味で、$(p,q)$ が $\alpha$ の最良近似であることを示す。$1\le q'\le q$、$(p',q')\ne(p,q)$ で $|q'\alpha-p'|\le|q\alpha-p|$ となる整数の組があったとする。$p'/q'=p/q$ なら、$\gcd(p,q)=1$ から $(p',q')=k(p,q)$（$k\ge1$ は整数）で、$q'\le q$ から $k=1$ となり矛盾する。よって $p'/q'\ne p/q$ であり、$|p'q-pq'|\ge1$ から $|p/q-p'/q'|\ge1/(qq')$ である。一方
$$ \left|\alpha-\frac{p'}{q'}\right|=\frac{|q'\alpha-p'|}{q'}\le\frac{|q\alpha-p|}{q'}< \frac{1}{2qq'},\qquad\left|\alpha-\frac pq\right|< \frac1{2q^2}\le\frac1{2qq'} $$
なので、三角不等式から $|p/q-p'/q'|<1/(qq')$ となり、矛盾する。よって $(p,q)$ は最良近似であり、同記事の定理「収束子は最良近似である」の 3 により、ある $n\ge0$ について $(p,q)=(p_n,q_n)$ である。$\square$

$\alpha$ は $p_n/q_n$ と $p_{n+1}/q_{n+1}$ の真に間にあるので（連分数 の定理「無限単純連分数の収束」）、命題「隣り合う収束子の行列式」から
$$ \left|\alpha-\frac{p_n}{q_n}\right|+\left|\alpha-\frac{p_{n+1}}{q_{n+1}}\right|=\left|\frac{p_{n+1}}{q_{n+1}}-\frac{p_n}{q_n}\right|=\frac{1}{q_nq_{n+1}} $$
である。どちらも不等式をみたさないとすると、左辺は $\frac1{2q_n^2}+\frac1{2q_{n+1}^2}$ 以上であり、相加平均と相乗平均の不等式からこれは $\frac1{q_nq_{n+1}}$ 以上なので、すべての不等号は等号でなければならない。とくに $|\alpha-p_n/q_n|=1/(2q_n^2)$ となるが、左辺は無理数、右辺は有理数なので矛盾する。後半は前半と thm-ltcf-main による。$\square$

正の整数 $m,k$ について、部分商が $0,m,2,k,k,k,\dots$ の無理数 $\alpha=[0;m,2,k,k,\dots]$ と $p/q=1/(m+1)$ を考える。収束子の分母は $q_0=1$、$q_1=m$、$q_2=2m+1$ で、$n\ge1$ で増加するので、$m< m+1<2m+1$ から $1/(m+1)$ は収束子でない（既約な収束子の値が $1/(m+1)$ なら分母は $m+1$ である）。第 2 完全商を $x=x_2=[2;k,k,\dots]$ とすると $2< x<2+\frac1k$ であり、$p_0=0$、$p_1=1$、$q_0=1$、$q_1=m$ から $\alpha=\dfrac{x}{xm+1}$ である。よって
$$ (m+1)^2\left|\alpha-\frac1{m+1}\right|=\frac{(x-1)(m+1)}{xm+1}< \frac{(1+\frac1k)(m+1)}{2m+1} $$
で、右辺は $m,k\to\infty$ で $\frac12$ に収束する。$m,k$ を大きくとれば右辺は $c$ より小さい。$\square$

$a_0\ge1$ なので $[0;a_0,a_1,\dots]$ は無限単純連分数で、有限連分数の定義から $[0;a_0,\dots,a_n]=1/[a_0;\dots,a_n]=q_n/p_n$ である。$n\to\infty$ とすると値は $1/\alpha$ なので、連分数 の定理「無理数の連分数展開」の 2 によりこれが $1/\alpha$ の展開である。$p_n\ge a_0\ge1$ で $\gcd(p_n,q_n)=1$ なので、$q_n/p_n$ は既約な表示であり、収束子の分子と分母そのものである。$\square$

$N:=x^2-dy^2$ とおく。$\sqrt d$ は無理数なので $N\ne0$ である。
$N>0$ のとき：$x>y\sqrt d$ なので $x+y\sqrt d>2y\sqrt d$ であり、
$$ 0< \frac xy-\sqrt d=\frac{N}{y(x+y\sqrt d)}< \frac{N}{2y^2\sqrt d}< \frac1{2y^2} $$
である。thm-ltcf-main により $x/y$ は $\sqrt d$ の収束子である。
$N<0$ のとき：$y\sqrt d>x$ なので $x+y\sqrt d>2x$ であり、
$$ 0< \frac yx-\frac1{\sqrt d}=\frac{y\sqrt d-x}{x\sqrt d}=\frac{|N|}{x\sqrt d\,(x+y\sqrt d)}< \frac{|N|}{2x^2\sqrt d}< \frac1{2x^2} $$
である。$1/\sqrt d$ は無理数で $\gcd(y,x)=1$ なので、thm-ltcf-main により $y/x$ は $1/\sqrt d$ の収束子である。$y\ge1$ なので第 $0$ 収束子 $0/1$ ではなく、lem-ltcf-reciprocal（$\alpha=\sqrt d>1$）により $y=q_n$、$x=p_n$ となる $n\ge0$ がある。$\square$