初 等 整 数 論 講 義 第 $2$ 版

$\blacktriangleleft$ $\S\ 18.$ 任意の法に関する指数,指標  $\S\ 20.$ 実数の連分数展開 $\blacktriangleright$

『初等整数論講義 第 $2$ 版』目次へ



第 $1$ 章 附   記

 $\S\ 19.$ 連  分  数

 $\boldsymbol{1.}$ 連分数というのは\[a_0+\frac{b_1}{a_1+\dfrac{b_2}{a_2+\cdots\cdots\hphantom{b_1b}\lower{1.3em}{+\dfrac{b_{n-1}}{a_{n-1}+\dfrac{b_n}{a_n}}}}}\tag{$\ 1\ $}\]のような形の式である.すなわち $a_0$,$a_1$,$a_2$,$\cdots\cdots$;$b_1$,$b_2$,$\cdots\cdots$ 等の文字に関する特種の有理式にほかならないのである.
 紙面を節約するために,連分数を表わす種々の記法が用いられているが,本書では $\left(\ 1\ \right)$ を次のように記す.\[a_0+\frac{b_1}{a_1}\raise{0.2em}{\underset{\Large+}{}}\frac{b_2}{a_2}\raise{0.2em}{\underset{\Large+}{}}\ \underset{\Large\cdots}{}\ \underset{\Large\cdots}{}\ \raise{0.2em}{\underset{\Large+}{}}\frac{b_n}{a_n}.\]かつまた本書においては分子 $b_1$,$b_2$,$\cdots\cdots$,$b_n$ が $1$ なる場合,すなわち\[k_0+\frac{1}{k_1}\raise{0.2em}{\underset{\Large+}{}}\frac{1}{k_2}\raise{0.2em}{\underset{\Large+}{}}\ \underset{\Large\cdots}{}\ \underset{\Large\cdots}{}\ \raise{0.2em}{\underset{\Large+}{}}\frac{1}{k_n}\tag{$\ 2\ $}\]のような形のみを取り扱う.

 $\boldsymbol{2.}$ 本節ではまず $\left(\ 2\ \right)$ のような連分数を一つの分数式として表わす計算の方法を説明するが,便宜上,少し問題を一般化して,次のような関係式を考察する.\[\left.\begin{alignat*}{1}x_0&=k_0x_1+x_2,\\[2mm]x_1&=k_1x_2+x_3,\\[2mm]&\cdots\cdots\cdots\cdots\\[2mm]x_{n-1}&=k_{n-1}x_n+x_{n+1},\\[2mm]&\cdots\cdots\cdots\cdots\end{alignat*}\right\}\tag{$\ 3\ $}\]ここで $k_0$,$k_1$,$\cdots\cdots$ は任意の常数として,$x_0$,$x_1$,$x_2$,$\cdots\cdots$ をこれらの方程式によって結びつけられた変数と見る.
 〔定理 $\boldsymbol{2.\ 1}$〕 変数 $x_0$,$x_1$,$x_2$,$\cdots\cdots$ が関係式 $\left(\ 3\ \right)$ で結び付けられているときは\[x_0=p_nx_n+p_{n-1}x_{n+1},\hphantom{m}\left(n=1,\ 2,\ \cdots\cdots\right)\tag{$\ 4\ $}\]ただし,$p_n$ は $k_0$,$k_1$,$\cdots\cdots$,$k_{n-1}$ のみに関係する係数で\begin{alignat*}{1}p_0&=1,\hspace{0.5cm}p_1=k_0.\tag{$\ 5\ $}\\[2mm]p_n&=p_{n-1}k_{n-1}+p_{n-2}.\ \ \left(n\geqq2\right)\tag{$\ 6\ $}\end{alignat*} 〔〕 $n=1$ のときには $\left(\ 4\ \right)$ は $\left(\ 3\ \right)$ の第一式にほかならない.さて $\left(\ 4\ \right)$ が $n-1$ の場合に成り立つと仮定すれば,\[x_0=p_{n-1}x_{n-1}+p_{n-2}x_n.\] $\left(\ 3\ \right)$ から代入して\begin{alignat*}{1}x_0&=p_{n-1}\left(k_{n-1}x_n+x_{n+1}\right)+p_{n-2}x_n\\[2mm]&=\left(p_{n-1}k_{n-1}+p_{n-2}\right)x_n+p_{n-1}x_{n+1}.\end{alignat*}すなわち $\left(\ 6\ \right)$ のようにすれば,$\left(\ 4\ \right)$ は $n$ の場合にも成り立つのである.
 $\left(\ 5\ \right)$, $\left(\ 6\ \right)$ から見える通り,$p_n$ は $k_0$,$k_1$,$\cdots\cdots$,$k_{n-1}$ の多項式でかつこれらの文字に加法と乗法とのみを行なって組み立てられている.
 この多項式を Gauss は次のような記法で表わした:\[p_n=\left[k_0,\ k_1,\ k_2,\ \cdots\cdots,\ k_{n-1}\right]\ \ \left(n=1,\ 2,\ \cdots\cdots\right)\]括弧 $\left[\hphantom{m}\right]$ は函数記号である.すなわち\begin{alignat*}{1}\left[k_0\right]&=k_0,\\[2mm]\left[k_0,\ k_1\right]&=k_0k_1+1,\\[2mm]\left[k_0,\ k_1,\ k_2\right]&=k_0k_1k_2+k_0+k_2,\ \cdots\cdots\\[2mm]\left[k_0,\ k_1,\ \cdots\cdots,\ k_n\right]&=\left[k_0,\ k_1,\ \cdots\cdots,\ k_{n-1}\right]k_n\\[2mm]&\hphantom{==}+\left[k_0,\ k_1,\ \cdots\cdots,\ k_{n-2}\right].\tag{$\ 6^{\large*}$}\end{alignat*}この最後の等式は $\left(\ 6\ \right)$ の再記である.
 $\boldsymbol{3.}$ $\left(\ 3\ \right)$ の第一の方程式を除外して,変数 $x_1$,$x_2$,$\cdots\cdots$ のみに着眼すれば,定理 $2.\ 1$ によって\[x_1=q_nx_n+q_{n-1}x_{n+1}\tag{$\ 7\ $}\]を得る.ここでは\[q_n=\left[k_1,\ k_2,\ \cdots\cdots,\ k_{n-1}\right]\hspace{1cm}\left(n=2,\ 3,\ \cdots\cdots\right)\] $\left(\ 7\ \right)$ を $n=1$ の場合にも成り立たせるために\[q_0=0,\hspace{0.5cm}q_1=1\tag{$\ 8\ $}\]と置く($x_1=1x_1+0x_2$).
 そうすれば $\left(\ 6\ \right)$ と同様に\[q_n=q_{n-1}k_{n-1}+q_{n-2}\hspace{1cm}\left(n=2,\ 3,\ \cdots\cdots\right)\tag{$\ 9\ $}\]等式 $\left(\ 4\ \right)$,$\left(\ 7\ \right)$,すなわち\begin{alignat*}{1}x_0&=p_nx_n+p_{n-1}x_{n+1},\\[2mm]x_1&=q_nx_n+q_{n-1}x_{n+1}\end{alignat*}を,$x_n$,$x_{n+1}$ を未知数とする連立一次方程式と見なせば,$x_n$ を $x_0$ と $x_1$ とで表わすことができる.そのためにまず\[\begin{vmatrix}p_n&p_{n-1}\\q_n&q_{n-1}\end{vmatrix}=\left(-1\right)^n\tag{$10$}\]を証明する.この等式は連分数論において基本的である. $\left(\ 6\ \right)$,$\left(\ 9\ \right)$ から\[\begin{vmatrix}p_n&p_{n-1}\\q_n&q_{n-1}\end{vmatrix}=\begin{vmatrix}p_{n-1}k_{n-1}+p_{n-2}&p_{n-1}\\q_{n-1}k_{n-1}+q_{n-2}&q_{n-1}\end{vmatrix}=-\begin{vmatrix}p_{n-1}&p_{n-2}\\q_{n-1}&q_{n-2}\end{vmatrix}.\]すなわち $\left(\ 10\ \right)$ の行列式は $n$ の値 $1$ を増すとき,ただその符号を変えるばかりである.さて\[\begin{vmatrix}p_1&p_0\\q_1&q_0\end{vmatrix}=\begin{vmatrix}k_0&1\\1&0\end{vmatrix}=-1.\]故に $\left(\ 10\ \right)$ が成り立つのである.
 よって次の定理を得る.
 〔定理 $\boldsymbol{2.\ 2}$〕 変数 $x_0$,$x_1$,$\cdots\cdots$,$x_n$ が関係式 $\left(\ 3\ \right)$ で結びつけられるときは\[\left(-1\right)^nx_n=q_{n-1}x_0-p_{n-1}x_1,\]すなわち\begin{alignat*}{1}\left(-1\right)^nx_n&=\left[k_1,\ k_2,\ \cdots\cdots,\ k_{n-2}\right]x_0\\[2mm]&\hphantom{=}\ -\left[k_0,\ k_1,\ k_2,\ \cdots\cdots,\ k_{n-2}\right]x_1.\tag{$11$}\end{alignat*} 〔〕 $\left(\ 4\ \right)$,$\left(\ 7\ \right)$ にそれぞれ $q_{n-1}$,$-p_{n-1}$ を掛けて加え,$\left(10\right)$ を用いて $\left(11\right)$ を得る.

 $\boldsymbol{4.}$ $p_n$,$q_n$ を計算するには $\left(\ 6\ \right)$,$\left(\ 9\ \right)$ を用いるよりも,次の公式によるのが便利である.\begin{alignat*}{1}\left[k_0,\ k_1,\ k_2,\ \cdots\cdots,\ k_{n-1}\right]&=k_0\left[k_1,\ k_2,\ \cdots\cdots,\ k_{n-1}\right]\\[2mm]&\hphantom{=}\ +\left[k_2,\ \cdots\cdots,\ k_{n-1}\right].\tag{$12$}\end{alignat*} これによれば,終りの係数から始めてつぎつぎに $\left[k_{n-1}\right]=k_{n-1}$,$\left[k_{n-2},\ k_{n-1}\right]$,$\left[k_{n-3},\ k_{n-2},\ k_{n-1}\right]$,$\cdots\cdots$ を計算することができて,$\left[k_0,\ \cdots\cdots,\ k_{n-1}\right]$ を得る途中で,$\left[k_1,\ \cdots\cdots,\ k_{n-1}\right]$ が求められるから,計算に無駄がない.
 さて公式 $\left(12\right)$ は次のようにして証明することができる.\begin{alignat*}{1}x_0&=\left[k_0,\ k_1,\ k_2,\ \cdots\cdots,\ k_{n-1}\right]x_n+\left[k_0,\ k_1,\ k_2,\ \cdots\cdots,\ k_{n-2}\right]x_{n+1},\tag{$13$}\\[2mm]x_1&=\left[k_1,\ k_2,\ \cdots\cdots\cdots,\ k_{n-1}\right]x_n+\left[k_1,\ k_2,\ \cdots\cdots,\ k_{n-2}\right]x_{n+1}.\tag{$14$}\end{alignat*}同様に\[x_2=\left[k_2,\ \cdots\cdots,\ k_{n-1}\right]x_n+\left[k_2,\ \cdots\cdots,\ k_{n-2}\right]x_{n+1}.\tag{$15$}\]しかるに $\left(\ 3\ \right)$ によって\[x_0=k_0x_1+x_2.\]故に $\left(14\right)$ に $k_0$ を掛けて $\left(15\right)$ を加え,$\left(13\right)$ と比較して $\left(12\right)$ を得るのである.
 〔問題 $\boldsymbol{1}$〕 $\left[a,\ b,\ c,\ \cdots\cdots,\ k,\ l\ \right]=\left[\ l,\ k,\ \cdots\cdots,\ c,\ b,\ a\right]$.
 〔解〕 $\left(\ 6^{\large*}\right)$ と $\left(12\right)$ とによる(数学的帰納法).
 または $p_n=k_{n-1}p_{n-1}+p_{n-2}$,$p_{n-1}=k_{n-2}p_{n-2}+p_{n-3}$,$\cdots$,$p_2=k_1p_1+p_0$,$p_1=k_0p_0+0$ を $\left(\ 3\ \right)$ の等式に代用して,$\left(13\right)$ から(ここでは $x_n=p_0=1$,$x_{n+1}=0$)\[p_n=\left[k_{n-1},\ k_{n-2},\ \cdots\cdots,\ k_1,\ k_0\right],\] すなわち\[\left[k_0,\ k_1,\ \cdots\cdots,\ k_{n-1}\right]=\left[k_{n-1},\ k_{n-2},\ \cdots\cdots,\ k_1,\ k_0\right].\] これによっても $\left(12\right)$ が証明される.

 〔問題 $\boldsymbol{2}$〕 $\left[k_0,\ k_1,\ \cdots\cdots,\ k_n\right]=\ \!$$\ k_0$$\hphantom{--}1$$\ 0$$0$$\cdots\cdots$$0$
$\ -1$$\hphantom{-}\ \ k_1$$\ 1$$0$$\cdots\cdots$$0$
$\ 0$$\hphantom{1}-\!1$$k_2$$1$$\cdots\cdots$$0$
${\small\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots}$
$\ 0$$\hphantom{--}0\cdots$$-1$$\ \ k_{n-1}$$1$
$\ 0$$\hphantom{--}0\cdots\cdots$$\hphantom{-}0$$\ -1$$k_n$

 〔解〕 右辺の行列式を $\varDelta_{n+1}$ とすれば,$\varDelta_{n+1}=k_n\varDelta_n+\varDelta_{n-1}$ で,$\varDelta_1=k_0$,$\varDelta_2=k_0k_1+1$(数学的帰納法).

 $\boldsymbol{5.}$ われわれの目標とした問題,すなわち連分数 $\left(\ 2\ \right)$ を分数式の形に表わすことは公式 $\left(12\right)$ によって,自然に解けてしまった.すなわち次の通り:\[k_0+\frac{1}{k_1}\raise{0.2em}{\underset{\Large+}{}}\frac{1}{k_2}\raise{0.2em}{\underset{\Large+}{}}\ \underset{\Large\cdots}{}\ \underset{\Large\cdots}{}\ \raise{0.2em}{\underset{\Large+}{}}\frac{1}{k_n}=\frac{\left[k_0,\ k_1,\ k_2,\ \cdots\cdots,\ k_n\right]}{\left[k_1,\ k_2,\ \cdots\cdots,\ k_n\right]}.\] 実際,右辺は $\left(12\right)$ によって\[\frac{k_0\left[k_1,\ k_2,\ \cdots\cdots,\ k_n\right]+\left[k_2,\ \cdots\cdots,\ k_n\right]}{\left[k_1,\ k_2,\ \cdots\cdots,\ k_n\right]}\\[2mm]\begin{alignat*}{1}&=k_0+\frac{1}{\dfrac{\left[k_1,\ k_2,\ \cdots\cdots,\ k_n\right]}{\left[k_2,\ \cdots\cdots,\ k_n\right]}}=k_0+\frac{1}{k_1+\dfrac{1}{\dfrac{\left[k_2,\ \cdots\cdots,\ k_n\right]}{\left[k_3,\ \cdots\cdots,\ k_n\right]}}}=\cdots\cdots\\[2mm]&=k_0+\frac{1}{k_1}\raise{0.2em}{\underset{\Large+}{}}\frac{1}{k_2}\raise{0.2em}{\underset{\Large+}{}}\ \underset{\Large\cdots}{}\ \underset{\Large\cdots}{}\ \raise{0.2em}{\underset{\Large+}{}}\frac{1}{k_n}.\end{alignat*}\] この後,上記の公式を次のような形で,しばしば引用する.\[k_0+\frac{1}{k_1}\raise{0.2em}{\underset{\Large+}{}}\frac{1}{k_2}\raise{0.2em}{\underset{\Large+}{}}\ \underset{\Large\cdots}{}\ \underset{\Large\cdots}{}\ \raise{0.2em}{\underset{\Large+}{}}\frac{1}{k_{n-1}}\ \raise{0.2em}{\underset{\Large+}{}}\frac{1}{x_n}=\frac{p_nx_n+p_{n-1}}{q_nx_n+q_{n-1}},\]ただし,$p$,$q$は前の通り,すなわち\[p_n=\left[k_0,\ k_1,\ k_2,\ \cdots\cdots,\ k_{n-1}\right],\hphantom{m}q_n=\left[k_1,\ k_2,\ \cdots\cdots,\ k_{n-1}\right].\] 実際,\begin{alignat*}{1}k_0&+\frac{1}{k_1}\raise{0.2em}{\underset{\Large+}{}}\frac{1}{k_2}\raise{0.2em}{\underset{\Large+}{}}\ \underset{\Large\cdots}{}\ \underset{\Large\cdots}{}\ \raise{0.2em}{\underset{\Large+}{}}\frac{1}{k_{n-1}}\ \raise{0.2em}{\underset{\Large+}{}}\frac{1}{x_n}=\frac{\left[k_0,\ k_1,\ k_2,\ \cdots\cdots,\ k_{n-1},\ x_n\right]}{\left[k_1,\ k_2,\ \cdots\cdots,\ k_{n-1},\ x_n\right]}\\[2mm]&\hphantom{+}=\frac{\left[k_0,\ k_1,\ k_2,\ \cdots\cdots,\ k_{n-1}\right]x_n+\left[k_0,\ k_1,\ k_2,\ \cdots\cdots,\ k_{n-2}\right]}{\left[k_1,\ k_2,\ \cdots\cdots,\ k_{n-1}\right]x_n+\left[k_1,\ k_2,\ \cdots\cdots,\ k_{n-2}\right]}\\[2mm]&\hphantom{+}=\frac{p_nx_n+p_{n-1}}{q_nx_n+q_{n-1}}.\end{alignat*}
 $\boldsymbol{6.}$ 上記 $\left(\ 3\ \right)$ のような関係式\[x_{n-1}=k_{n-1}x_n+x_{n+1}\hspace{1cm}\left(n=1,\ 2,\ \cdots\cdots\right)\]から,$x_n$ を $x_0$,$x_1$ で表わすことは,すでにしばしば述べたのであるが(代.),ここではその計算の法式を詳説したのである.
 特に正の整数 $a$,$b$ の最大公約数 $d$ を互除法によって求めるとき,上文の記号と合わせるために,$a\gt b$,$a=x_0$,$b=x_1$,$d=x_n$ と記して\begin{alignat*}{1}x_0&=k_0x_1+x_2,\\[2mm]\cdots&\cdots\cdots\cdots\\[2mm]x_{n-2}&=k_{n-2}x_{n-1}+x_n\\[2mm]x_{n-1}&=k_{n-1}x_n\hspace{1cm}\left(x_{n+1}=0\right)\end{alignat*}と置けば,\begin{alignat*}{1}x_0&=\left[k_0,\ k_1,\ k_2,\ \cdots\cdots,\ k_{n-1}\right]x_n=p_nd,\\[2mm]x_1&=\left[k_1,\ k_2,\ \cdots\cdots,\ k_{n-1}\right]x_n=q_nd.\end{alignat*} また $\left(11\right)$ によって\[\left(-1\right)^nd=aq_{n-1}-bp_{n-1}.\] 特に $a$,$b$ が互いに素であるときは($d=1$),\[aq_{n-1}-bp_{n-1}=\left(-1\right)^n.\tag{$16$}\]よって上記 $p$,$q$ の計算法を用いて,一次不定方程式\[ay-bx=1\]の整数解を求めることができる.
 〔例〕 $332y-87x=1$.
$332=3\hspace{0.7mm}\cdotp87+71$,$\hspace{1cm}\begin{array}{cccccc}k_0&k_1&k_2&k_3&k_4&k_5\\\hline3&1&4&2&3&2\end{array}$
$\hphantom{1}87=1\hspace{0.7mm}\cdotp71+16$,
$\hphantom{1}71=4\hspace{0.7mm}\cdotp16+7$,
$\hphantom{1}16=2\hspace{0.7mm}\cdotp7\hphantom{1}+2$,$\hspace{1cm}\begin{array}{cccccc}x_0&x_1&x_2&x_3&x_4&x_5&x_6\\\hline332&87&71&16&7&2&1\end{array}$
$\hphantom{11}7=3\hspace{0.7mm}\cdotp2\hphantom{1}+1$,
$\hphantom{11}2=2\hspace{0.7mm}\cdotp1$.
 故に $\left(16\right)$ によって($n=6$)
$332\hspace{0.7mm}\cdotp\left[1,\ 4,\ 2,\ 3\right]-87\hspace{0.7mm}\cdotp\left[3,\ 1,\ 4,\ 2,\ 3\right]=1$.
よって$x=\left[3,\ 1,\ 4,\ 2,\ 3\right],$   
$y=\left[1,\ 4,\ 2,\ 3\right]\hphantom{3,\ ,}$
は一組の整数解である.
 これらの数を計算すれば,次のようになる.\[\raise{0.05em}\leftarrow\!\!\!\!\begin{array}{lllll}\ \hphantom{1}3,&1,&4,&2,&3\ \\\hline\ 145,&38,&31,&7,&3\ \end{array}\]$\left(12\right)$ によって右の端からつぎつぎに\begin{eqnarray*}\left[3\right]&=&3,\\\left[2,\ 3\right]&=&2\hspace{0.7mm}\cdotp3+1=7,\\\left[4,\ 2,\ 3\right]&=&4\hspace{0.7mm}\cdotp7+3=31,\\\left[1,\ 4,\ 2,\ 3\right]&=&1\hspace{0.7mm}\cdotp31+7=38,\\\left[3,\ 1,\ 4,\ 2,\ 3\right]&=&3\hspace{0.7mm}\cdotp38+31=145\end{eqnarray*}を求めたのである.すなわち\[x=145,\hphantom{m}y=38.\] 上記の例では $1$ が偶数番号の剰余($x_6=1$)として出てきたのであるが,$1$ が奇数番号の剰余である場合には $\left(16\right)$ は負の解を与えるであろう.例えば\[87y-71x=1\]を上の方法で解けば,上記の計算から,\begin{alignat*}{1}x_0&=87,\ \ x_1=71,\ \cdots\cdots,\ \ x_5=1,\\[2mm]k_0&=1,\ \ k_1=4,\ \ k_2=2,\ \ k_3=3.\end{alignat*}故に $\left(16\right)$ によって\[87\hspace{0.7mm}\cdotp\left[4,\ 2,\ 3\right]-71\hspace{0.7mm}\cdotp\left[1,\ 4,\ 2,\ 3\right]=-1.\]したがって\begin{alignat*}{1}x&=-\left[1,\ 4,\ 2,\ 3\right]=-38,\\[2mm]y&=-\left[4,\ 2,\ 3\right]=-31\end{alignat*}が一組の整数解である,一般の解は\begin{alignat*}{1}x&=-38+87t,\\[2mm]y&=-31+71t\end{alignat*}であるから,$t=1$ として,正の整数解\[x=49,\hphantom{m}\ y=40\]を得る.






$\blacktriangleleft$ $\S\ 18.$ 任意の法に関する指数,指標  $\S\ 20.$ 実数の連分数展開 $\blacktriangleright$

『初等整数論講義 第 $2$ 版』目次へ


 ページトップへ inserted by FC2 system