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

整数論の問題

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

$19$ の正則連分数展開を $19 = [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}$ は互いに素な正の整数）とする。 $n$ が 0 以上の整数全体を動くとき、整数 $p_{n}^{2} - 19 q_{n}^{2}$ がとりうる値をすべて求めよ。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

$d$ の連分数展開を $m_{n}, Q_{n}$ の漸化式で求め、公式 $p_{n}^{2} - d q_{n}^{2} = (- 1)^{n + 1} Q_{n + 1}$ を使う。

ヒント 2

$m_{0} = 0, Q_{0} = 1, a_{0} = 4$ から $m_{n + 1} = a_{n} Q_{n} - m_{n}$ , $Q_{n + 1} = \frac{19 - m _{n + 1}^{2}}{Q _{n}}$ , $a_{n + 1} = ⌊ \frac{4 + m _{n + 1}}{Q _{n + 1}} ⌋$ を計算し、 $(m_{n}, Q_{n})$ がくり返すところまで進める。

ヒント 3

$Q_{1}, Q_{2}, \dots$ は $3, 5, 2, 5, 3, 1, \dots$ となり、 $19 = [4; 2, 1, 3, 1, 2, 8]$ （周期 6）。あとは符号 $(- 1)^{n + 1}$ をつけて値を並べる。

答えと解説

答えを見る

{- 3, - 2, 1, 5}

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

解説を読む

$d = 19$ とし、 $m_{0} = 0, Q_{0} = 1, a_{0} = ⌊ 19 ⌋ = 4$ （ $4^{2} = 16 < 19 < 25 = 5^{2}$ より）から始めて、漸化式
$m_{n + 1} = a_{n} Q_{n} - m_{n}, Q_{n + 1} = \frac{19 - m _{n + 1}^{2}}{Q _{n}}, a_{n + 1} = ⌊ \frac{a _{0} + m _{n + 1}}{Q _{n + 1}} ⌋$
で順に計算する。

$m_{1} = 4 \cdot 1 - 0 = 4, Q_{1} = \frac{19 - 16}{1} = 3, a_{1} = ⌊ \frac{8}{3} ⌋ = 2$
$m_{2} = 2 \cdot 3 - 4 = 2, Q_{2} = \frac{19 - 4}{3} = 5, a_{2} = ⌊ \frac{6}{5} ⌋ = 1$
$m_{3} = 1 \cdot 5 - 2 = 3, Q_{3} = \frac{19 - 9}{5} = 2, a_{3} = ⌊ \frac{7}{2} ⌋ = 3$
$m_{4} = 3 \cdot 2 - 3 = 3, Q_{4} = \frac{19 - 9}{2} = 5, a_{4} = ⌊ \frac{7}{5} ⌋ = 1$
$m_{5} = 1 \cdot 5 - 3 = 2, Q_{5} = \frac{19 - 4}{5} = 3, a_{5} = ⌊ \frac{6}{3} ⌋ = 2$
$m_{6} = 2 \cdot 3 - 2 = 4, Q_{6} = \frac{19 - 16}{3} = 1, a_{6} = ⌊ \frac{8}{1} ⌋ = 8 = 2 a_{0}$

さらに $m_{7} = 8 \cdot 1 - 4 = 4, Q_{7} = 3$ となり $(m_{7}, Q_{7}) = (m_{1}, Q_{1})$ なので、以後は同じ計算をくり返す。よって
$19 = [4; 2, 1, 3, 1, 2, 8]$
で周期の長さは $ℓ = 6$ 、 $Q_{n}$ は $n ≧ 1$ で $3, 5, 2, 5, 3, 1$ を周期 6 でくり返す。

公式 $p_{n}^{2} - 19 q_{n}^{2} = (- 1)^{n + 1} Q_{n + 1}$ を $n = 0, 1, \dots, 5$ に用いると
$- Q_{1} = - 3, + Q_{2} = 5, - Q_{3} = - 2, + Q_{4} = 5, - Q_{5} = - 3, + Q_{6} = 1.$
周期 6 は偶数なので、 $n$ を 6 増やしても符号 $(- 1)^{n + 1}$ も $Q_{n + 1}$ も変わらない。したがって $n ≧ 6$ でも同じ値しか現れない。

（確認: 近似分数は $\frac{4}{1}, \frac{9}{2}, \frac{13}{3}, \frac{48}{11}, \frac{61}{14}, \frac{170}{39}$ で、例えば $1 3^{2} - 19 \cdot 3^{2} = 169 - 171 = - 2$ 、 $17 0^{2} - 19 \cdot 3 9^{2} = 28900 - 28899 = 1$ 。）

よって、とりうる値は ${- 3, - 2, 1, 5}$ である。なお、値 $1$ を与える $(170, 39)$ が $x^{2} - 19 y^{2} = 1$ の基本解である。

別解

$19$ の連分数展開を、 $m_{0} = 0, d_{0} = 1, a_{k} = ⌊(19 + m_{k}) / d_{k} ⌋, m_{k + 1} = a_{k} d_{k} - m_{k}, d_{k + 1} = (19 - m_{k + 1}^{2}) / d_{k}$ で計算する。

計算結果は $19 = [4; 2, 1, 3, 1, 2, 8]$ で、周期は 6 である。このとき $d_{1}, \dots, d_{6} = 3, 5, 2, 5, 3, 1$ となる。

一般に $p_{n}^{2} - 19 q_{n}^{2} = (- 1)^{n + 1} d_{n + 1}$ が成り立つ。

$n = 0$ : $- d_{1} = - 3$
$n = 1$ : $+ d_{2} = 5$
$n = 2$ : $- d_{3} = - 2$
$n = 3$ : $+ d_{4} = 5$
$n = 4$ : $- d_{5} = - 3$
$n = 5$ : $+ d_{6} = 1$

周期 6 は偶数なので、 $n = 6$ 以降も符号を含めて同じ値が繰り返される。

検算:
- $n = 0$ : $4^{2} - 19 = - 3$
- $n = 1$ : $9/2$ より $81 - 76 = 5$
- $n = 2$ : $13/3$ より $169 - 171 = - 2$

よって、とりうる値は ${- 3, - 2, 1, 5}$ である。

整数論の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題