連分数展開と近似分数

互除法で有理数の正則連分数展開 $[a_{0}; a_{1}, \dots, a_{n}]$ を求め、漸化式 $p_{n} = a_{n} p_{n - 1} + p_{n - 2}$ , $q_{n} = a_{n} q_{n - 1} + q_{n - 2}$ で近似分数 $\frac{p _{n}}{q _{n}}$ を計算し、 $p_{n} q_{n - 1} - p_{n - 1} q_{n} = (- 1)^{n - 1}$ を使える

前提

ユークリッドの互除法（数学A 整数の性質）
整数部分と小数部分（数学I 数と式）

この技能までの道筋（20 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

約数の見つけ方（算数整数の性質）
最大公約数と最小公倍数（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
最大公約数と最小公倍数（数学A 整数の性質）
ユークリッドの互除法（数学A 整数の性質）
分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
平方根の意味と根号の簡単化（中学数学数と式）
根号の乗除と加減（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
乗法公式による展開（中学数学数と式）
分母の有理化（中学数学数と式）
乗法公式・分配法則を使う根号の式の展開（中学数学数と式）
根号を含む式の計算と分母の有理化（数学I 数と式）
整数部分と小数部分（数学I 数と式）

説明

有理数 $\frac{a}{b}$ を、整数と「1 割る〜」の入れ子 $a_{0} + \frac{1}{a _{1} + \frac{1}{⋱ + \frac{1}{a _{n}}}}$ の形に書き直すのが連分数展開です。この形を $[a_{0}; a_{1}, \dots, a_{n}]$ と書きます。互除法の商を並べるだけで展開が得られます。さらに途中で打ち切った分数（近似分数） $\frac{p _{k}}{q _{k}}$ を漸化式で順に計算できます。近似分数は元の数をよく近似し、性質 $p_{n} q_{n - 1} - p_{n - 1} q_{n} = (- 1)^{n - 1}$ から $a x - b y = \pm 1$ の整数解もすぐに読み取れます。

なぜそうしてよいのか

【展開が互除法になる理由】 $x = \frac{a}{b}$ の整数部分を $a_{0}$ とすると、小数部分 $x - a_{0}$ は $0$ 以上 $1$ 未満です。 $0$ でなければ $x = a_{0} + \frac{1}{x _{1}}$ （ $x_{1} = \frac{1}{x - a _{0}} > 1$ ）と書けるので、次は $x_{1}$ の整数部分 $a_{1}$ を取り出します。これを繰り返します。 $a = a_{0} b + r$ （ $0 \leq r < b$ ）のとき $x - a_{0} = \frac{r}{b}$ なので、 $x_{1} = \frac{b}{r}$ です。つまり各段階で行っているのは、互除法の 1 ステップ「 $b$ を $r$ で割る」そのものです。互除法は必ず余り $0$ で止まるので、有理数の展開は有限で終わり、 $a_{1}, a_{2}, \dots$ は正の整数になります。 $a_{0}$ は「 $x$ 以下の最大の整数」で、負のこともあります。なお $n \geq 1$ のとき最後の項は $a_{n} \geq 2$ とします（ $[\dots, a_{n}] = [\dots, a_{n} - 1, 1]$ なので、こう決めると展開が 1 通りに定まります）。

【漸化式の理由】 $p_{- 2} = 0, q_{- 2} = 1, p_{- 1} = 1, q_{- 1} = 0$ と置き、 $p_{k} = a_{k} p_{k - 1} + p_{k - 2}$ , $q_{k} = a_{k} q_{k - 1} + q_{k - 2}$ で $p_{k}, q_{k}$ を定めます。このとき、正の実数 $t$ に対して $[a_{0}; a_{1}, \dots, a_{k - 1}, t] = \frac{t p _{k - 1} + p _{k - 2}}{t q _{k - 1} + q _{k - 2}}$ が成り立ちます。これは $k$ についての帰納法で示せます。 $k = 0$ では右辺は $\frac{t}{1} = t$ で正しいです。 $k$ で正しいとします。 $[a_{0}; \dots, a_{k}, t]$ は $[a_{0}; \dots, a_{k - 1}, a_{k} + \frac{1}{t}]$ と同じ値です。そこで $k$ の式に $a_{k} + \frac{1}{t}$ を代入し、分子と分母に $t$ を掛けて整理すると $\frac{t ( a _{k} p _{k - 1} + p _{k - 2} ) + p _{k - 1}}{t ( a _{k} q _{k - 1} + q _{k - 2} ) + q _{k - 1}} = \frac{t p _{k} + p _{k - 1}}{t q _{k} + q _{k - 1}}$ となり、 $k + 1$ でも正しいことがわかります。ここで $t = a_{k}$ と置くと $[a_{0}; \dots, a_{k}] = \frac{p _{k}}{q _{k}}$ が得られます。

【符号つき恒等式の理由】漸化式を代入すると次のようになります。 $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 = 0$ のときの値は $p_{0} q_{- 1} - p_{- 1} q_{0} = a_{0} \cdot 0 - 1 \cdot 1 = - 1$ なので、 $p_{k} q_{k - 1} - p_{k - 1} q_{k} = (- 1)^{k - 1}$ です。この式から、 $p_{k}$ と $q_{k}$ の公約数は $1$ を割り切ることがわかります。したがって $\frac{p _{k}}{q _{k}}$ は既約分数であり、隣り合う近似分数の差は $\frac{p _{k}}{q _{k}} - \frac{p _{k - 1}}{q _{k - 1}} = \frac{1}{q _{k} q _{k - 1}}$ となります。

手順

互除法を行い、商を順に並べる： $a = a_{0} b + r_{1}, b = a_{1} r_{1} + r_{2}, r_{1} = a_{2} r_{2} + r_{3}, \dots$ を余りが $0$ になるまで続ける。商 $a_{0}, a_{1}, \dots, a_{n}$ から $\frac{a}{b} = [a_{0}; a_{1}, \dots, a_{n}]$ が得られる（ $a_{0}$ は $\frac{a}{b}$ 以下の最大の整数）。
表の左端に初期値 $p_{- 2} = 0, p_{- 1} = 1$ と $q_{- 2} = 1, q_{- 1} = 0$ を書き、その右に $a_{0}, a_{1}, \dots$ を並べる。
左から順に $p_{k} = a_{k} p_{k - 1} + p_{k - 2}$ , $q_{k} = a_{k} q_{k - 1} + q_{k - 2}$ を計算する。これで近似分数 $\frac{p _{k}}{q _{k}}$ が得られる。
検算する：最後の近似分数 $\frac{p _{n}}{q _{n}}$ が元の既約分数 $\frac{a}{b}$ に一致すること、および $p_{n} q_{n - 1} - p_{n - 1} q_{n} = (- 1)^{n - 1}$ が成り立つことを確かめる。

例題

$\frac{67}{29}$ を正則連分数 $[a_{0}; a_{1}, \dots, a_{n}]$ （ $a_{n} \geq 2$ ）に展開し、最後の 1 つ手前の近似分数 $\frac{p _{n - 1}}{q _{n - 1}}$ を求めよ。

例題の解答

【手順1】互除法を行います。 $67 = 2 \cdot 29 + 9$ , $29 = 3 \cdot 9 + 2$ , $9 = 4 \cdot 2 + 1$ , $2 = 2 \cdot 1 + 0$ です。商を並べて $\frac{67}{29} = [2; 3, 4, 2]$ （ $n = 3$ ）となります。
【手順2】初期値を $p_{- 2} = 0, p_{- 1} = 1, q_{- 2} = 1, q_{- 1} = 0$ とします。
【手順3】漸化式で順に計算します。
$k = 0$ （ $a_{0} = 2$ ）： $p_{0} = 2 \cdot 1 + 0 = 2$ , $q_{0} = 2 \cdot 0 + 1 = 1$
$k = 1$ （ $a_{1} = 3$ ）： $p_{1} = 3 \cdot 2 + 1 = 7$ , $q_{1} = 3 \cdot 1 + 0 = 3$
$k = 2$ （ $a_{2} = 4$ ）： $p_{2} = 4 \cdot 7 + 2 = 30$ , $q_{2} = 4 \cdot 3 + 1 = 13$
$k = 3$ （ $a_{3} = 2$ ）： $p_{3} = 2 \cdot 30 + 7 = 67$ , $q_{3} = 2 \cdot 13 + 3 = 29$
近似分数は $\frac{2}{1}, \frac{7}{3}, \frac{30}{13}, \frac{67}{29}$ です。
【手順4】検算します。 $\frac{p _{3}}{q _{3}} = \frac{67}{29}$ で元の数と一致します。また $p_{3} q_{2} - p_{2} q_{3} = 67 \cdot 13 - 30 \cdot 29 = 871 - 870 = 1 = (- 1)^{3 - 1}$ も成り立ちます。
したがって、最後の 1 つ手前の近似分数は $\frac{p _{2}}{q _{2}} = \frac{30}{13}$ です。（おまけとして、 $67 \cdot 13 - 29 \cdot 30 = 1$ から、 $67 x - 29 y = 1$ の整数解の 1 つが $x = 13, y = 30$ であることも読み取れます。）

答え: $\frac{30}{13}$

よくある誤り

初期値を $p_{- 1} = 0, q_{- 1} = 1$ のように逆に置いてしまう誤り。正しくは $p_{- 2} = 0, p_{- 1} = 1, q_{- 2} = 1, q_{- 1} = 0$ です。こう置くと $p_{0} = a_{0}, q_{0} = 1$ , $p_{1} = a_{1} a_{0} + 1, q_{1} = a_{1}$ となり、 $\frac{p _{0}}{q _{0}} = a_{0}$ と一致するので確認できます。
恒等式の符号を $p_{n} q_{n - 1} - p_{n - 1} q_{n} = (- 1)^{n}$ としてしまう誤り。正しくは $(- 1)^{n - 1}$ です。 $n = 1$ で確かめると $p_{1} q_{0} - p_{0} q_{1} = (a_{1} a_{0} + 1) \cdot 1 - a_{0} a_{1} = 1 = (- 1)^{0}$ になります。
連分数の項に互除法の「余り」を並べてしまう誤り（例： $\frac{67}{29}$ を余り $9, 2, 1$ から $[2; 9, 2, 1]$ とする）。正しくは「商」を並べて $[2; 3, 4, 2]$ です。
負の有理数で $a_{0}$ を小数点以下の切り捨てで決めてしまう誤り（例： $- \frac{7}{3}$ で $a_{0} = - 2$ とすると、残り $- \frac{1}{3}$ が負になる）。正しくは $a_{0}$ を「 $x$ 以下の最大の整数」とします。 $- \frac{7}{3} = - 3 + \frac{2}{3}$ なので $a_{0} = - 3$ で、 $- \frac{7}{3} = [- 3; 1, 2]$ となります。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

この技能の次に学べること

√d の連分数展開とペル方程式の基本解（大学数学整数論）