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

整数論の問題

難易度 4大学院入試の標準レベル大学数学整数論

$31$ の正則連分数展開を $31 = [a_{0}; a_{1}, a_{2}, \dots]$ とし、0 以上の整数 $n$ に対して第 $n$ 近似分数を
$\frac{p _{n}}{q _{n}} = [a_{0}; a_{1}, \dots, a_{n}]$
とする。ただし $p_{n}, q_{n}$ は互いに素な整数で $q_{n} > 0$ とする。 $n$ が 0 以上の整数全体を動くとき、整数 $p_{n}^{2} - 31 q_{n}^{2}$ がとる値全体の集合を求めよ。

この問題で使うもの

√d の連分数展開とペル方程式の基本解（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

まず $31$ の連分数展開を、完全商 $α_{k} = (P_{k} + 31) / Q_{k}$ の形で追いかけて求め、周期を見つけましょう。

ヒント 2

$31 = \frac{p _{n} α _{n + 1} + p _{n - 1}}{q _{n} α _{n + 1} + q _{n - 1}}$ に $α_{n + 1} = (P_{n + 1} + 31) / Q_{n + 1}$ を代入して有理部分と無理部分を比べ、 $p_{n} q_{n - 1} - p_{n - 1} q_{n} = (- 1)^{n - 1}$ と組み合わせると、 $p_{n}^{2} - 31 q_{n}^{2}$ を $Q_{n + 1}$ で表せます。

ヒント 3

$31 = [5; 1, 1, 3, 5, 3, 1, 1, 10]$ で、 $Q_{1}, \dots, Q_{8}$ は $6, 5, 3, 2, 3, 5, 6, 1$ です。 $p_{n}^{2} - 31 q_{n}^{2} = (- 1)^{n + 1} Q_{n + 1}$ と周期が偶数であることを使って、符号付きの値を並べましょう。

答えと解説

答えを見る

{- 6, - 3, 1, 2, 5}

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

解説を読む

連分数展開の計算 完全商を $α_{k} = \frac{P _{k} + 31}{Q _{k}}$ とおくと、 $P_{0} = 0, Q_{0} = 1$ で、
$a_{k} = ⌊ α_{k} ⌋, P_{k + 1} = a_{k} Q_{k} - P_{k}, Q_{k + 1} = \frac{31 - P _{k + 1}^{2}}{Q _{k}}$
により順に求まる（ $α_{k + 1} = 1/ (α_{k} - a_{k})$ を有理化すると得られる）。 $5 < 31 < 6$ に注意して計算すると

$k$	0	1	2	3	4	5	6	7	8
$P_{k}$	0	5	1	4	5	5	4	1	5
$Q_{k}$	1	6	5	3	2	3	5	6	1
$a_{k}$	5	1	1	3	5	3	1	1	10

となる。 $(P_{9}, Q_{9}) = (10 \cdot 1 - 5, (31 - 25) /1) = (5, 6) = (P_{1}, Q_{1})$ なので、以後は $k = 1$ からの繰り返しになり、
$31 = [5; 1, 1, 3, 5, 3, 1, 1, 10]$
（周期 8）で、 $k \geq 1$ に対して $Q_{k + 8} = Q_{k}$ である。

$p_{n}^{2} - 31 q_{n}^{2}$ と $Q_{n + 1}$ の関係 $p_{- 1} = 1, q_{- 1} = 0$ とおくと、近似分数の漸化式から
$31 = \frac{p _{n} α _{n + 1} + p _{n - 1}}{q _{n} α _{n + 1} + q _{n - 1}}$
が成り立つ。 $P = P_{n + 1}, Q = Q_{n + 1}$ として $α_{n + 1} = (P + 31) / Q$ を代入し、分母を払うと
$31 q_{n} + (q_{n} P + q_{n - 1} Q) 31 = (p_{n} P + p_{n - 1} Q) + p_{n} 31 .$
$31$ は無理数なので、有理部分と無理部分を比べて
$p_{n} = q_{n} P + q_{n - 1} Q, 31 q_{n} = p_{n} P + p_{n - 1} Q .$
よって
$p_{n}^{2} - 31 q_{n}^{2} = p_{n} (q_{n} P + q_{n - 1} Q) - q_{n} (p_{n} P + p_{n - 1} Q) = Q (p_{n} q_{n - 1} - p_{n - 1} q_{n}) .$
よく知られた関係 $p_{n} q_{n - 1} - p_{n - 1} q_{n} = (- 1)^{n - 1}$ を使うと
$p_{n}^{2} - 31 q_{n}^{2} = (- 1)^{n + 1} Q_{n + 1} .$

値の決定 $k = n + 1$ とおくと、値は $(- 1)^{k} Q_{k}$ （ $k \geq 1$ ）である。 $k = 1, 2, \dots, 8$ について
$- 6, 5, - 3, 2, - 3, 5, - 6, 1$
となる。周期 8 は偶数なので、 $Q_{k}$ だけでなく符号 $(- 1)^{k}$ も周期 8 で繰り返す。よって現れる値はこの 8 個で尽きる。

検算 $p_{0} / q_{0} = 5/1$ : $25 - 31 = - 6$ 。 $p_{1} / q_{1} = 6/1$ : $36 - 31 = 5$ 。 $p_{2} / q_{2} = 11/2$ : $121 - 124 = - 3$ 。 $p_{3} / q_{3} = 39/7$ : $1521 - 1519 = 2$ 。 $p_{7} / q_{7} = 1520/273$ : $2310400 - 2310399 = 1$ 。いずれも一致する。

したがって求める集合は ${- 6, - 3, 1, 2, 5}$ である。

別解

$p_{n}^{2} - 31 q_{n}^{2}$ は連分数の完全商の分母を使って求められる。 $31 = 5.5677 \dots$ から、 $m_{0} = 0, d_{0} = 1, a_{0} = 5$ とし、 $m_{k + 1} = a_{k} d_{k} - m_{k}$ 、 $d_{k + 1} = (31 - m_{k + 1}^{2}) / d_{k}$ 、 $a_{k + 1} = ⌊(31 + m_{k + 1}) / d_{k + 1} ⌋$ を計算する。

$k = 1$ : $m_{1} = 5, d_{1} = 6, a_{1} = 1$
$k = 2$ : $m_{2} = 1, d_{2} = 5, a_{2} = 1$
$k = 3$ : $m_{3} = 4, d_{3} = 3, a_{3} = 3$
$k = 4$ : $m_{4} = 5, d_{4} = 2, a_{4} = 5$
$k = 5$ : $m_{5} = 5, d_{5} = 3, a_{5} = 3$
$k = 6$ : $m_{6} = 4, d_{6} = 5, a_{6} = 1$
$k = 7$ : $m_{7} = 1, d_{7} = 6, a_{7} = 1$
$k = 8$ : $m_{8} = 5, d_{8} = 1, a_{8} = 10$

よって $31 = [5; 1, 1, 3, 5, 3, 1, 1, 10]$ 、周期は 8。 $d_{8} = 1$ で周期が閉じ、 $d_{9} = d_{1} = 6$ に戻る。

一般に $p_{n}^{2} - 31 q_{n}^{2} = (- 1)^{n + 1} d_{n + 1}$ である。したがって
- $n = 0$ : $- 6$
- $n = 1$ : $+ 5$
- $n = 2$ : $- 3$
- $n = 3$ : $+ 2$
- $n = 4$ : $- 3$
- $n = 5$ : $+ 5$
- $n = 6$ : $- 6$
- $n = 7$ : $+ 1$

周期が偶数 (8) なので、以降は符号も含めてこの並びを繰り返す。値の集合は ${- 6, - 3, 1, 2, 5}$ 。

検算: $n = 0$ : $5^{2} - 31 = - 6$ 。 $n = 1$ : $6/1$ で $36 - 31 = 5$ 。 $n = 2$ : $11/2$ で $121 - 124 = - 3$ 。 $n = 3$ : $[5; 1, 1, 3] = 39/7$ で $1521 - 1519 = 2$ 。 $n = 7$ で $1$ になる（基本解）ことも周期から整合する。

整数論の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題