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

12.2 近似分数

実数$x$が，
$x=[q_0;q_1,q_2,\dots ,q_n,\dots ]$
と連分数展開されるとき，$x$の近似分数
$x_0=q_0,x_1=[q_0;q_1]=\dfrac{b_1}{a_1},x_2=[q_0;q_1,q_2]=\dfrac{b_2}{a_2},\dots ,$
$x_n=[q_0;q_1,q_2,\dots ,q_n]=\dfrac{b_n}{a_n}$
を調べる．
まず，近似分数を数列$\{q_n\}$で表そう．
$x_k$を$q_0,q_1,\dots ,q_k$で表したときの$q_k$を$q_k+\dfrac{1}{q_{k+1}}$で置き換えた式が$x_{k+1}$であることを利用する．
$x_0=q_0=\dfrac{b_0}{a_0}$
$x_1=q_0+\dfrac{1}{q_1}=\dfrac{b_0}{a_0}+\dfrac{1}{q_1}=\dfrac{q_1b_0+a_0}{a_0q_1}=\dfrac{b_1}{a_1}$
$x_2=\dfrac{(q_1+\dfrac{1}{q_2})b_0+a_0}{a_0(q_1+\dfrac{1}{q_2})} =\dfrac{b_1+\dfrac{b_0}{q_2}}{a_1+\dfrac{a_0}{q_2}}=\dfrac{q_2b_1+b_0}{q_2a_1+a_0}$
これで規則性が見えてきました．確認しましょう．
$x_k=\dfrac{q_kb_{k-1}+b_{k-2}}{q_ka_{k-1}+a_{k-2}}=\dfrac{b_k}{a_k}$
のとき，
$x_{k+1}=\dfrac{(q_k+\dfrac{1}{q_{k+1}})b_{k-1}+b_{k-2}}{(q_k+\dfrac{1}{q_{k+1}})a_{k-1}+a_{k-2}} =\dfrac{q_{k+1}b_k+b_{k-1}}{q_{k+1}a_k+a_{k-1}}$
すなわち，
$x$の近似分数の列$\{x_n\}$を
$x_n=\dfrac{b_n}{a_n}$
とするとき，
$a_0=1,a_1=q_1,$
$a_n=q_na_{n-1}+a_{n-2} \ \ (2\leqq n)$
$b_0=q_0,b_1=q_1b_0+1$
$b_n=q_nb_{n-1}+b_{n-2} \ \ (2\leqq n)$
で得られることが分かる．ここで$a_n,b_n$が互いに素でないと気持ち悪いが，互いに素であることは後で証明する．
近似分数は次の表を用いて計算するの一般的です．
$\begin{matrix} \quad & \quad & q_0 & q_1 & q_2 & \dots & q_n　\\ b_n: & 1 & q_0 & b_1 & b_2 & \dots & b_n \\ a_n: & 0 & 1 & a_1 & a_2 & \dots & a_n \end{matrix}$
上の表で，
$b_1=q_1\times q_0+1,b_2=q_2\times b_1+q_0,\dots$
$a_1=q_1,a_2=q_2\times a_1+1,\dots$
である．この表のように，第１列に１と０を付け加えると計算がしやすい．
$x=[1;2,3,4]$の近似分数を求めよう．
$\begin{matrix} \quad & \quad & q_0=1 & q_1=2 & q_2=3 & q_4=4　\\ b_n: & 1 & b_0=(q_0)=1 & b_1=3 & b_2=10 & b_4=43 \\ a_n: & 0 & a_0=1 & a_1=2 & a_2=7 & a_4=30 \end{matrix}$
より近似分数は
$x_0=1,x_1=\dfrac{3}{2},\dfrac{10}{7},\dfrac{43}{30}$


無理数$x$が
$x=[q_0;q_1,q_2,\dots ]$
と連分数展開されるとき，$x$の近似分数の列$\left \{x_n=\dfrac{b_n}{a_n}\right\}$
の性質を調べよう．

まず，隣り合う近似分数
$x_n=\dfrac{b_n}{a_n},x_{n+1}=\dfrac{b_{n+1}}{a_{n+1}}$
の関係を調べる．
$x_{n+1}-x_n=\dfrac{b_{n+1}}{a_{n+1}}-\dfrac{b_n}{a_n}$
$=\dfrac{a_nb_{n+1}-a_{n+1}b_n}{a_{n+1}a_n}$
分子を計算しよう．
$c_n=a_nb_{n+1}-a_{n+1}b_n$
とおく．
$a_{n+1}=q_{n+1}a_n+a_{n-1},b_{n+1}=q_{n+1}b_n+b_{n-1}$
より
$c_n=a_n(q_{n+1}b_n+b_{n-1})-(q_{n+1}a_n+a_{n-1})b_n$
$=a_nb_{n-1}-a_{n-1}b_n$
$=-c_{n-1}$
$\therefore c_n=(-1)^nc_0$
ここで，
$c_0=a_0b_1-a_1b_0=1\cdot (q_0q_1+1)-q_0q_1=1$
$\therefore c_n=(-1)^n$

この結果をまとめると次のようになる．

命題
無理数$x$の隣り合う近似分数
$x_n=\dfrac{b_n}{a_n},x_{n+1}=\dfrac{b_{n+1}}{a_{n+1}}$
について
$a_nb_{n+1}-a_{n+1}b_n=(-1)^n$
が成り立つ．

この命題より，当然
$x_{n+1}-x_n=\dfrac{(-1)^n}{a_na_{n_1}}$
が成り立ち，さらに$a_n,b_n$が必ず互いに素であることが分かる．
$\because \alpha $が$a_n,b_n$の公約数なら$a_nb_{n+1}-a_{n+1}b_n$は$\alpha$の倍数$)$

例
命題の性質を，不定方程式
$ax+by=1$・・・@
の整数解を見つける問題に応用しよう．
２つの分数
$\dfrac{d}{c},\dfrac{b}{a}$
が隣あう近似分数であるなら，
$ad-bc=\pm 1$
である．この性質を利用して，不定方程式@の整数解を見つけることが出来る．実際$\frac{b}{a}$の近似分数列の $\frac{b}{a}$の手前の分数を$\frac{d}{c}$とすれば
$ad-bc=\pm 1$
であるから，
$x=d,y=-c$
または $x=-d,y=c$
が不定方程式@の整数解の一つである．


ここで，先を急がず，２つの既約分数
$\dfrac{b}{a},\dfrac{d}{c}$ただし $\dfrac{b}{a}$＜$\dfrac{d}{c}$
が$ad-bc=\pm 1$を満たす場合の性質を調べよう．
まず加比の理を思い出そう．
最近はこの名前を見ることが非常に少なくなったが次の性質をいう．

命題(加比の理)
２つの分数$\dfrac{b}{a},\dfrac{d}{c}$が$\dfrac{b}{a}$＜$\dfrac{d}{c}$を満たすとき，任意の正の整数$m,n$に対して
$\dfrac{b}{a}$＜$\dfrac{mb+nd}{ma+nc}$＜$\dfrac{d}{c}$
が成り立つ．

証明は分母を払って計算すれば簡単であるが，右図のように直線の傾きに注目した方が分かりやすい．
$P(a,b),Q(c,d)$として，$PQ$を$n:m$に内分した点を$R(\dfrac{ma+nc}{m+n},\dfrac{mb+nd}{m+n})$とすると
直線$OP,OQ,OR$の傾きはそれぞれ
$\dfrac{b}{a},\dfrac{d}{c},\dfrac{mb+nd}{ma+nc}$
であるから加比の理が成り立つ．
グラフより$\dfrac{mb+nd}{ma+nc}$は$\frac{n}{m+n}$が大きくなるにつれ増えるすなわち$\frac{d}{c}$に近づくことが分かる．
説明から分かるように，$m,n$は正の実数であれば成り立つ．

逆を調べよう．すなわち，
$\dfrac{b}{a}$＜$\dfrac{d}{c}$
を満たすとき，$x,y$が正の整数で
$\dfrac{b}{a}$＜$\dfrac{y}{x}$＜$\dfrac{d}{c}$
を満たすとき，正の整数$m,n$を用いて
$x=ma+nc,y=mb+nd$
と表せるか．
です．


続く



目次