初等整数論/連分数

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

$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}+{\frac {1}{\displaystyle a_{1}+{\frac {1}{\displaystyle a_{2}+{\frac {1}{\displaystyle a_{3}+{\frac {1}{\cdots }}}}}}}}$

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

$(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}}\cdots (1)$

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

${\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+1}\right]&=k_{n+1}\left[k_{0},k_{1},\cdots ,k_{n}\right]+\left[k_{0},k_{1},\cdots ,k_{n-1}\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}\ \cdots (2)$ （$p_{n}$ は $\left[\,\cdots \,\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}$ (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$ のときでも成り立つ。

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

なお、$p_{n+1}=p_{n}k_{n}+p_{n-1}$ という漸化式が上の証明から分かるが、

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

さて、(1) の一番目の式を除外したときに定理 4.1 より $x_{1}=q_{n}x_{n}+q_{n-1}x_{n+1}$

ただし $q_{0}=0,\ q_{1}=1,\ q_{n}=\left[k_{1},k_{2},\cdots ,k_{n-1}\right]\ (n=2,3,\cdots )$ である。

そうすると、$p_{n}$ と同様、$q_{n+1}=q_{n}k_{n}+q_{n-1}\ \cdots (3)$ となる。

このとき、次の定理が連分数の理論において重要である。

定理 4.2

$(-1)^{n}x_{n}=q_{n-1}x_{0}-p_{n-1}x_{1}$

証明
これを証明する前に、まずは次の等式を証明する。

$\left|{\begin{array}{ccc}p_{n}&p_{n-1}\\q_{n}&q_{n-1}\end{array}}\right|=(-1)^{n}$

すなわち、$p_{n}q_{n-1}-p_{n-1}q_{n}=(-1)^{n}\cdots (4)$

$n=1$ のとき、

$\left|{\begin{array}{ccc}p_{1}&p_{0}\\q_{1}&q_{0}\end{array}}\right|=\left|{\begin{array}{ccc}k_{0}&1\\1&0\end{array}}\right|=-1$

より、自明に成り立つ。

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

${\begin{aligned}\left|{\begin{array}{ccc}p_{n+1}&p_{n}\\q_{n+1}&q_{n}\end{array}}\right|&=\left|{\begin{array}{ccc}p_{n}k_{n}+p_{n-1}&p_{n}\\q_{n}k_{n}+q_{n-1}&q_{n}\end{array}}\right|\\&=(p_{n}k_{n}+p_{n-1})q_{n}-p_{n}(q_{n}k_{n}+q_{n-1})\\&=p_{n}k_{n}q_{n}+p_{n-1}q_{n}-p_{n}q_{n}k_{n}-p_{n}q_{n-1}\\&=p_{n-1}q_{n}-p_{n}q_{n-1}\\&=-(p_{n}q_{n-1}-p_{n-1}q_{n})\\&=-\left|{\begin{array}{ccc}p_{n}&p_{n-1}\\q_{n}&q_{n-1}\\\end{array}}\right|\\&=(-1)^{n+1}\end{aligned}}$

ただし、最後の変形には帰納法の仮定を用いた。以上より数学的帰納法によって証明される。

さて、(2)、(3) より

${\begin{aligned}&{\begin{cases}x_{0}&=p_{n}x_{n}+p_{n-1}x_{n+1}\\x_{1}&=q_{n}x_{n}+q_{n-1}x_{n+1}\end{cases}}\ \cdots (5)\\\iff &{\begin{cases}q_{n-1}x_{0}&=q_{n-1}p_{n}x_{n}+q_{n-1}p_{n-1}x_{n+1}\\-p_{n-1}x_{1}&=-p_{n-1}q_{n}x_{n}-p_{n-1}q_{n-1}x_{n+1}\end{cases}}\end{aligned}}$

$\therefore \ x_{n}(p_{n}q_{n-1}-p_{n-1}q_{n})=q_{n-1}x_{0}-p_{n-1}x_{1}\iff (-1)^{n}x_{n}=q_{n-1}x_{0}-p_{n-1}x_{1}\ \ \ (\because (4)\,)$

---

さて、$p_{n},q_{n}$ を計算するには次の等式を用いるのが簡便である。

$\left[k_{0},k_{1},\cdots ,k_{n+1}\right]=k_{0}\left[k_{1},k_{2},\cdots ,k_{n+1}\right]+\left[k_{2},k_{3},\cdots ,k_{n+1}\right]\ \ \cdots (6)$

$n=1$ のとき、定義より

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

したがって成り立つ。

$n=2$ のとき、

${\begin{aligned}\left[k_{0},k_{1},k_{2},k_{3}\right]&=k_{3}\left[k_{0},k_{1},k_{2}\right]+\left[k_{0},k_{1}\right]\\&=k_{3}(k_{2}\left[k_{0},k_{1}\right]+\left[k_{0}\right])+k_{0}k_{1}+1\\&=k_{3}(k_{2}k_{0}k_{1}+k_{2}+k_{0})+k_{0}k_{1}+1\\&=k_{0}k_{1}k_{2}k_{3}+k_{2}k_{3}+k_{0}k_{3}+k_{0}k_{1}+1\\\end{aligned}}$

${\begin{aligned}k_{0}\left[k_{1},k_{2},k_{3}\right]+\left[k_{2},k_{3}\right]&=k_{0}(k_{3}\left[k_{1},k_{2}\right]+\left[k_{1}\right])+k_{2}k_{3}+1\\&=k_{0}(k_{3}k_{2}k_{1}+k_{3})+k_{2}k_{3}+1\\&=k_{0}k_{1}k_{2}k_{3}+k_{2}k_{3}+k_{0}k_{1}+1\\\end{aligned}}$

$\therefore \ \left[k_{0},k_{1},k_{2},k_{3}\right]=k_{0}\left[k_{1},k_{2},k_{3}\right]+\left[k_{2},k_{3}\right]$

したがって成り立つ。

次に、$n<m\ \ (3\leqq m)$ なる全ての $n$ について成り立つとすると

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

よって、$m$ も成り立つ。以上より全ての場合に成り立つことが分かり、(6) は累積帰納法で証明される。この式を使えば、後ろから $\left[k_{n+1}\right],\ \left[k_{n},k_{n+1}\right],\ \left[k_{n-1},k_{n},k_{n+1}\right],\cdots$ が次々に求まり、楽に計算ができる。

さて、目標としていたことは連分数を計算することだったが、それは (6) を用いれば簡単にできる。

$(a_{0},a_{1},a_{2},\cdots ,a_{n})$ は冒頭と同じく

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

を表すこととする。

$(k_{0},k_{1},k_{2},\cdots ,k_{n})={\frac {\left[k_{0},k_{1},k_{2},\cdots ,k_{n}\right]}{\left[k_{1},k_{2},\cdots ,k_{n}\right]}}$ が成り立つ。

なぜなら、(6) によって左辺は

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

となるからである。