１２.ユークリッド互除法と近似分数 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}$ と表せることが分かりました． すなわち，次の命題が分かりました． 命題 ２つの既約分数$\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}$ と表せる． この命題より次の性質は簡単に分かる． 系 ２つの既約分数$\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$箱にどのように分配しても２個以上入る箱が少なくとも１つは存在する 定理の証明 $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)$ に分割すれば，少なくともどれかの区間には２つの値が入る，それを $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}$ 続く 目次 |