√d の連分数展開とペル方程式の基本解

$d$ の連分数展開 $[a_{0}; a_{1}, \dots, a_{ℓ - 1}, 2 a_{0}]$ を $m_{n + 1} = a_{n} Q_{n} - m_{n}$ , $Q_{n + 1} = \frac{d - m _{n + 1}^{2}}{Q _{n}}$ の漸化式で求め、 $p_{n}^{2} - d q_{n}^{2} = (- 1)^{n + 1} Q_{n + 1}$ を使って、 $p_{n}^{2} - d q_{n}^{2}$ のとる値や、周期の長さの偶奇に応じた $x^{2} - d y^{2} = 1$ の基本解（例: $d = 43$ ）を求められる

前提

連分数展開と近似分数（大学数学整数論）
ペル方程式の解の生成（大学数学整数論）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

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

説明

平方数でない正の整数 $d$ に対し、 $d$ の連分数展開を、根号の近似値を使わず整数の計算だけで求める方法を学びます。展開は必ず $d = [a_{0}; a_{1}, \dots, a_{ℓ - 1}, 2 a_{0}]$ の形になります（上線部が周期、 $ℓ$ が周期の長さ）。途中で出てくる整数 $Q_{n}$ を使うと、近似分数 $\frac{p _{n}}{q _{n}}$ について $p_{n}^{2} - d q_{n}^{2}$ の値がすぐわかります。その結果、試しに探すのが難しい大きな $d$ でも、ペル方程式 $x^{2} - d y^{2} = 1$ の基本解（ $x, y$ が正の整数である解のうち $x$ が最小のもの）を機械的に求められます。

なぜそうしてよいのか

$d$ を展開していく途中の値（完全商）を $x_{n} = \frac{m _{n} + d}{Q _{n}}$ （ $m_{n}, Q_{n}$ は整数、 $Q_{n} > 0$ ）の形に保ちます。出発点は $x_{0} = d$ 、つまり $m_{0} = 0, Q_{0} = 1$ です。整数部分 $a_{n}$ を引くと $x_{n} - a_{n} = \frac{d - ( a _{n} Q _{n} - m _{n} )}{Q _{n}}$ となるので、 $m_{n + 1} = a_{n} Q_{n} - m_{n}$ とおきます。その逆数の分母を有理化すると $\frac{Q _{n}}{d - m _{n + 1}} = \frac{Q _{n} ( m _{n + 1} + d )}{d - m _{n + 1}^{2}}$ です。そこで $Q_{n + 1} = \frac{d - m _{n + 1}^{2}}{Q _{n}}$ とおけば、 $x_{n + 1} = \frac{m _{n + 1} + d}{Q _{n + 1}}$ と同じ形に戻ります。この割り算は常に割り切れ、 $Q_{n + 1}$ は正の整数になることが知られています。また $a_{0} = ⌊ d ⌋$ とすると、 $a_{n} = ⌊ \frac{a _{0} + m _{n}}{Q _{n}} ⌋$ で整数部分が正確に求まります。

次に $p_{n}^{2} - d q_{n}^{2}$ の値を求めます。 $d = [a_{0}; a_{1}, \dots, a_{n}, x_{n + 1}]$ なので、近似分数の漸化式から $d = \frac{x _{n + 1} p _{n} + p _{n - 1}}{x _{n + 1} q _{n} + q _{n - 1}}$ が成り立ちます。 $x_{n + 1} = \frac{m + d}{Q}$ （ $m = m_{n + 1}, Q = Q_{n + 1}$ ）を代入して分母を払うと、 $d {(m + d) q_{n} + Q q_{n - 1}} = (m + d) p_{n} + Q p_{n - 1}$ です。 $d$ は無理数なので、両辺の有理部分どうし・ $d$ の係数どうしが等しくなり、 $d q_{n} = m p_{n} + Q p_{n - 1}$ と $p_{n} = m q_{n} + Q q_{n - 1}$ が得られます。よって
$p_{n}^{2} - d q_{n}^{2} = p_{n} (m q_{n} + Q q_{n - 1}) - q_{n} (m p_{n} + Q p_{n - 1}) = Q (p_{n} q_{n - 1} - p_{n - 1} q_{n}) = (- 1)^{n + 1} Q_{n + 1}$
となります。

さらに次の事実が知られています。(i) $Q_{n} = 1$ となるのは $n$ が周期の長さ $ℓ$ の倍数のときだけで、 $n = ℓ$ で初めて $Q_{ℓ} = 1$ 、 $a_{ℓ} = 2 a_{0}$ となって周期が閉じる。(ii) $x^{2} - d y^{2} = \pm 1$ の正の整数解 $(x, y)$ では $\frac{x}{y}$ は必ず $d$ の近似分数のどれかになる。したがって $p_{n}^{2} - d q_{n}^{2} = \pm 1$ となるのは $n + 1$ が $ℓ$ の倍数のときで、そのときの符号は $(- 1)^{n + 1}$ です。 $ℓ$ が偶数なら $n = ℓ - 1$ で初めて $+ 1$ になります。 $ℓ$ が奇数なら $n = ℓ - 1$ では $- 1$ で、 $n = 2 ℓ - 1$ で初めて $+ 1$ になります。 $p_{n}, q_{n}$ は $n$ とともに増えるので、最初に $+ 1$ になったものが基本解です。

手順

初期値を置く: $a_{0} = ⌊ d ⌋$ , $m_{0} = 0$ , $Q_{0} = 1$ 。
漸化式を回す: $m_{n + 1} = a_{n} Q_{n} - m_{n}$ , $Q_{n + 1} = \frac{d - m _{n + 1}^{2}}{Q _{n}}$ , $a_{n + 1} = ⌊ \frac{a _{0} + m _{n + 1}}{Q _{n + 1}} ⌋$ を順に計算する。
$Q_{ℓ} = 1$ （同時に $a_{ℓ} = 2 a_{0}$ ）となった最初の $ℓ$ が周期の長さ。 $d = [a_{0}; a_{1}, \dots, a_{ℓ - 1}, 2 a_{0}]$ と書ける。
近似分数を計算する: $p_{n} = a_{n} p_{n - 1} + p_{n - 2}$ , $q_{n} = a_{n} q_{n - 1} + q_{n - 2}$ （ $p_{- 2} = 0, p_{- 1} = 1, q_{- 2} = 1, q_{- 1} = 0$ ）。 $p_{n}^{2} - d q_{n}^{2} = (- 1)^{n + 1} Q_{n + 1}$ で検算できる。
基本解を決める: $ℓ$ が偶数なら $(p_{ℓ - 1}, q_{ℓ - 1})$ 。 $ℓ$ が奇数なら $p_{ℓ - 1}^{2} - d q_{ℓ - 1}^{2} = - 1$ なので、 $(p_{2 ℓ - 1}, q_{2 ℓ - 1})$ を使う。これは $x + y d = (p_{ℓ - 1} + q_{ℓ - 1} d)^{2}$ でも求まる。

例題

$13$ の連分数展開を求め、ペル方程式 $x^{2} - 13 y^{2} = 1$ の基本解 $(x, y)$ を求めよ。

例題の解答

【手順1】 $3^{2} < 13 < 4^{2}$ より $a_{0} = 3$ 。 $m_{0} = 0, Q_{0} = 1$ とする。
【手順2】漸化式を回す。
$m_{1} = 3 \cdot 1 - 0 = 3, Q_{1} = \frac{13 - 9}{1} = 4, a_{1} = ⌊ \frac{3 + 3}{4} ⌋ = 1$
$m_{2} = 1 \cdot 4 - 3 = 1, Q_{2} = \frac{13 - 1}{4} = 3, a_{2} = ⌊ \frac{4}{3} ⌋ = 1$
$m_{3} = 1 \cdot 3 - 1 = 2, Q_{3} = \frac{13 - 4}{3} = 3, a_{3} = ⌊ \frac{5}{3} ⌋ = 1$
$m_{4} = 1 \cdot 3 - 2 = 1, Q_{4} = \frac{13 - 1}{3} = 4, a_{4} = ⌊ \frac{4}{4} ⌋ = 1$
$m_{5} = 1 \cdot 4 - 1 = 3, Q_{5} = \frac{13 - 9}{4} = 1, a_{5} = ⌊ \frac{6}{1} ⌋ = 6$
【手順3】 $Q_{5} = 1$ 、 $a_{5} = 6 = 2 a_{0}$ なので周期の長さは $ℓ = 5$ 。 $13 = [3; 1, 1, 1, 1, 6]$ 。
【手順4】近似分数は $\frac{p _{0}}{q _{0}} = \frac{3}{1}, \frac{4}{1}, \frac{7}{2}, \frac{11}{3}, \frac{18}{5}$ （ $n = 0, \dots, 4$ ）。
検算: $3^{2} - 13 \cdot 1^{2} = - 4 = - Q_{1}$ 、 $4^{2} - 13 \cdot 1^{2} = 3 = Q_{2}$ 、 $7^{2} - 13 \cdot 2^{2} = - 3 = - Q_{3}$ 、 $1 1^{2} - 13 \cdot 3^{2} = 4 = Q_{4}$ 、 $1 8^{2} - 13 \cdot 5^{2} = - 1 = - Q_{5}$ 。すべて $(- 1)^{n + 1} Q_{n + 1}$ に一致する。
【手順5】 $ℓ = 5$ は奇数なので、 $(18, 5)$ は $x^{2} - 13 y^{2} = - 1$ の解であり、求める基本解ではない。2周目まで進めて $(p_{9}, q_{9})$ を求める。
$(18 + 513)^{2} = 324 + 325 + 18013 = 649 + 18013$ 。
漸化式を続けても同じ結果になる。 $a_{5}, \dots, a_{9} = 6, 1, 1, 1, 1$ より $p_{5}, \dots, p_{9} = 119, 137, 256, 393, 649$ 、 $q_{5}, \dots, q_{9} = 33, 38, 71, 109, 180$ 。
確認: $64 9^{2} - 13 \cdot 18 0^{2} = 421201 - 421200 = 1$ 。
よって基本解は $(649, 180)$ 。

答え: $(649, 180)$

よくある誤り

周期の長さが奇数なのに $(p_{ℓ - 1}, q_{ℓ - 1})$ を基本解としてしまう誤り。 $d = 13$ では $1 8^{2} - 13 \cdot 5^{2} = - 1$ である。正しくは符号 $(- 1)^{ℓ}$ を確かめ、 $ℓ$ が奇数なら $(p_{2 ℓ - 1}, q_{2 ℓ - 1}) = (649, 180)$ を使う。
添字を1つずらしてしまう誤り。 $p_{n}^{2} - d q_{n}^{2} = (- 1)^{n} Q_{n}$ としたり、 $2 a_{0}$ まで含めた $p_{ℓ} / q_{ℓ}$ を使ったりする。正しくは $p_{n}^{2} - d q_{n}^{2} = (- 1)^{n + 1} Q_{n + 1}$ で、基本解の候補は最後の項 $2 a_{0}$ の直前までで作る $(p_{ℓ - 1}, q_{ℓ - 1})$ 。 $d = 43$ なら $ℓ = 10$ で $(p_{9}, q_{9}) = (3482, 531)$ 。
$Q_{n + 1} = d - m_{n + 1}^{2}$ として $Q_{n}$ で割り忘れる誤り。正しくは $Q_{n + 1} = \frac{d - m _{n + 1}^{2}}{Q _{n}}$ 。 $d = 13$ の $n = 1$ では $\frac{13 - 1}{4} = 3$ であり、 $12$ ではない。
$a_{n + 1}$ を $d$ の粗い小数近似から求めて、整数部分を1つずらしてしまう誤り。正しくは整数だけで $a_{n + 1} = ⌊ \frac{a _{0} + m _{n + 1}}{Q _{n + 1}} ⌋$ と計算する。 $d = 13$ の $n + 1 = 4$ では $⌊ \frac{3 + 1}{4} ⌋ = 1$ となる。

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

入口の問題

この技能を使う問題

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

単数群と実 2 次体の基本単数（大学院数学代数的整数論）