初等整数論/連分数のソースを表示

{{Nav}}

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

<math>a_0 + \frac{b_0}{ \displaystyle a_1 + \frac{b_1}{ \displaystyle a_2 + \frac{b_2}{ \displaystyle a_3 + \frac{b_3}{\cdots} } } }</math>

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

<math>a_0 + \frac{1}{ \displaystyle a_1 + \frac{1}{ \displaystyle a_2 + \frac{1}{ \displaystyle a_3 + \frac{1}{\cdots} } } }</math>

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

<math>(a_0, a_1, a_2, a_3, \cdots )</math> と表すことにする。

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

<math>\begin{cases}
x_0 & = k_0x_1 + x_2 \\
x_2 & = k_1x_2 + x_3 \\
& \cdots \\
x_{n-1} & = k_{n-1}x_n + x_{n+1} \\
& \cdots
\end{cases} \cdots (1)</math>

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

<math>\begin{align}
\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{align}</math>

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

====== 定理 4.1 ======
<math>p_0 = 1, \ p_n = \left[ k_0, k_1, \cdots , k_{n-1} \right] \ (n = 1, 2, \cdots )</math> とおくと

<math>x_0 = p_nx_n + p_{n-1}x_{n+1} \ \cdots (2)</math> （<math>p_n</math> は <math>\left[ \, \cdots \, \right]</math> の再記である）

'''証明'''<br />
<math>x_0 = k_0x_1 + x_2 = p_1x_1 + p_0x_2</math> より、 <math>n = 1</math> のときは自明に成り立つ。

次に、<math>n</math> のとき成り立つとすると

<math>x_0 = p_nx_n + p_{n-1}x_{n+1}</math> (1) の式を代入して

<math>\begin{align}
x_0 & = p_n(k_nx_{n+1} + x_{n+2}) + p_{n-1}x_{n+1} \\
& = (p_nk_n + p_{n-1})x_{n+1} + p_nx_{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_nx_{n+2} \\
& = ( \left[ k_0, k_1, \cdots , k_n \right] )x_{n+1} + p_nx_{n+2} \\
& = p_{n+1}x_{n+1} + p_nx_{n+2} \\
\end{align}</math>

すなわち <math>n+1</math> のときでも成り立つ。

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


なお、<math>p_{n+1} = p_nk_n + p_{n-1}</math> という漸化式が上の証明から分かるが、

これは <math>k_n</math> をユークリッドの互除法の逐次商とみたときに[[初等整数論/算術の基本定理#一次不定方程式|一次不定方程式]]の係数の漸化式と同じである。


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

ただし <math>q_0 = 0, \ q_1 = 1, \ q_n = \left[ k_1, k_2, \cdots , k_{n-1} \right] \ (n = 2, 3, \cdots)</math> である。

そうすると、<math>p_n</math> と同様、<math>q_{n+1} = q_nk_n + q_{n-1} \ \cdots (3)</math> となる。

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

====== 定理 4.2 ======
<math>(-1)^nx_n = q_{n-1}x_0 - p_{n-1}x_1</math>

'''証明'''<br />
これを証明する前に、まずは次の等式を証明する。

<math>
\left|
    \begin{array}{ccc}
      p_n & p_{n-1} \\
      q_n & q_{n-1}
    \end{array}
\right|
 = (-1)^n
</math>

すなわち、<math>p_n q_{n-1} - p_{n-1}q_n = (-1)^n \cdots (4)</math>

<math>n = 1</math> のとき、

<math>
\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
</math>

より、自明に成り立つ。

次に、<math>n</math> のとき成り立つとすると、

<math>\begin{align}
\left|
    \begin{array}{ccc}
      p_{n+1} & p_n \\
      q_{n+1} & q_n
    \end{array}
\right|
& = 
\left|
    \begin{array}{ccc}
      p_nk_n + p_{n-1} & p_n \\
      q_nk_n + q_{n-1} & q_n
    \end{array}
\right| \\
& = (p_nk_n + p_{n-1})q_n - p_n(q_nk_n + q_{n-1}) \\
& = p_nk_nq_n + p_{n-1}q_n - p_nq_nk_n - p_nq_{n-1} \\
& = p_{n-1}q_n - p_nq_{n-1} \\
& = -(p_nq_{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{align}</math>

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


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

<math>\begin{align}
& \begin{cases}
  x_0 & = p_nx_n + p_{n-1}x_{n+1} \\
  x_1 & = q_nx_n + q_{n-1}x_{n+1}
\end{cases} \ \cdots (5) \\
\iff &
\begin{cases}
  q_{n-1}x_0 & = q_{n-1}p_nx_n + q_{n-1}p_{n-1}x_{n+1} \\
  -p_{n-1}x_1 & = -p_{n-1}q_nx_n - p_{n-1}q_{n-1}x_{n+1}
\end{cases}
\end{align}
</math>

<math>
\therefore \ x_n(p_nq_{n-1} - p_{n-1}q_n) = q_{n-1}x_0 - p_{n-1}x_1 \iff (-1)^nx_n = q_{n-1}x_0 - p_{n-1}x_1 \ \ \ (\because (4) \, )
</math>


----

さて、<math>p_n, q_n</math> を計算するには次の等式を用いるのが簡便である。

<math>\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)</math>

<math>n = 1</math> のとき、定義より

<math>\begin{align}
\left[ k_0, k_1, k_2 \right] & = k_2 \left[ k_0, k_1 \right] + \left[ k_0 \right] \\
& = k_2 (k_0k_1 + 1) + k_0 \\
& = k_0(k_1k_2 + 1) + k_2 \\
& = k_0 \left[ k_1, k_2 \right] + \left[ k_2 \right]
\end{align}</math>

したがって成り立つ。

<math>n = 2</math> のとき、

<math>
\begin{align}
\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_0k_1 + 1 \\
& = k_3(k_2k_0k_1 + k_2 + k_0) + k_0k_1 + 1 \\
& = k_0k_1k_2k_3 + k_2k_3 + k_0k_3 + k_0k_1 + 1 \\
\end{align}
</math>


<math>
\begin{align}
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_2k_3 + 1 \\
& = k_0(k_3k_2k_1 + k_3) + k_2k_3 + 1 \\
& = k_0k_1k_2k_3 + k_2k_3 + k_0k_1 + 1 \\
\end{align}
</math>


<math>
\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]
</math>

したがって成り立つ。


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

<math>\begin{align}
\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{align}</math>

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

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

<math>(a_0, a_1, a_2, \cdots, a_n)</math> は冒頭と同じく

<math>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} } } } } }</math>

を表すこととする。

<math>(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] }</math> が成り立つ。

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

<math>\begin{align}
\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{align}</math>

となるからである。

{{Nav}}

[[Category:初等整数論|れんふんすう]]