12.ユークリッド互除法と近似分数

12.3 近似分数(2)

$\dfrac{b}{a}$<$\dfrac{d}{c},ad-bc=1$
のとき,既約分数$\frac{y}{x}$が
$\dfrac{b}{a}$<$\dfrac{y}{x}$<$\dfrac{d}{c}$・・・@
を満たすとき,正の整数$m,n$を用いて
$x=ma+nc,y=mb+nd$・・・A
と表せるか.
について調べます.

まず,Aの$m,n$と$x,y$の関係を調べます.
$\begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} a & c \\ b & d \end{pmatrix} \begin{pmatrix} m \\ n \end{pmatrix}$
が成り立つ.さらに$ad-bc=1$より
$\begin{pmatrix} a & c \\ b & d \end{pmatrix} ^{-1} =\begin{pmatrix} d & -c \\ -b & a \end{pmatrix}$
より
$\begin{pmatrix} m \\ n \end{pmatrix} = \begin{pmatrix} d & -c \\ -b & a \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix}$
$\therefore m=dx-cy, \ \ n=-bx+ay$
さらに@より
$dx-cy$>$0, \ -bx+ay$>$0$
したがって,@を満たす任意の既約分数$\frac{y}{x}$はある正の整数$m,n$が存在して,
$\dfrac{y}{x}=\dfrac{mb+nd}{ma+nc}$
と表せることが分かりました.
すなわち,次の命題が分かりました.

命題
2つの既約分数$\frac{b}{a},\frac{d}{c} \ \ (\frac{b}{a}$<$\frac{d}{c})$の分子,分母の間に$ad-bc=1$なる関係があるとき
$\dfrac{b}{a}$<$\dfrac{y}{x}$<$\dfrac{d}{c}$
を満たすどのような既約分数$\frac{y}{x}$に対しても,正の整数$m,n$が存在して,
$\dfrac{y}{x}=\dfrac{mb+nd}{ma+nc}$
と表せる.

この命題より次の性質は簡単に分かる.


2つの既約分数$\frac{b}{a},\frac{d}{c} \ \ (\frac{b}{a}$<$\frac{d}{c})$の分子,分母の間に$ad-bc=1$なる関係があるとき
$\dfrac{b}{a}$<$\dfrac{y}{x}$<$\dfrac{d}{c}$
を満たす既約分数$\frac{y}{x}$のうちで,分母が最小のものは,
$\dfrac{y}{x}=\dfrac{b+d}{a+c}$
である.


さて,話を戻そう.
すでに調べたことは
無理数$x$が
$x=[q_0;q_1,q_2,\dots ]$
と連分数展開されるとき,$x$の近似分数の列$\left \{x_n=\dfrac{b_n}{a_n}\right\}$は
$a_{n+1}=q_{n+1}a_n+a_{n-1},b_{n+1}=q_{n+1}b_n+b_{n-1}$
ただし,$a_{-1}=0,a_0=1,b_{-1}=1,b_0=q_0$ で与えられる.さらに
$x_{n+1}-x_n=\dfrac{b_{n+1}}{a_{n+1}}-\dfrac{b_n}{a_n}=\dfrac{(-1)^n}{a_na_{n+1}}$
である.

次に$x$とその近似分数との差を求めよう.
$x_n=[q_0;q_1,q_2,\dots ,q_n]$
であり,実数$\gamma$を
$x=[q_0;q_1,q_2,\dots ,q_n,\gamma]$
によって定義すれば,$x$は$x$の近似分数
$x_{n+1}=[q_0;q_1,q_2,\dots ,q_n,q_{n+1}]$
の$q_{n+1}$に$\gamma$を代入したものである.
$\alpha =a_n\gamma +a_{n-1},\beta=b_n\gamma +b_{n-1}$
で$\alpha ,\beta$を定義すれば
$x=\dfrac{\beta}{\alpha}$
である.
$x_n-x=\dfrac{b_n}{a_n}-\dfrac{\beta}{\alpha}$
$=\dfrac{b_n}{a_n}-\dfrac{b_n\gamma +b_{n-1}}{a_n\gamma +a_{n-1}}$
$=\dfrac{-(a_nb_{n-1}-a_{n-1}b_n)}{a_n(\gamma a_n+a_{n-1})}$
$=\dfrac{(-1)^{n-1}}{a_n(\gamma a_n+a_{n-1})}$
したがって,
$n$が偶数のとき$x_n$<$x$,$n$が奇数のとき$x$<$x_n$・・・B
が成り立つ.

次に,$x_{n+2}-x_n$を計算しよう.
$x_{n+2}-x_n=\dfrac{b_{n+2}}{a_{n+2}}-\dfrac{b_n}{a_n}$
$=\dfrac{a_nb_{n+2}-a_{n+2}b_n}{a_{n+2}a_n}$
$a_nb_{n+2}-a_{n+2}b_n=a_n(q_{n+2}b_{n+1}+b_n)-(q_{n+2}a_{n+1}+a_n)b_n=(-1)^nq_{n+2}$
であるから
$x_{n+2}-x_n=\dfrac{(-1)^nq_{n+2}}{a_{n+2}a_n}$・・・C
Cより次のことが分かる.
$n$が偶数のとき$x_n$<$x_{n+2}$
$n$が奇数のとき$x_n$>$x_{n+2}$
BおよびCより
$x_0$<$x_2$<$\cdots$<$x$<$\cdots$<$x_3$<$x_1$
となることが分かる.

また,$x$は$x_n,x_{n+1}$の間にあり,
$|x_n-x_{n+1}|=\dfrac{1}{a_na_{n+1}}$・・・D
であった.
$x=[q_0;q_1,\dots ,q_n,q_{n+1},\gamma]$
によって$\gamma$を定めれば,
$|x_{n+1}-x|=\dfrac{1}{a_{n+1}(\gamma a_{n+1}+a_n)}$

$[\gamma]=q_{n+2}$
であるから,
$\gamma $>$q_{n+2}$
$\therefore |x_{n+1}-x|$<$\dfrac{1}{a_{n+1}a_{n+2}}$
一方,
$a_{n+2}=q_{n+2}a_{n+1}+a_n$>$a_{n+1}+a_n$>$2a_n$
より
$|x_{n+1}-x|$<$\dfrac{1}{2a_{n}a_{n+1}}$・・・E
D,Eより
$|x_{n+1}-x|$<$|x_{n}-x|$・・・F
が分かる.
Fは無理数$x$の近似分数列$\{x_n=\dfrac{b_n}{a_n}\}$は順に$x$に近づいている事を意味している.
この節の目的である次の定理の証明の準備が整った.

定理
無理数$x$の近似分数
$x_n=\dfrac{b_n}{a_n}$
は分母が$a_n$以下の分数のうちもっとも$x$に近い分数である.

証明
$x_{n-1}$<$x$<$x_n$
のときすなわち$n$が奇数のとき証明する.
既約分数$\frac{s}{t}$が
$x_{n-1}$<$\dfrac{s}{t}$<$x_n$
を満たすとき
$t$>$a_n$
を示せばよい.
$x_n-\dfrac{s}{t}=\dfrac{b_n}{a_n}-\dfrac{s}{t}=\dfrac{tb_n-sa_n}{ta_n}\geqq \dfrac{1}{ta_n}$
同様に
$\dfrac{s}{t}-x_{n-1}\geqq \dfrac{1}{ta_{n-1}}$
さらに,
$x_n-x_{n-1}=\dfrac{(-1)^{n-1}}{a_na_{n-1}}=\dfrac{1}{a_na_{n-1}}$
より
$\dfrac{1}{a_na_{n-1}}=x_n-x_{n-1}\geqq \dfrac{1}{ta_n}+\dfrac{1}{ta_{n-1}}\geqq \dfrac{a_n+a_{n-1}}{ta_na_{n-1}}$
$\therefore t \geqq a_n+a_{n-1}$>$a_n$
したがって,証明された.

今までの内容より次が成り立つ.
正の無理数$x$の近似分数を
$x_n=\dfrac{b_n}{a_n}$
とすると,
$|x-\dfrac{b_n}{a_n}|$<$\dfrac{1}{a_na_{n+1}}$ が成り立つから,
$|a_nx-b_n|$<$\dfrac{1}{a_{n+1}}$
を得る.したがって,任意の正の整数$t$に対して
$a_n\leqq t$<$a_{n+1}$
を満たす$n$をとれば
$|a_nx-b_n|$<$\dfrac{1}{a_{n+1}}$<$\dfrac{1}{t}$
を満たす.したがって,次のことが証明された.

定理
任意の正の無理数$x$と任意の正の整数$t$に対して,
$|nx-m|$<$\dfrac{1}{t}, \ \ 1\leqq n\leqq t$
を満たす整数$n,m$が存在する.

この定理は,連分数の知識を用いず直接証明できる.それは次の部屋割り論法と呼ばれる方法をも ちいたものでDirichletによるものである.

<部屋割り論法>
$n+1$個を$n$箱にどのように分配しても2個以上入る箱が少なくとも1つは存在する

定理の証明 $n=0,1,2,\dots ,t$のおのおのの値に対して,$m$を
$m=[nx]$
によって定義すれば,$t+1$個の値,
$\{nx-m\}$
はそれぞれ
$0\leqq nx-m $<$1$
を満たす.そこで,区間$[0,1)$を$t$個の区間
$[0,\frac{1}{t}),[\frac{1}{t},\frac{2}{t}),\dots ,[\frac{t-1}{t},1)$
に分割すれば,少なくともどれかの区間には2つの値が入る,それを
$n_1x-m_1,n_2x-m_2$
とすれば,
$|(n_1x-m_1)-(n_2x-m_2)|$<$\dfrac{1}{t}$
$n=n_1-n_2,m=m_1-m_2$
とおけば,
$|nx-m|$<$\dfrac{1}{t}$


続く



目次