COMPASS

真の理解のためのシンプルな数学のノート

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください(532 ピクセル以上推奨).

ペル方程式

ペル方程式

定義≪ペル方程式≫

 $d$ を平方数でない正の整数とする. $x^2-dy^2 = 1$ または $x^2-dy^2 = -1$ の形の方程式を ペル方程式(Pell's equation)と呼ぶ. $(\pm 1,0)$ を $x^2-dy^2 = 1$ の自明解(trivial solution)と呼ぶ.

注意

 $d$ が平方数のとき, 整数の範囲で \[ x^2-dy^2 = (x+y\sqrt d)(x-y\sqrt d)\] と因数分解でき, 積が $\pm 1$ であるような整数は $1$ と $-1$ に限るから, $x^2-dy^2 = 1$ の解は $(x,y) = (\pm 1,0)$ に限り, $x^2-dy^2 = -1$ の解が存在するのは $d = 1$ のときに限ることが分かる. これは $d$ が平方数でないときの解の様子とまったく異なるので, $d$ が平方数の場合は除外して考える.

定理≪$x^2-dy^2 = 1$ の解の存在≫

 $d$ を平方数でない正の整数とする. このとき, $x^2-dy^2 = 1$ は無限個の整数解を持つ.

ペル方程式の解の構造

定理≪ペル方程式の解の構造≫

 $d$ を平方数でない正の整数とする.
(a)
$x^2-dy^2 = 1$ の正の整数解について, $x+y\sqrt d$ の最小値を $\varepsilon$ とおく. このとき, 各正の整数 $n$ に対して \[\varepsilon ^n = x_n+y_n\sqrt d\] で定まる $(x,y) = (x_n,y_n)$ が $x^2-dy^2 = 1$ のすべての正の整数解を与える.
(b)
$x^2-dy^2 = -1$ の整数解が存在するとして, その正の整数解について $x+y\sqrt d$ の最小値を $\varepsilon$ とおく. このとき, 各正の整数 $n$ に対して \[\varepsilon ^{2n-1} = x_n+y_n\sqrt d\] で定まる $(x,y) = (x_n,y_n)$ が $x^2-dy^2 = -1$ のすべての正の整数解を与える.

補題≪共役の乗法性≫

 $d$ を平方数でない正の整数とする. $a,$ $b$ が整数のとき, \[\widetilde{a+b\sqrt d} = a-b\sqrt d\] と定める. $a_1,$ $b_1,$ $a_2,$ $b_2$ が整数のとき, $\alpha _k = a_k+b_k\sqrt d\ (k = 1,2)$ について, $\widetilde{\alpha _1\alpha _2} = \widetilde{\alpha _1}\cdot\widetilde{\alpha _2}$ が成り立つ.

補題の証明

 $\alpha _1\alpha _2 = (a_1a_2+b_1b_2d)+(a_1b_2+b_1a_2)\sqrt d$ から, \begin{align*} &\widetilde{\alpha _1}\cdot\widetilde{\alpha _2} = (a_1-b_1\sqrt d)(a_2-b_2\sqrt d) \\ &= (a_1a_2+b_1b_2d)-(a_1b_2+b_1a_2)\sqrt d = \widetilde{\alpha _1\alpha _2} \end{align*} が成り立つ.

定理の証明

(a)
補題と $\varepsilon\tilde\varepsilon = 1$ から, \begin{align*} x_n{}^2-dy_n{}^2 &= (x_n+y_n\sqrt d)(x_n-y_n\sqrt d) \\ &= \varepsilon ^n\widetilde{\varepsilon ^n} = \varepsilon ^n\tilde\varepsilon ^n = (\varepsilon\tilde\varepsilon )^n \\ &= 1^n = 1 \end{align*} が成り立つ. さらに, $(x,y)$ を $x^2-dy^2 = 1$ の正の整数解とする. このとき, $\varepsilon > 1$ から, \[\varepsilon ^n \leqq x+y\sqrt d < \varepsilon ^{n+1}\] を満たす正の整数 $n$ が存在する. 両辺を $\varepsilon ^n$ で割ると, \[ 1 \leqq (x+y\sqrt d)\varepsilon ^{-n} < \varepsilon\] となる. \begin{align*} &(x+y\sqrt d)\varepsilon ^{-n} = (x+y\sqrt d)\tilde\varepsilon ^n \\ &= (x+y\sqrt d)\widetilde{\varepsilon ^n} = (x+y\sqrt d)(x_n-y_n\sqrt d) \\ &= x'+y'\sqrt d \end{align*} を満たす整数 $x',$ $y'$ をとる. 補題により \[ (x-y\sqrt d)\tilde\varepsilon ^{-n} = x'-y'\sqrt d\] が成り立つので, 辺々を掛けあわせると \[ x'^2-dy'^2 = (x^2-dy^2)(\varepsilon\tilde\varepsilon )^{-n} = 1\cdot 1^{-n} = 1\] が得られる. よって, $\varepsilon$ の最小性により, $x'+y'\sqrt d = 1$ が成り立つ. これから $x+y\sqrt d = \varepsilon ^n$ が得られる.
(b)
補題と $\varepsilon\tilde\varepsilon = -1$ から, \begin{align*} x_n{}^2-dy_n{}^2 &= (x_n+y_n\sqrt d)(x_n-y_n\sqrt d) \\ &= \varepsilon ^{2n-1}\widetilde{\varepsilon ^{2n-1}} = \varepsilon ^{2n-1}\tilde\varepsilon ^{2n-1} = (\varepsilon\tilde\varepsilon )^{2n-1} \\ &= (-1)^{2n-1} = -1 \end{align*} が成り立つ. さらに, $(x,y)$ を $x^2-dy^2 = -1$ の正の整数解とする. このとき, $\varepsilon > 1$ から, \[\varepsilon ^{2n-1} \leqq x+y\sqrt d < \varepsilon ^{2n+1}\] を満たす正の整数 $n$ が存在する. 両辺を $\varepsilon ^{2n-1}$ で割ると, \[ 1 \leqq (x+y\sqrt d)\varepsilon ^{1-2n} < \varepsilon ^2\] となる. \begin{align*} &(x+y\sqrt d)\varepsilon ^{1-2n} = (x+y\sqrt d)\tilde\varepsilon ^{2n-1} \\ &= (x+y\sqrt d)\widetilde{\varepsilon ^{2n-1}} = (x+y\sqrt d)(x_n-y_n\sqrt d) \\ &= x'+y'\sqrt d \end{align*} を満たす整数 $x',$ $y'$ をとる. 補題により \[ (x-y\sqrt d)\tilde\varepsilon ^{1-2n} = x'-y'\sqrt d\] が成り立つので, 辺々を掛けあわせると \begin{align*} x'^2-dy'^2 &= (x^2-dy^2)(\varepsilon\tilde\varepsilon )^{1-2n} \\ &= (-1)\cdot (-1)^{1-2n} = 1 \end{align*} が得られる. $x^2-dy^2 = 1$ の正の整解について $x+y\sqrt d$ の最小値は $\varepsilon ^2$ であるから, $x'+y'\sqrt d = 1$ が成り立つ. これから $x+y\sqrt d = \varepsilon ^{2n-1}$ が得られる.

定理≪ペル方程式の平方根の近似計算への応用≫

 $d$ を平方数でない正の整数とする. $x^2-dy^2 = 1$ の正の整数解について, $x+y\sqrt d$ の値が小さい順に $(x_n,y_n)$ とおくと, $x_n/y_n$ は $\sqrt d$ に収束する.

問題

数学 B: 数列

問題≪ペル方程式に関する連立漸化式≫

 数列 $\{ x_n\},$ $\{ y_n\}$ を \[ x_1 = 3,\ y_1 = 2,\ x_{n+1} = 3x_n+4y_n,\ y_{n+1} = 2x_n+3y_n\] で定める.
(a)
数列 $\{ x_n+ky_n\}$ が公比 $r$ の等比数列となるような定数 $k,$ $r$ の組を $2$ 組求めよ. さらに, 数列 $\{ x_n\},$ $\{ y_n\}$ の一般項を求めよ.
(b)
$x_n,$ $x_{n+1},$ $x_{n+2}$ の関係式を求めよ. また, 数列 $\{ x_{n+1}-\alpha x_n\}$ が公比 $\beta$ の等比数列となるような定数 $\alpha,$ $\beta$ の組を $2$ 組求めよ. さらに, 数列 $\{ x_n\},$ $\{ y_n\}$ の一般項を求めよ.

解答例

(a)
数列 $\{ x_n+ky_n\}$ が公比 $r$ の等比数列となるとき, \begin{align*} &x_{n+1}+ky_{n+1} = r(x_n+ky_n) \\ &(3x_n+4y_n)+k(2x_n+3y_n) = r(x_n+ky_n) \\ &(2k-r+3)x_n+(3k-rk+4)y_n = 0 \end{align*} となる. よって, $2k-r+3 = 3k-rk+4 = 0$ であれば, この等式が成り立つ. $r = 2k+3$ を $3k-rk+4 = 0$ に代入して整理すると $2k^2 = 4$ つまり $k = \pm\sqrt 2$ となるから, \[ (k,r) = (\pm\sqrt 2,3\pm 2\sqrt 2)\] は条件を満たす(複号同順). $\{ x_n\pm\sqrt 2y_n\}$ は初項 $3\pm 2\sqrt 2,$ 公比 $3\pm 2\sqrt 2$ の等比数列であるから, \begin{align*} x_n+\sqrt 2y_n &= (3+2\sqrt 2)^n \quad \cdots [1], \\ x_n-\sqrt 2y_n &= (3-2\sqrt 2)^n \quad \cdots [2] \end{align*} が成り立つ. よって, $([1]+[2])\div 2,$ $([1]-[2])\div 2\sqrt 2$ から, \begin{align*} x_n &= \frac{(3+2\sqrt 2)^n+(3-2\sqrt 2)^n}{2}, \\ y_n &= \frac{(3+2\sqrt 2)^n-(3-2\sqrt 2)^n}{2\sqrt 2} \end{align*} が得られる.
(b)
第 $3$ 式から, $x_{n+2} = 3x_{n+1}+4y_{n+1}$ である. ここに第 $4$ 式を代入して整理すると, \[ x_{n+2} = 3x_{n+1}+8x_n+12y_n\] となる. これと第 $3$ 式から $y_n$ を消去すると, \begin{align*} &x_{n+2}-3x_{n+1} = 3x_{n+1}-x_n \\ &x_{n+2}-6x_{n+1}+x_n = 0 \end{align*} となる. 数列 $\{ x_{n+1}-\alpha x_n\}$ が公比 $\beta$ の等比数列となるとき, \begin{align*} &x_{n+2}-\alpha x_{n+1} = \beta (x_{n+1}-\alpha x_n) \\ &x_{n+2}-(\alpha +\beta )x_{n+1}+\alpha\beta x_n = 0 \end{align*} となる. よって, $\alpha +\beta = 6,$ $\alpha\beta = 1$ のとき, つまり $(\alpha,\beta ) = (3\mp 2\sqrt 2,3\pm 2\sqrt 2)$ のとき, 上記の等式が成り立つ. $\{ x_{n+1}-(3\mp 2\sqrt 2)x_n\}$ は初項 \begin{align*} x_2-(3\mp 2\sqrt 2)x_1 &= (3\cdot 3+4\cdot 2)-(3\mp 2\sqrt 2)\cdot 3 \\ &= \pm 2\sqrt 2(3\pm 2\sqrt 2), \end{align*} 公比 $3\pm 2\sqrt 2$ の等比数列であるから, \begin{align*} x_{n+1}-(3-2\sqrt 2)x_n &= 2\sqrt 2(3+2\sqrt 2)^n \quad \cdots [1], \\ x_{n+1}-(3+2\sqrt 2)x_n &= -2\sqrt 2(3-2\sqrt 2)^n \quad \cdots [2] \end{align*} が成り立つ. よって, $([1]-[2])\div 4\sqrt 2$ から, \[ x_n = \frac{(3+2\sqrt 2)^n+(3-2\sqrt 2)^n}{2}\] が得られる. このとき, \begin{align*} y_n &= \frac{1}{4}x_{n+1}-\frac{3}{4}x_n \\ &= \frac{(3+2\sqrt 2)^{n+1}+(3-2\sqrt 2)^{n+1}}{8} \\ &\qquad -\frac{3(3+2\sqrt 2)^n+3(3-2\sqrt 2)^n}{8} \\ &= \frac{(3+2\sqrt 2)^n\cdot 2\sqrt 2+(3-2\sqrt 2)^n\cdot (-2\sqrt 2)}{8} \\ &= \frac{(3+2\sqrt 2)^n-(3-2\sqrt 2)^n}{2\sqrt 2} \end{align*} である.

背景

 平方数でない正の整数 $d$ について, $x^2-dy^2 = 1$ の形の方程式を「ペル方程式」(Pell's equation)と呼ぶ. $x^2-dy^2 = 1$ は必ず正の整数解を持つことが知られており, そのような解について $x+y\sqrt d$ の最小値を $\varepsilon$ とおくと, $\varepsilon ^n = x_n+y_n\sqrt d$ で定まる $(x,y) = (x_n,y_n)$ が $x^2-dy^2 = 1$ のすべての正の整数解を与えることが知られている. $d = 2$ のとき $\varepsilon = 3+2\sqrt 2$ であり, 問題の漸化式は $x_{n+1}+y_{n+1}\sqrt 2 = (x_n+y_n\sqrt 2)(3+2\sqrt 2)$ から定まるものである.
 数学 III の内容についての補足: (a), (b) の結果から \begin{align*} \frac{x_n}{y_n} &= \sqrt 2\cdot\frac{(3+2\sqrt 2)^n+(3-2\sqrt 2)^n}{(3+2\sqrt 2)^n-(3-2\sqrt 2)^n} \\ &= \sqrt 2\cdot\frac{1+\left(\dfrac{3-2\sqrt 2}{3+2\sqrt 2}\right) ^n}{1-\left(\dfrac{3-2\sqrt 2}{3+2\sqrt 2}\right) ^n} \\ &\to \sqrt 2 \quad (n \to \infty) \end{align*} となるが, 一般の $d$ についても $\lim\limits_{n \to \infty}\dfrac{x_n}{y_n} = \sqrt d$ の成り立つことが知られている.