Pell数

同義語:Pell数列Pell numberPell sequence

概要

Pell数(Pell number)とは、$P_0=0$、$P_1=1$ から漸化式 $P_{n+1}=2P_n+P_{n-1}$ で作られる整数列 $0,1,2,5,12,29,70,169,\dots$ の項である。一般項は $P_n=\frac{(1+\sqrt2)^n-(1-\sqrt2)^n}{2\sqrt2}$ で、$(1+\sqrt2)^n=H_n+P_n\sqrt2$ と書くと $H_n^2-2P_n^2=(-1)^n$ が成り立ち、$x^2-2y^2=\pm1$ の正の整数解はこれで尽くされる。$H_n/P_n$ は $\sqrt2$ の連分数の収束子である。$\gcd(P_m,P_n)=P_{\gcd(m,n)}$ が成り立ち、直角をはさむ 2 辺の差が 1 の直角三角形の斜辺は奇数番目の Pell 数である。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 三項間漸化式, Euclidの互除法

Pell数(Pell number)は、$P_0=0$、$P_1=1$ から漸化式 $P_{n+1}=2P_n+P_{n-1}$ で作られる整数列
$$ 0,\ 1,\ 2,\ 5,\ 12,\ 29,\ 70,\ 169,\ 408,\ 985,\ 2378,\ \dots $$
の項である。この数列を Pell数列 という。Fibonacci数列 の漸化式 $F_{n+1}=F_n+F_{n-1}$ の係数 $1$ を $2$ に変えたもので、Fibonacci 数が黄金比 $\frac{1+\sqrt5}2$ と結びつくのと同じように、Pell 数は $1+\sqrt2$(白銀比 と呼ばれることがある)と結びつく。
Pell 数のいちばん大事な性質は $\sqrt2$ との関係である。$(1+\sqrt2)^n=H_n+P_n\sqrt2$ と展開したときの $\sqrt2$ の係数が $P_n$ であり、$H_n^2-2P_n^2=\pm1$ が成り立つ。$x^2-2y^2=\pm1$ の正の整数解はこれで尽くされ、$H_n/P_n$ は $\sqrt2$ の最良の有理近似(連分数の収束子)になる。これは Pellの方程式 の $d=2$ の場合であり、名前もこの方程式から来ている。
この記事では、Pell 数の一般項・行列表示・加法公式を示し、$x^2-2y^2=\pm1$ の解がちょうど $(H_n,P_n)$ であることを直接証明する。次に、最大公約数の公式 $\gcd(P_m,P_n)=P_{\gcd(m,n)}$ と、そこから従う素数の条件を証明し、2 辺の差が $1$ の直角三角形への応用を述べる。

定義と一般項

Pell数と付随する数列

Pell数 $P_n$ を
$$ P_0=0,\qquad P_1=1,\qquad P_{n+1}=2P_n+P_{n-1}\quad(n\ge1) $$
で定める。同じ漸化式を満たし初期値が $H_0=H_1=1$ である数列を $H_n$ と書く。

小さい $n$ の値は次のとおりである。

$n$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$
$P_n$$0$$1$$2$$5$$12$$29$$70$$169$$408$$985$$2378$
$H_n$$1$$1$$3$$7$$17$$41$$99$$239$$577$$1393$$3363$

$Q_n:=2H_n$($2,2,6,14,34,82,\dots$)を Pell–Lucas 数 と呼ぶことが多い。$P_n$ と $Q_n$ は、パラメータ $(2,-1)$ の Lucas 数列 $U_n$、$V_n$ にあたる(Lucas数列の関係式)。漸化式を $P_{n-1}=P_{n+1}-2P_n$ と読んで負の番号に延ばすと $P_{-1}=1$、$P_{-2}=-2$ で、一般に $P_{-n}=(-1)^{n+1}P_n$ となる(Bic75 p. 345)。

一般項

$\alpha:=1+\sqrt2$、$\beta:=1-\sqrt2$ とおくと、すべての $n\ge0$ について
$$ P_n=\frac{\alpha^n-\beta^n}{2\sqrt2},\qquad H_n=\frac{\alpha^n+\beta^n}2 $$
である。とくに $P_{n+1}/P_n\to\alpha$($n\to\infty$)で、$P_n$ は $\alpha^n/(2\sqrt2)$ にもっとも近い整数である。

$\alpha$、$\beta$ は $t^2=2t+1$ の 2 根なので、$\alpha^n$ と $\beta^n$ はどちらも漸化式 $u_{n+1}=2u_n+u_{n-1}$ を満たし、その 1 次結合も満たす。右辺の 2 式は $n=0,1$ でそれぞれ $0,1$ と $1,1$ になるので、漸化式から全部の $n$ で左辺に一致する。$\lvert\beta\rvert=\sqrt2-1< 1$ なので $\beta^n\to0$ であり、$P_{n+1}/P_n\to\alpha$ が従う。また $\lvert\beta^n/(2\sqrt2)\rvert< \frac12$ から最後の主張が従う。$\square$

一般項は Bic75 (3)(p. 345)にある。$\alpha=1+\sqrt2$ は、短い辺を $1$ とする長方形から 1 辺 $1$ の正方形を 2 つ取り除くと元と相似な長方形が残るときの長辺の長さで、黄金比が正方形を 1 つ取り除く場合にあたるのと対になっている(Bic75 pp. 345–346, Figure 1)。

行列表示と加法公式

行列表示

$M:=\begin{pmatrix}2&1\\1&0\end{pmatrix}$ について、すべての $n\ge0$ で
$$ M^n=\begin{pmatrix}P_{n+1}&P_n\\P_n&P_{n-1}\end{pmatrix} $$
である。したがって次が成り立つ。

  1. $P_{n+1}P_{n-1}-P_n^2=(-1)^n$。
  2. すべての $m,n\ge0$ について $P_{m+n+1}=P_{m+1}P_{n+1}+P_mP_n$、$P_{m+n}=P_{m+1}P_n+P_mP_{n-1}$。

$n=0$ では右辺は $\begin{pmatrix}P_1&P_0\\P_0&P_{-1}\end{pmatrix}=I$ である。右辺を $M^n$ と仮定して $M$ を掛けると、
$$ \begin{pmatrix}P_{n+1}&P_n\\P_n&P_{n-1}\end{pmatrix}\begin{pmatrix}2&1\\1&0\end{pmatrix}=\begin{pmatrix}2P_{n+1}+P_n&P_{n+1}\\2P_n+P_{n-1}&P_n\end{pmatrix}=\begin{pmatrix}P_{n+2}&P_{n+1}\\P_{n+1}&P_n\end{pmatrix} $$
となり、帰納法で示される。1 は両辺の行列式をとって $\det M=-1$ を使えばよい。2 は $M^{m+n}=M^mM^n$ の成分を比べたもので、左上の成分から前半、右上の成分から後半が出る。$\square$

1 は Fibonacci 数の Cassiniの恒等式 にあたる。2 で $m=n$ とすると
$$ P_{2n+1}=P_{n+1}^2+P_n^2,\qquad P_{2n}=P_n(P_{n+1}+P_{n-1})=2P_nH_n $$
を得る(後半は $P_{n+1}+P_{n-1}=2H_n$ による。これは prop-pell-number-binet から確かめられる)。これらと 1 は Bic75 (4)・(8)・(12)・(15)(p. 346)、行列表示は p. 347 にある。
隣り合う項の比 $P_{n+1}/P_n$ は $\frac21,\frac52,\frac{12}5,\frac{29}{12},\dots$ で、$1+\sqrt2=[2;2,2,2,\dots]$ の連分数の収束子である。実際 $[2;2,\dots,2]$($2$ が $n$ 個)の値は漸化式 $x\mapsto2+1/x$ から $P_{n+1}/P_n$ になる。
Pell 数は次のような数え上げにも現れる。

  • 母関数:$\displaystyle\sum_{n\ge0}P_nx^n=\frac x{1-2x-x^2}$(Bic75 (18)、p. 346)。母関数 の分母が漸化式の係数を表す。
  • 敷き詰め:$1\times n$ の帯を、2 色のどちらかで塗った $1\times1$ の正方形と、色を区別しない $1\times2$ の長方形で敷き詰める方法の数を $T_n$ とすると、右端の 1 枚で場合分けして $T_n=2T_{n-1}+T_{n-2}$、$T_0=1$、$T_1=2$ なので、$T_n=P_{n+1}$ である。
  • 2 乗和:$P_{k+1}-P_{k-1}=2P_k$ から $P_k^2=\frac12(P_kP_{k+1}-P_{k-1}P_k)$ で、$k=1,\dots,n$ について足すと和が畳み込まれ、$\sum_{k=1}^nP_k^2=\frac12P_nP_{n+1}$ となる(Bic75 (17))。

$\sqrt2$ と方程式 $x^2-2y^2=\pm1$

$1+\sqrt2$ の冪

すべての $n\ge0$ について
$$ (1+\sqrt2)^n=H_n+P_n\sqrt2,\qquad H_n^2-2P_n^2=(-1)^n $$
である。また $H_{n+1}=H_n+2P_n$、$P_{n+1}=H_n+P_n$ が成り立つ。

$n=0$ では $1=H_0+P_0\sqrt2$ である。$(1+\sqrt2)^n=a_n+b_n\sqrt2$($a_n,b_n$ は整数)と書くと、$(a_n+b_n\sqrt2)(1+\sqrt2)=(a_n+2b_n)+(a_n+b_n)\sqrt2$ から $a_{n+1}=a_n+2b_n$、$b_{n+1}=a_n+b_n$ である。これから $b_{n+1}=a_n+b_n=(a_{n-1}+2b_{n-1})+b_n=2b_n+b_{n-1}$($a_{n-1}=b_n-b_{n-1}$ を使った)で、$a_n$ についても同じ漸化式が出る。$(a_0,b_0)=(1,0)$、$(a_1,b_1)=(1,1)$ なので $a_n=H_n$、$b_n=P_n$ である。$\mathbb Z[\sqrt2]$ のノルム $N(x+y\sqrt2):=x^2-2y^2$ は乗法的で $N(1+\sqrt2)=-1$ なので、$H_n^2-2P_n^2=(-1)^n$ を得る。$\square$

$x^2-2y^2=\pm1$ の正の解

正の整数の組 $(x,y)$ が $x^2-2y^2=\pm1$ を満たすための必要十分条件は、ある $n\ge1$ について $(x,y)=(H_n,P_n)$ となることである。このとき右辺は $(-1)^n$ である。

十分性は prop-pell-number-sqrt2 である。必要性を $y$ についての帰納法で示す。$y=1$ なら $x^2=2\pm1$ から $x=1$ で、$(x,y)=(H_1,P_1)$ である。$y\ge2$ とする。$x^2\ge2y^2-1>y^2$ から $x>y$、$x^2\le2y^2+1< 4y^2$ から $x< 2y$ である。そこで
$$ (x+y\sqrt2)(\sqrt2-1)=x'+y'\sqrt2,\qquad x':=2y-x,\quad y':=x-y $$
とおくと、$x',y'\ge1$ かつ $y'< y$ で、$N(\sqrt2-1)=-1$ から $x'^2-2y'^2=\mp1$ である。帰納法の仮定から $(x',y')=(H_m,P_m)$ となる $m\ge1$ があり、$(\sqrt2-1)^{-1}=1+\sqrt2$ なので
$$ x+y\sqrt2=(H_m+P_m\sqrt2)(1+\sqrt2)=(1+\sqrt2)^{m+1}=H_{m+1}+P_{m+1}\sqrt2 $$
である。$\sqrt2$ は無理数なので $(x,y)=(H_{m+1},P_{m+1})$ を得る。$\square$

$n$ が偶数のものが Pellの方程式 $x^2-2y^2=1$ の解 $(3,2),(17,12),(99,70),\dots$、奇数のものが $x^2-2y^2=-1$ の解 $(1,1),(7,5),(41,29),\dots$ である。この定理は $\mathbb Z[\sqrt2]$ の単元が $\pm(1+\sqrt2)^n$($n\in\mathbb Z$)で尽くされることと同じ内容である。一般の $d$ についての構造は Pell の方程式の記事で証明されているが、$d=2$ では上のように「$\sqrt2-1$ を掛けて小さくする」だけで済む。
$H_n/P_n$ は $\frac11,\frac32,\frac75,\frac{17}{12},\frac{41}{29},\dots$ で、$\sqrt2=[1;2,2,2,\dots]$ の連分数の収束子にほかならない。誤差は
$$ \Bigl\lvert\frac{H_n}{P_n}-\sqrt2\Bigr\rvert=\frac{1}{P_n^2\,(H_n/P_n+\sqrt2)}< \frac1{2P_n^2} $$
である($H_n^2-2P_n^2=\pm1$ を $(H_n/P_n-\sqrt2)(H_n/P_n+\sqrt2)P_n^2$ と書き、$H_n/P_n+\sqrt2\ge1+\sqrt2>2$ を使う)。

平方数である三角数

三角数 $\frac{k(k+1)}2$ が平方数 $m^2$ になるのは、$(2k+1)^2-2(2m)^2=1$ のとき、すなわち thm-pell-number-solutions から $2k+1=H_{2j}$、$2m=P_{2j}$ となるときである。よって平方数である三角数は $(P_{2j}/2)^2=1,\,36,\,1225,\,41616,\dots$ で尽くされる(Pellの方程式 の記事では $x^2-8y^2=1$ の形で扱っている)。

最大公約数と素数

最大公約数の公式

すべての $m,n\ge0$ について $\gcd(P_m,P_n)=P_{\gcd(m,n)}$ である。とくに $m\ge1$ について、$P_m\mid P_n$ であることと $m\mid n$ であることは同値である。

まず $\gcd(P_n,P_{n+1})=1$ である。prop-pell-number-matrix の 1 で $P_{n+1}P_{n-1}-P_n^2=\pm1$ なので、$P_n$ と $P_{n+1}$ の公約数は $1$ を割る。
次に $m,n\ge1$ について、prop-pell-number-matrix の 2 から $P_{m+n}=P_{m+1}P_n+P_mP_{n-1}$ なので
$$ \gcd(P_{m+n},P_n)=\gcd(P_mP_{n-1},P_n)=\gcd(P_m,P_n) $$
である(2 つめの等号は $\gcd(P_{n-1},P_n)=1$ による)。すなわち $\gcd(P_a,P_b)$ は $(a,b)$ を $(a-b,b)$ に置き換えても変わらない。Euclidの互除法 で $(m,n)$ を $(\gcd(m,n),0)$ まで変形すれば $\gcd(P_m,P_n)=\gcd(P_{\gcd(m,n)},P_0)=P_{\gcd(m,n)}$ を得る($m$ か $n$ が $0$ の場合は $P_0=0$ からすぐわかる)。
後半について、$m\mid n$ なら $\gcd(m,n)=m$ なので $P_m\mid P_n$ である。逆に $P_m\mid P_n$ なら $P_m=\gcd(P_m,P_n)=P_{\gcd(m,n)}$ で、$P_1< P_2< P_3< \cdots$ なので $m=\gcd(m,n)$、すなわち $m\mid n$ である。$\square$

Pell数が素数になる番号

$P_n$ が素数ならば $n$ は素数である。

$P_0=0$、$P_1=1$ は素数でないので $n\ge2$ である。$n=ab$、$1< a< n$ と分解できれば、thm-pell-number-gcd から $P_a\mid P_n$ で、$2\le P_a< P_n$ なので $P_n$ は素数でない。$\square$

逆は成り立たない。$P_2=2$、$P_3=5$、$P_5=29$ は素数だが、$7$ は素数なのに $P_7=169=13^2$ である。また $P_n$ の偶奇は $n$ の偶奇と一致する($P_{n+1}\equiv P_{n-1}\pmod2$ による)。

2 辺の差が 1 の直角三角形

2 辺の差が 1 の直角三角形

$k\ge1$ について
$$ \bigl(P_{k+1}^2-P_k^2,\ 2P_{k+1}P_k,\ P_{2k+1}\bigr) $$
は直角をはさむ 2 辺の差が $1$ の ピタゴラス数 である。逆に、直角をはさむ 2 辺が連続する整数 $a,a+1$($a\ge1$)である整数辺の直角三角形は、すべてこの形で、斜辺は $P_{2k+1}$($k\ge1$)である。

$m:=P_{k+1}$、$n:=P_k$ とおくと $(m^2-n^2)^2+(2mn)^2=(m^2+n^2)^2$ で、prop-pell-number-matrix の後の式から $m^2+n^2=P_{2k+1}$ である。prop-pell-number-sqrt2 から $m-n=P_{k+1}-P_k=H_k$ なので
$$ (m^2-n^2)-2mn=(m-n)^2-2n^2=H_k^2-2P_k^2=(-1)^k $$
であり、2 辺の差は $1$ である。逆に $a^2+(a+1)^2=c^2$ なら、両辺を $2$ 倍して整理すると $(2a+1)^2-2c^2=-1$ である。thm-pell-number-solutions から $(2a+1,c)=(H_n,P_n)$ となる奇数 $n$ があり、$a\ge1$ なので $n\ne1$、すなわち $n=2k+1$($k\ge1$)である。$c$ が決まれば $a^2+(a+1)^2=c^2$ から $a$ はただ 1 つに決まるので、三角形は前半の $k$ のものと一致する。$\square$

$k=1,2,3,4$ で $(3,4,5)$、$(21,20,29)$、$(119,120,169)$、$(697,696,985)$ となる。この三角形の列は 17 世紀に Girard が短い方の辺 $3,20,119,696,\dots$ として挙げ、Fermat は 1 つの三角形 $(x,x+1,z)$ から次の三角形を作る漸化式を与えた。さらに、$1,2,5,12,29,70,\dots$ の連続する 2 項から Euclid の公式で作れるという上の形の規則も 18 世紀には知られていた(Dic05 Vol. II, Chapter IV, pp. 181–182)。
Markov 数との関係。 $n\ge1$ について $(2,P_{2n-1},P_{2n+1})$ は Markov 方程式 $x^2+y^2+z^2=3xyz$ の解であり、$2$ を含む解はこれと $(1,1,2)$ で尽くされる。とくに奇数番目の Pell 数 $1,5,29,169,985,\dots$ はすべて Markov数 である。たとえば $4+1+25=30=3\cdot2\cdot1\cdot5$ である。証明は Markov 数の記事にある。

反例:仮定を外すと成り立たないこと

外す仮定反例成り立たなくなること
右辺が $\pm1$(thm-pell-number-solutions)$x^2-2y^2=2$ の解 $(x,y)=(2,1)$解が $(H_n,P_n)$ の形であること
初期値 $P_0=0$、$P_1=1$(thm-pell-number-gcd)同じ漸化式の $H_n$:$1,1,3,7,17,41,99,\dots$$\gcd(H_3,H_6)=\gcd(7,99)=1\ne H_3$
初期値 $P_0=0$、$P_1=1$(cor-pell-number-prime)同じ漸化式の $H_n$$H_4=17$ は素数だが $4$ は素数でない
漸化式の $P_{n-1}$ の係数が $1$(thm-pell-number-gcd)$U_0=0$、$U_1=1$、$U_{n+1}=2U_n+2U_{n-1}$:$0,1,2,6,16,44,\dots$$\gcd(U_3,U_4)=\gcd(6,16)=2\ne U_1=1$
表の確かめ

1 行目:$4-2\cdot1=2$ である。$(2,1)$ はどの $(H_n,P_n)$ とも異なる($P_n=1$ となるのは $n=1$ だけで、$H_1=1$)。
2・3 行目:同じ漸化式を満たす数列はどれも $u_{m+n}=P_{m+1}u_n+P_mu_{n-1}$ を満たすが、$u=H$ に当てると右辺に $H_m$ ではなく $P_m$ が現れるので、互除法の議論が働かない。実際 $\gcd(H_3,H_6)=1$ で、$H_3=7$ は $H_6=99=9\cdot11$ を割らない。また $H_4=17$ は素数である。
4 行目:$U_{n+1}U_{n-1}-U_n^2=\pm2^{n-1}$ となり、隣り合う項が互いに素でなくなる。$U_3=6$、$U_4=16$ の最大公約数は $2$ だが、$\gcd(3,4)=1$ に対応する $U_1$ は $1$ である。

関連項目

参考文献

[1]
Marjorie Bicknell, A primer on the Pell sequence and related sequences, The Fibonacci Quarterly, 1975, 定義・負の番号・一般項 (3)(p. 345)、長方形の Figure 1(pp. 345–346)、恒等式 (4)–(20)(p. 346)、行列表示(p. 347)
[2]
Leonard Eugene Dickson, History of the Theory of Numbers, Vol. II: Diophantine Analysis, Dover ed., Dover Publications, 2005, Chapter IV, pp. 181–182(直角をはさむ 2 辺の差が 1 の直角三角形)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する