連分数とディオファントス近似 ― 有理近似の理論

有限・無限連分数の定義と収束の証明を与え，近似分数の性質を厳密に示す．最良有理近似の理論，ペル方程式$x^2 - Dy^2 = 1$の解法，Stern-Brocot木を解説する．

2026年2月27日

1 連分数の定義

定義 1 (有限連分数).

a_{0} \in Z

，

a_{1}, a_{2}, \dots, a_{n} \in Z_{> 0}

に対して

[a_{0}; a_{1}, a_{2}, \dots, a_{n}] = a_{0} + \frac{1}{a _{1} + \frac{1}{a _{2} + \frac{1}{⋱ + \frac{1}{a _{n}}}}}

を有限連分数（finite continued fraction）という．

a_{i}

を部分商（partial quotient）という．

定理 2.

任意の有理数

r

は有限連分数として表される．その表し方はユークリッド互除法に対応する．

証明.

r = p / q

（

q > 0

）に対して割り算の原理より

p = a_{0} q + r_{1}

（

0 \leq r_{1} < q

）．

r_{1} = 0

ならば

r = a_{0}

．

r_{1} > 0

ならば

r = a_{0} + r_{1} / q = a_{0} + 1/ (q / r_{1})

で

q / r_{1}

に同じ操作を繰り返す．ユークリッド互除法は有限回で終了するので有限連分数が得られる． □

2 近似分数

定義 3 (近似分数).

[a_{0}; a_{1}, \dots, a_{n}, \dots]

の第

k

近似分数（convergent）を

C_{k} = p_{k} / q_{k} = [a_{0}; a_{1}, \dots, a_{k}]

とする．

p_{k}, q_{k}

は漸化式

p_{k} = a_{k} p_{k - 1} + p_{k - 2}, q_{k} = a_{k} q_{k - 1} + q_{k - 2}

で定まる（

p_{- 1} = 1

，

p_{- 2} = 0

，

q_{- 1} = 0

，

q_{- 2} = 1

）．

定理 4 (近似分数の基本性質).

$p_{k} q_{k - 1} - p_{k - 1} q_{k} = (- 1)^{k - 1}$ （ $k \geq 0$ ）．
$g cd (p_{k}, q_{k}) = 1$ ．
$C_{0} < C_{2} < C_{4} < \dots < α < \dots < C_{5} < C_{3} < C_{1}$ （ $α$ は無限連分数の値）．

証明.

(1)

k

に関する帰納法．

k = 0

：

p_{0} q_{- 1} - p_{- 1} q_{0} = a_{0} \cdot 0 - 1 \cdot 1 = - 1 = (- 1)^{- 1}

．帰納段階：

p_{k} q_{k - 1} - p_{k - 1} q_{k} = (a_{k} p_{k - 1} + p_{k - 2}) q_{k - 1} - p_{k - 1} (a_{k} q_{k - 1} + q_{k - 2}) = - (p_{k - 1} q_{k - 2} - p_{k - 2} q_{k - 1}) = - (- 1)^{k - 2} = (- 1)^{k - 1}

．

(2) (1) より

p_{k} q_{k - 1} - p_{k - 1} q_{k} = \pm 1

なので

g cd (p_{k}, q_{k}) ∣ 1

．

(3)

C_{k} - C_{k - 1} = (p_{k} q_{k - 1} - p_{k - 1} q_{k}) / (q_{k} q_{k - 1}) = (- 1)^{k - 1} / (q_{k} q_{k - 1})

より，偶数番目は増加，奇数番目は減少．

C_{k} - C_{k - 2} = (- 1)^{k - 1} a_{k} / (q_{k} q_{k - 2})

の符号も確認でき，偶数添字列は狭義単調増加，奇数添字列は狭義単調減少． □

3 無限連分数の収束

定理 5.

a_{0} \in Z

，

a_{i} \in Z_{> 0}

（

i \geq 1

）に対して

lim_{k \to \infty} C_{k}

が存在する．

証明.

q_{k} \geq q_{k - 1} + q_{k - 2}

より

q_{k}

は狭義単調増加で

q_{k} \to \infty

．

∣ C_{k} - C_{k - 1} ∣ = 1/ (q_{k} q_{k - 1}) \to 0

なので，有界単調列の収束定理より偶数部分列と奇数部分列はそれぞれ収束し，その差が

0

に収束するから同じ極限を持つ． □

4 最良有理近似

定理 6.

近似分数

p_{k} / q_{k}

は以下の意味で最良有理近似を与える：

1 \leq q \leq q_{k}

かつ

p / q \neq = p_{k} / q_{k}

なる任意の有理数

p / q

に対して

∣ q_{k} α - p_{k} ∣ < ∣ q α - p ∣

．

証明.

p / q \neq = p_{k} / q_{k}

かつ

1 \leq q \leq q_{k}

とする．

p / q

を

p_{k} / q_{k}

と

p_{k - 1} / q_{k - 1}

の整数係数一次結合で表す．

p_{k} q_{k - 1} - p_{k - 1} q_{k} = (- 1)^{k - 1}

より行列

(q_{k} p_{k} q_{k - 1} p_{k - 1})

は行列式

\pm 1

を持つので，整数

s, t

が存在して

q = s q_{k} + t q_{k - 1}

，

p = s p_{k} + t p_{k - 1}

と書ける．

p / q \neq = p_{k} / q_{k}

より

t \neq = 0

．

q \leq q_{k}

かつ

q_{k - 1} \geq 1

より

t

と

s

は異符号でない（

s = 0

の場合は

q = t q_{k - 1} \leq q_{k}

で

t \geq 1

）か，あるいは

∣ s ∣ \leq 1

の範囲に制限される．

q α - p = s (q_{k} α - p_{k}) + t (q_{k - 1} α - p_{k - 1})

が成り立つ．近似分数の基本性質 (3) より

q_{k} α - p_{k}

と

q_{k - 1} α - p_{k - 1}

は異符号である．

t \neq = 0

のとき

s (q_{k} α - p_{k})

と

t (q_{k - 1} α - p_{k - 1})

が同符号（または一方が

0

）であることが

q \geq 1

の条件から導かれる．よって

∣ q α - p ∣ = ∣ s ∣ \cdot ∣ q_{k} α - p_{k} ∣ + ∣ t ∣ \cdot ∣ q_{k - 1} α - p_{k - 1} ∣ \geq ∣ q_{k - 1} α - p_{k - 1} ∣ > ∣ q_{k} α - p_{k} ∣.

最後の不等式は

∣ q_{k} α - p_{k} ∣ = ∣ C_{k} - α ∣ \cdot q_{k} < 1/ (q_{k + 1}) \leq 1/ q_{k}

と

∣ q_{k - 1} α - p_{k - 1} ∣ \geq ∣ q_{k} α - p_{k} ∣

の精密な評価（

∣ C_{k - 1} - α ∣ > ∣ C_{k} - α ∣

と

q_{k - 1} < q_{k}

の組合せ）から従う． □

注意 7.

この定理は，連分数展開の近似分数が分母の大きさの制約のもとで最良の有理近似を与えるという深い結果である．

5 ペル方程式

定理 8.

D

が平方数でない正整数のとき，ペル方程式

x^{2} - D y^{2} = 1

の正整数解は無限に存在し，最小解

(x_{1}, y_{1})

は

D

の連分数展開の近似分数から得られる．すべての解は

(x_{n}, y_{n})

（

x_{n} + y_{n} D = (x_{1} + y_{1} D)^{n}

）で与えられる．

証明.

D = [a_{0}; \overline{a_{1}, \dots, a_{r}}]

は周期的連分数展開を持つ．周期

r

の近似分数

p_{r - 1} / q_{r - 1}

が

p_{r - 1}^{2} - D q_{r - 1}^{2} = (- 1)^{r}

を満たす．

r

が偶数なら

(p_{r - 1}, q_{r - 1})

が最小解．

r

が奇数なら

(p_{2 r - 1}, q_{2 r - 1})

が最小解．すべての解が

(x_{1} + y_{1} D)

のべき乗で得られることは，

Z [D]

のノルム写像の乗法性から従う． □

例 9.

x^{2} - 2 y^{2} = 1

．

2 = [1; \overline{2}]

で

C_{0} = 1/1

，

C_{1} = 3/2

．

3^{2} - 2 \cdot 2^{2} = 1

より最小解は

(3, 2)

．次の解：

(3 + 22)^{2} = 17 + 122

より

(17, 12)

．

連分数とディオファントス近似 ― 有理近似の理論

1 連分数の定義

2 近似分数

3 無限連分数の収束

4 最良有理近似

5 ペル方程式

関連する「教科書の行間」記事

Share your expertise with the world

More from Folio公式

Folio LaTeXの基本 ― 標準LaTeXとの違いと始め方

カタラン数はなぜどこにでも現れるのか ― 括弧列・二分木・格子経路の不思議な一致

漸化式と母関数 ― 数列を「関数」にすると何が見えるか

包除原理はなぜ「足して引いて」を繰り返すのか ― ベン図からメビウス関数へ