「初等整数論/連分数」の版間の差分

編集の要約なし
編集の要約なし
x_{n-1} & = k_{n-1}x_n + x_{n+1} \\
& \cdots
\end{cases} \cdots (1)</math>
 
さてガウスの取った記号にならって、次の記号を定める。
<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 (n = 1, 2, \cdots)</math> (<math>p_n</math> は <math>\left[ \, \cdots \, \right]</math> の再記である)
 
'''証明'''<br />
次に、<math>n</math> のとき成り立つとすると
 
<math>x_0 = p_nx_n + p_{n-1}x_{n+1}</math> 方程式(1) の式を代入して
 
<math>\begin{align}
 
 
なお、<math>p_{n+1} = p_nk_n + p_{n-1}</math> という漸化式が上の証明から分かるが、
なお、この構造は <math>k_n</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>
 
<!--
(2) より
 
<math>\begin{align}
x_0 & = \left[ k_0, k_1, \cdots , k_{n-1} \right]x_n + \left[ k_0, k_1, \cdots , k_{n-2} \right]x_{n+1} \\
x_1 & = \left[ k_1, k_2, \cdots , k_{n-1} \right]x_n + \left[ k_1, k_2, \cdots , k_{n-2} \right]x_{n+1} \\
x_2 & = \left[ k_2, k_3, \cdots , k_{n-1} \right]x_n + \left[ k_2, k_3, \cdots , k_{n-2} \right]x_{n+1} \\
\end{align}</math>
 
2番目の式に <math>k_0</math> をかけて <math>x_1</math>
-->
1,326

回編集