正則連分数の性質

次の定理を示すことが今回の目的である。

定理. \[ [a_0,a_1,\cdots,a_n] \] を正則連分数とする。(ここでは簡単のため $a_k \in \mathbb{N} (k=0,1,2,\cdots )$ を仮定する。) そして、既約分数化したのものを \[ \frac{p_n}{q_n} = [a_0,a_1,\cdots,a_n] \] とおく。このとき、各 $n\in \{ 0,1,2,\cdots, \}$に対して次が成立する。 \[ p_{n+1} q_{n} - p_{n} q_{n+1} = (-1)^{n} \]

最後にこの性質を応用して、1次不定方程式を解く。

行列と一次分数関数の関係

\[ f(x) = \frac{ax+b}{cx+d}, \quad g(x) = \frac{px+q}{rx+s} \] とするとき、これらの合成関数は \begin{align*} f(g(x)) &= \frac{a\cfrac{px+q}{rx+s}+b}{c\cfrac{px+q}{rx+s}+d} \\ &= \frac{a(px+q)+b(rx+s)}{c(px+q)+d(rx+s)} \\ &= \frac{(ap+br)x+aq+bs}{(cp+dr)x+cq+ds} \end{align*} となる。一方 \[ \pmatrix{a & b \\ c & d} \pmatrix{p & q \\ r & s} = \pmatrix{ap+br & aq +bs \\ cp + dr & cq +ds} \] となっているから、分数関数の合成は行列の積を利用して計算できることが分かる。

例. \[ f(x) = \frac{x-1}{x+1} \] とおくとき$f(f(x))$を直接代入して計算すると \[ f(f(x)) = -\frac{1}{x} \] が確かめられる。一方 $f(x)$ に対応する行列は \[ \pmatrix{1 & -1 \\ 1 & 1} \] となることから、この $2$ 乗を計算すると \[ \pmatrix{1 & -1 \\ 1 & 1} \pmatrix{1 & -1 \\ 1 & 1} = \pmatrix{0 & -2 \\ 2 & 0} \] が得られる。この右辺の行列に対応する1次分数関数は \[ \frac{-2}{2x}=\frac{-1}{x} \] となり、先ほど得た $f(f(x))$ の計算結果と一致する。

連分数の1次分数関数による表現と行列表現

記号 $\circ$ によって代入操作を表すことにする。(これはあまり用いられない記法であるが便利なので導入する.) 例. \[ (2x+1)\circ(x+1) = 2(x+1)+1=2x+3\] この約束の下で、連分数は次のように1次分数関数の合成として表現できる。 \begin{align*} [a_0] &= a_0 = x \circ a_0 \\ [a_0,a_1] &= a_0+ \frac{1}{a_1} = \left (a_0 + \frac{1}{x} \right) \circ a_1 \\ [a_0,a_1,a_2] &= a_0+ \frac{1}{a_1 + \cfrac{1}{a_2}} = \left (a_0 + \frac{1}{x} \right) \circ \left (a_1 + \frac{1}{x} \right) \circ a_2 \end{align*} 一般に \[ [a_0,a_1,\cdots,a_n] = \left (a_0 + \frac{1}{x} \right) \circ \left (a_1 + \frac{1}{x} \right) \circ \cdots \circ \left (a_{n-1} + \frac{1}{x} \right) \circ a_{n} \] が成立する。 分数関数 \[ a_k + \frac{1}{x} = \frac{a_k x +1}{x+0} \] は行列 \[ \pmatrix{a_k & 1 \\ 1 & 0} \] に対応していることに注目し、 \[ \pmatrix{z_1 & z_2 \\ z_3 & z_4} = \prod_{k=0}^{n-1} \pmatrix{a_k &1 \\ 1 & 0} \] とおく。(定理の仮定から$z_1,z_2,z_3,z_4$はすべて自然数である。)
1次分数関数の合成は行列を用いて計算できるから \[ [a_0,a_1,\cdots,a_n] = \frac{z_1x+z_2}{z_3x+z_4} \circ a_n = \frac{z_1 a_n +z_2}{z_3 a_n+z_4} \] が得られる。 ここで \[ \pmatrix{p_n \\ q_n} = \pmatrix{z_1 a_n +z_2\\ z_3 a_n+z_4} \] とおくと (これが証明中の $p_n,q_n$ の定義.) \[ \frac{p_n}{q_n} = [a_0,a_1,\cdots,a_n] \] が成り立つことに注意する。(ただし左辺が既約かどうかはまだわからない. もし既約であれば、定理における$p_n,q_n$と一致する.) \[ \pmatrix{p_n \\ q_n} = \pmatrix{z_1 a_n +z_2\\ z_3 a_n+z_4} = \pmatrix{z_1 & z_2 \\ z_3 & z_4} \pmatrix{a_n \\ 1} \] とかけるから \[ \pmatrix{p_n \\ q_n} =\pmatrix{z_1 & z_2 \\ z_3 & z_4} \pmatrix{a_n \\ 1}= \left( \prod_{k=0}^{n-1} \pmatrix{a_k &1 \\ 1 & 0} \right) \pmatrix{a_n \\ 1} \] が得られる。これから \begin{align*} \pmatrix{p_{n+1} \\ q_{n+1}} &= \left( \prod_{k=0}^{n} \pmatrix{a_k &1 \\ 1 & 0} \right) \pmatrix{a_{n+1} \\ 1}\\ &= \left( \prod_{k=0}^{n-1} \pmatrix{a_k &1 \\ 1 & 0} \right) \pmatrix{a_n &1 \\ 1 & 0} \pmatrix{a_{n+1} \\ 1}\\ &= \left( \prod_{k=0}^{n-1} \pmatrix{a_k &1 \\ 1 & 0} \right) \pmatrix{a_n a_{n+1} +1 \\ a_{n+1} } \end{align*} よってまとめて、 \[ \pmatrix{p_{n+1} & p_{n} \\ q_{n+1} & q_{n}} = \left( \prod_{k=0}^{n-1} \pmatrix{a_k &1 \\ 1 & 0} \right) \pmatrix{ a_n a_{n+1} +1 & a_n \\a_{n+1} & 1} \] 気づきにくいが \[ \pmatrix{ a_n a_{n+1} +1 & a_n \\a_{n+1} & 1} = \pmatrix{a_n &1 \\ 1 & 0} \pmatrix{a_{n+1} &1 \\ 1 & 0} \] を用いると、 \[ \pmatrix{p_{n+1} & p_{n} \\ q_{n+1} & q_{n}} = \prod_{k=0}^{n+1} \pmatrix{a_k &1 \\ 1 & 0} \] とかけることがわかる。 両辺で行列式を考えると、行列式の性質より \[ \begin{vmatrix} p_{n+1} & p_{n} \\ q_{n+1} & q_{n} \end{vmatrix} = \prod_{k=0}^{n+1} \begin{vmatrix} a_k &1 \\ 1 & 0 \end{vmatrix} \] が成立するから \[ p_{n+1} q_{n} - p_{n} q_{n+1} = (-1)^{n} \qquad \text{(eq1)} \] が得られる。もし、分数 \[ \frac{p_n}{q_n}\] が既約でないとすると、ある素数で(eq1)の左辺が割れることになるが 右辺は素数では割れないので、矛盾。したがって、 $p_n/q_n$ は既約である。ゆえに、この $p_n,q_n$ は定理で定義される $p_n,q_n$ と一致し、(eq1)が成立する。

例. \[[1] = \frac{1}{1}\] \[[1,2] = 1+\frac{1}{2} = \frac{3}{2}\] \[[1,2,3] = 1+\cfrac{1}{2+\cfrac{1}{3}}= \frac{10}{7} \] これらを左から並べると \[ \frac{10}{7},\frac{3}{2},\frac{1}{1} \] 隣り合う分数に対して、 \[ \text{(左)分子×(右)分母}-\text{(右)分子×(左)分母} \] を実行すると $\pm1$ になる。 \begin{align*} &10 \times 2 - 3 \times 7 = -1\\ &3 \times 1 - 1 \times 2 = 1 \end{align*}

不定方程式の解法

今示した連分数の性質を用いて、1次の不定方程式を解く。

例題. \[ 17x - 7y = 1\] の整数解を求めよ。

解. 係数から得られる分数$17/7$を連分数展開する。 \[\frac{17}{7} =2+\cfrac{1}{2+\cfrac{1}{3}} = [2,2,3]\] 右辺の最後を一つ省略した連分数を計算すると \[ [2,2] = 2 + \frac{1}{2} = \frac{5}{2} \] が得られる。 よって \[ \frac{17}{7}, \quad \frac{5}{2} \] とならべて、 \[ \text{(左)分子×(右)分母}-\text{(右)分子×(左)分母} \] を行うと連分数の性質から$\pm1$になる。 実際 \[ 17 \times 2 - 5 \times 7 = -1 \] となっていることが確認できるので、これを少し変形して \[ 17 \times (-2) - 7 \times (-5) = 1 \] が得られる。したがって \[x=-2,\quad y=-5\] が一つの解となる。一般解はこの特殊解を用いて \[ \begin{cases} x = -2 + 7t \\ y = -5 + 17t \end{cases} \] と表現できる。したがって、正の解としては \[ x = 5, \quad y=12 \] が得られることがわかる。