連分数と有理近似 ― 無理数を「一番良い分数」で近似する

連分数がユークリッド互除法の別の顔であることを示し，収束分数による最良有理近似，√2 の連分数展開，ペル方程式，Stern-Brocot 木を解説します．

2026年2月27日

$π \approx 3.14159 \dots$ を分数で近似するとき， $22/7 = 3.142 \dots$ が驚くほど良い近似を与えます．分母がたった $7$ で，誤差は $0.04%$ 未満です．なぜ $22/7$ はこんなに良いのでしょうか？この問いに答えるのが連分数の理論です．

1 連分数の定義

定義 1 (連分数).

実数

α

の（正則）連分数展開とは，

α = a_{0} + \frac{1}{a _{1} + \frac{1}{a _{2} + \frac{1}{a _{3} + \dots}}}

という表示です．

a_{0} \in Z

，

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

を部分商と呼び，

α = [a_{0}; a_{1}, a_{2}, a_{3}, \dots]

と略記します．

例 2.

3.245 = 3 + 0.245 = 3 + 1/ (4 + 1/ (12 + 1/4))

，つまり

3.245 = [3; 4, 12, 4]

．

2 ユークリッドの互除法との関係

連分数展開とユークリッドの互除法はまったく同じ計算です．

例 3.

g cd (47, 13)

のユークリッドの互除法：

$47 = 3 \times 13 + 8$
$13 = 1 \times 8 + 5$
$8 = 1 \times 5 + 3$
$5 = 1 \times 3 + 2$
$3 = 1 \times 2 + 1$
$2 = 2 \times 1 + 0$

商の列は

3, 1, 1, 1, 1, 2

．一方

47/13 = [3; 1, 1, 1, 1, 2]

です．ユークリッドの互除法の商が，そのまま連分数の部分商になっています．

注意 4.

有理数の連分数展開は有限で終わり，無理数の連分数展開は無限に続きます．これはユークリッドの互除法が有理数では有限ステップで終了する（余りが

0

になる）のと対応しています．

3 収束分数 ― 「打ち切り」で良い近似を得る

定義 5 (収束分数).

連分数

α = [a_{0}; a_{1}, a_{2}, \dots]

の

n

次収束分数（convergent）とは，

\frac{p _{n}}{q _{n}} = [a_{0}; a_{1}, a_{2}, \dots, a_{n}]

です．

収束分数は漸化式で効率的に計算できます．

定理 6 (収束分数の漸化式).

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

初期値：

p_{- 1} = 1, p_{- 2} = 0, q_{- 1} = 0, q_{- 2} = 1

．

定理 7 (収束分数の性質).

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

注意 8.

この等式は，隣り合う収束分数

p_{n} / q_{n}

と

p_{n - 1} / q_{n - 1}

の差が

\pm 1/ (q_{n} q_{n - 1})

であることを意味します．

q_{n}

は単調増加するので，差はどんどん小さくなり，

p_{n} / q_{n}

は

α

に急速に収束します．

4 最良有理近似

定理 9 (最良有理近似).

p_{n} / q_{n}

が

α

の

n

次収束分数であるとき，分母が

q_{n}

以下のいかなる分数

a / b

（

b \leq q_{n}

，

a / b \neq = p_{n} / q_{n}

）に対しても，

α - \frac{p _{n}}{q _{n}} < α - \frac{a}{b}

が成り立ちます．

注意 10.

つまり収束分数は，その分母以下の分数の中で

α

に最も近い分数です．

22/7

が

π

の良い近似であるのは，

22/7

が

π = [3; 7, 15, 1, 292, \dots]

の第1次収束分数だからです．

5 $2$ の連分数展開

例 11 (

2

の連分数).

2 = 1 + (2 - 1)

．

2 - 1 = 1/ (2 + 1)

なので，

2 = 1 + \frac{1}{2 + 1} = 1 + \frac{1}{2 + ( 2 - 1 )} = 1 + \frac{1}{2 + \frac{1}{2 + 1}}

これは循環します：

2 = [1; \overline{2}]

（

2

が無限に繰り返される）．

収束分数：

1/1, 3/2, 7/5, 17/12, 41/29, \dots

17/12 = 1.41 \overline{6}

は

2 = 1.41421 \dots

の良い近似です．

注意 12.

一般に，

D

（

D

が平方数でない正の整数）の連分数展開は純循環であり，二次無理数と循環連分数は1対1に対応します（ラグランジュの定理）．

6 ペル方程式

$D$ の連分数展開は，ペル方程式の解法に直結します．

定義 13 (ペル方程式).

正の整数

D

（平方数でない）に対し，

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

をペル方程式と呼びます．

定理 14.

ペル方程式

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

の最小正整数解

(x_{1}, y_{1})

は，

D

の連分数展開の循環節の直前の収束分数

p_{k} / q_{k}

によって

(x_{1}, y_{1}) = (p_{k}, q_{k})

と得られます．

例 15.

D = 2

：

2 = [1; \overline{2}]

の循環節の長さは 1．

p_{0} / q_{0} = 1/1

より

(x, y) = (1, 1)

：

1 - 2 = - 1

（符号が違う）．

p_{1} / q_{1} = 3/2

より

(x, y) = (3, 2)

：

9 - 8 = 1

．正解です．

7 Stern-Brocot 木

定義 16 (Stern-Brocot 木).

0/1

と

1/0

から出発し，隣り合う分数

a / b

と

c / d

の中間数（mediant）

\frac{a + c}{b + d}

を挿入していくことで得られる二分木です．

注意 17.

Stern-Brocot 木には次の驚くべき性質があります：

すべての正の有理数がちょうど1回ずつ，既約分数として現れます
木は常にソートされています（左の子 < 親 < 右の子）
各ノードへのパス（LR 列）が連分数展開に対応します
二分探索により，与えられた実数に最も近い分母 $\leq N$ の分数を $O (lo g N)$ で見つけられます

8 まとめ

連分数展開はユークリッドの互除法の別の顔です
収束分数は「その分母以下で最良」の有理近似を与えます
$D$ の連分数展開は循環し，ペル方程式の解法に直結します
Stern-Brocot 木はすべての正の有理数を体系的に並べる構造です

次の最終記事では，このシリーズで学んだ定理たちが RSA 暗号の各パーツにどう対応するかを見ていきます．

整数論代数学教科書の行間

Folio公式

数学の「教科書が書かない行間」をLaTeXで．Folio公式アカウントです．

0 followers·105 articles

連分数と有理近似 ― 無理数を「一番良い分数」で近似する

1 連分数の定義

2 ユークリッドの互除法との関係

3 収束分数 ― 「打ち切り」で良い近似を得る

4 最良有理近似

5 $2$ の連分数展開

6 ペル方程式

7 Stern-Brocot 木

8 まとめ

Share your expertise with the world

More from Folio公式

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

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

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

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

1 連分数の定義

2 ユークリッドの互除法との関係

3 収束分数 ― 「打ち切り」で良い近似を得る

4 最良有理近似

5 2​の連分数展開

6 ペル方程式

7 Stern-Brocot 木

8 まとめ

Share your expertise with the world

More from Folio公式

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

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

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

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

5 $2$ の連分数展開