2014/11/24

連分数展開とその計算方法

分野: 数列  レベル: 最難関大学

  • 有理数の連分数展開はユークリッドの互除法に対応している
  • 有理数 $\iff$ 連分数展開が有限回で終わる

主に有理数の連分数展開に関する基本的な知識を解説します。連分数を背景とした入試問題もいくつか出題されています。

連分数と正則連分数

・分数の分母にさらに分数が含まれている以下のような形のものを連分数と言います:
$a_0+\dfrac{b_1}{a_1+\frac{b_2}{a_2+\frac{b_3}{a_3+\cdots}}}$

・特に,分子 $b_1,\:b_2,\cdots$ が全て $1$ であり,$a_0$ が整数,$a_1,\:a_2,\cdots$ が正の整数であるような連分数を正則連分数と言います。連分数の中でも正則連分数を扱うことがほとんどなので,正則連分数のことを単に「連分数」ということもあります。

・正則連分数は $a_0,a_1,\cdots$ の情報だけ持っておけばすぐに復元できます。そこで,分数式を下にズラっと書くと場所を取ってしまうので,正則連分数を以下のように数列を用いて表記することが多いです:
$a_0+\dfrac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3}}}=[a_0;a_1,a_2,a_3]$

有理数の連分数展開の例

有理数の連分数展開は割り算を繰り返し行うことで機械的にできます。一般的に議論する前に連分数展開の具体例を見てみます。

$\dfrac{36}{11}$ を正則連分数展開せよ。

・ $36$ を $11$ で割った商は $3$ ,余りは $3$ なので,
$\dfrac{36}{11}=3+\dfrac{3}{11}=3+\dfrac{1}{\frac{11}{3}}$

・ $11$ を $3$ で割った商は $3$ ,余りは $2$ なので,
$\dfrac{11}{3}=3+\dfrac{1}{\frac{3}{2}}$

・ $3$ を $2$ で割った商は $1$ ,余りは $1$ なので,
$\dfrac{3}{2}=1+\dfrac{1}{2}$

以上より,$\dfrac{36}{11}=3+\dfrac{1}{3+\dfrac{1}{1+\frac{1}{2}}}=[3;3,1,2]$

無理数でも同様に連分数展開はできますが,いつまでも終わることなく続きます(無限連分数)。連分数の理論は無理数のときにもっと面白くなるのですが本記事では深入りしません。

連分数展開とユークリッドの互除法

さきほどの具体例で見たように,連分数展開の方法はユークリッドの互除法に対応しています。→ユークリッドの互除法の証明と不定方程式

もう少しきちんと説明します。
$a$ を $b$ で割った商を $q$,余りを $r$ とおくと,
$a=bp+r$ より,$\dfrac{a}{b}=p+\dfrac{1}{\frac{b}{r}}$ となります。

よって, $\dfrac{a}{b}$ を正則連分数展開するには $\dfrac{b}{r}$ を正則連分数展開すればよい,ということになります。このように,$a$ と $b$ の問題を $b$ と $r$ の問題に帰着させるというのはユークリッドの互除法そのものです!

そして,正則連分数には各段階の商が残ります。これは先ほどの具体例を見れば納得できるでしょう。

有理数は有限正則連分数で表せる

今までの議論により以下の定理が導かれます:

有理数 $\iff$ 有限正則連分数で表せる

  • ($\Rightarrow$)ユークリッドの互除法は有限回で終了するので,有理数なら正則連分数展開が有限回で終了します。
  • ($\Leftarrow$)有限連分数は通分を繰り返して普通の分数にできるので有理数です。
例えば,2011年東大前期理系問2は,この記事の内容を理解していれば非常に簡単に解けます。

Tag: 東大入試数学の良問と背景知識まとめ

分野: 数列  レベル: 最難関大学