この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

整数論の問題

難易度 1教科書の例題レベル大学数学整数論

有理数 $\frac{67}{29}$ の正則連分数展開を
$\frac{67}{29} = [a_{0}; a_{1}, a_{2}, a_{3}] = a_{0} + \frac{1}{a _{1} + \frac{1}{a _{2} + \frac{1}{a _{3}}}}$
とする。ここで $a_{0}$ は整数、 $a_{1}, a_{2}, a_{3}$ は正の整数で、 $a_{3} ≧ 2$ とする。 $k = 0, 1, 2, 3$ に対して、第 $k$ 近似分数を $\frac{p _{k}}{q _{k}} = [a_{0}; a_{1}, \dots, a_{k}]$ （既約分数、 $q_{k} > 0$ ）と定める。近似分数 $\frac{p _{2}}{q _{2}}$ を既約分数で求めよ。

この問題で使うもの

連分数展開と近似分数（説明と入口の問題）

この問題を解けるようになるまで（21 技能）

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

「連分数展開と近似分数」の技能を使います。まずユークリッドの互除法で $67$ と $29$ を割り算していき、各段の商を並べて連分数展開 $[a_{0}; a_{1}, a_{2}, a_{3}]$ を求めましょう。

ヒント 2

近似分数は漸化式 $p_{k} = a_{k} p_{k - 1} + p_{k - 2}$ , $q_{k} = a_{k} q_{k - 1} + q_{k - 2}$ （初期値 $p_{- 2} = 0, p_{- 1} = 1, q_{- 2} = 1, q_{- 1} = 0$ ）で順に計算できます。

ヒント 3

互除法から $\frac{67}{29} = [2; 3, 4, 2]$ です。 $p_{0} / q_{0} = 2/1$ , $p_{1} / q_{1} = 7/3$ となるので、あと 1 回漸化式を使えば $p_{2} / q_{2}$ が求まります。

答えと解説

答えを見る

\frac{30}{13}

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

手順 1：互除法で部分商を求める。
$67$ と $29$ に互除法を行うと
$67 = 2 \cdot 29 + 9, 29 = 3 \cdot 9 + 2, 9 = 4 \cdot 2 + 1, 2 = 2 \cdot 1$
となる。各段の商が部分商なので
$\frac{67}{29} = [2; 3, 4, 2]$
すなわち $a_{0} = 2, a_{1} = 3, a_{2} = 4, a_{3} = 2$ である（最後の部分商 $a_{3} = 2 ≧ 2$ なので条件に合う）。

手順 2：漸化式で近似分数を計算する。
初期値を $p_{- 2} = 0, p_{- 1} = 1, q_{- 2} = 1, q_{- 1} = 0$ とし、
$p_{k} = a_{k} p_{k - 1} + p_{k - 2}, q_{k} = a_{k} q_{k - 1} + q_{k - 2}$
を使う。
- $k = 0$ : $p_{0} = 2 \cdot 1 + 0 = 2, q_{0} = 2 \cdot 0 + 1 = 1$
- $k = 1$ : $p_{1} = 3 \cdot 2 + 1 = 7, q_{1} = 3 \cdot 1 + 0 = 3$
- $k = 2$ : $p_{2} = 4 \cdot 7 + 2 = 30, q_{2} = 4 \cdot 3 + 1 = 13$
- $k = 3$ : $p_{3} = 2 \cdot 30 + 7 = 67, q_{3} = 2 \cdot 13 + 3 = 29$

$p_{3} / q_{3} = 67/29$ で元の数に戻るので、計算は正しい。

手順 3：検算（既約であることの確認）。
$p_{3} q_{2} - p_{2} q_{3} = 67 \cdot 13 - 30 \cdot 29 = 871 - 870 = 1 = (- 1)^{3 - 1}$ が成り立つ。同様に $p_{2} q_{1} - p_{1} q_{2} = 30 \cdot 3 - 7 \cdot 13 = 90 - 91 = - 1$ なので、 $30$ と $13$ の公約数は $1$ を割り切り、 $\frac{30}{13}$ は既約分数である。

実際、 $[2; 3, 4] = 2 + \frac{1}{3 + \frac{1}{4}} = 2 + \frac{4}{13} = \frac{30}{13}$ とも一致する。

よって $\frac{p _{2}}{q _{2}} = \frac{30}{13}$ 。

別解

ユークリッドの互除法を使う。
$67 = 2 \cdot 29 + 9$ より $a_{0} = 2$ 。
$29 = 3 \cdot 9 + 2$ より $a_{1} = 3$ 。
$9 = 4 \cdot 2 + 1$ より $a_{2} = 4$ 。
$2 = 2 \cdot 1$ より $a_{3} = 2$ （ $a_{3} ≧ 2$ を満たす）。
よって $\frac{67}{29} = [2; 3, 4, 2]$ 。

漸化式 $p_{k} = a_{k} p_{k - 1} + p_{k - 2}$ , $q_{k} = a_{k} q_{k - 1} + q_{k - 2}$ を使う。初期値は $p_{0} / q_{0} = 2/1$ , $p_{1} / q_{1} = (a_{1} a_{0} + 1) / a_{1} = 7/3$ 。
これより $p_{2} = 4 \cdot 7 + 2 = 30$ , $q_{2} = 4 \cdot 3 + 1 = 13$ 。

検算: $[2; 3, 4] = 2 + \frac{1}{3 + \frac{1}{4}} = 2 + \frac{4}{13} = \frac{30}{13}$ 。
$30$ と $13$ は互いに素なので既約である。

整数論の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題