初等整数論/連分数

連分数は分母に分数が出る形の式のことである。

$a_{0}+{\frac {b_{0}}{\displaystyle a_{1}+{\frac {b_{1}}{\displaystyle a_{2}+{\frac {b_{2}}{\displaystyle a_{3}+{\frac {b_{3}}{\cdots }}}}}}}}$

話を単純にするため分子がみな 1 になる連分数を扱う。

このような連分数はスペースを取るので様々な省略記法があるのだが、ここでは上の連分数を

$(a_{0},a_{1},a_{2},a_{3},\cdots )$ と表すことにする。

さて、この連分数の値を求めることを目標とするのだが、その前に全く関係のなさそうな話を少々することになる。

${\begin{cases}x_{0}&=k_{0}x_{1}+x_{2}\\x_{2}&=k_{1}x_{2}+x_{3}\\&\cdots \\x_{n-1}&=k_{n-1}x_{n}+x_{n+1}\\&\cdots \end{cases}}$

さてガウスの取った記号にならって、次の記号を定める。

${\begin{aligned}\left[k_{0}\right]&=k_{0}\\\left[k_{0},k_{1}\right]&=k_{0}k_{1}+1\\\left[k_{0},k_{1},\cdots ,k_{n}\right]&=k_{n}\left[k_{0},k_{1},\cdots ,k_{n-1}\right]+\left[k_{0},k_{1},\cdots ,k_{n-2}\right]\end{aligned}}$

このとき、上の連立方程式について次が成り立つ。

定理 4.1

$p_{0}=1,\ p_{n}=\left[k_{0},k_{1},\cdots ,k_{n-1}\right]\ (n=1,2,\cdots )$ とおくと

$x_{0}=p_{n}x_{n}+p_{n-1}x_{n+1}\ \ (n=1,2,\cdots )$ （$p_{n}$ は $\left[\right]$ の再記である）

証明
$x_{0}=k_{0}x_{1}+x_{2}=p_{1}x_{1}+p_{0}x_{2}$ より、 $n=1$ のときは自明に成り立つ。

次に、$n$ のとき成り立つとすると

$x_{0}=p_{n}x_{n}+p_{n-1}x_{n+1}$ 方程式の式を代入して

${\begin{aligned}x_{0}&=p_{n}(k_{n}x_{n+1}+x_{n+2})+p_{n-1}x_{n+1}\\&=(p_{n}k_{n}+p_{n-1})x_{n+1}+p_{n}x_{n+2}\\&=(k_{n}\left[k_{0},k_{1},\cdots ,k_{n-1}\right]+\left[k_{0},k_{1},\cdots ,k_{n-2}\right])x_{n+1}+p_{n}x_{n+2}\\&=(\left[k_{0},k_{1},\cdots ,k_{n}\right])x_{n+1}+p_{n}x_{n+2}\\&=p_{n+1}x_{n+1}+p_{n}x_{n+2}\\\end{aligned}}$

すなわち $n+1$ のときでも成り立つ。

以上より数学的帰納法で証明される。

なお、この構造は $k_{n}$ をユークリッドの互除法の逐次商とみたときに一次不定方程式の係数の漸化式と同じである。