$p=2+\sqrt{5}$ とおき,自然数 $n=1,2,3,\ldots$ に対して
$$
a_n=p^n+\left(-\frac{1}{p}\right)^n
$$
と定める。以下の問いに答えよ。ただし設問 (1) は結論のみを書けばよい。
(1) $a_1$,$a_2$ の値を求めよ。
(2) $n\geqq 2$ とする。積 $a_1a_n$ を,$a_{n+1}$ と $a_{n-1}$ を用いて表せ。
(3) $a_n$ は自然数であることを示せ。
(4) $a_{n+1}$ と $a_n$ の最大公約数を求めよ。
有理化により
$$
q=-\frac{1}{2+\sqrt5}=-\frac{\sqrt5-2}{(\sqrt5+2)(\sqrt5-2)}=2-\sqrt5 .
$$
すなわち第2項の底 $-1/p$ は $p$ の共役であり,問題文はそれを「符号付きの逆数」として提示している。
$p+q=4$,$pq=-1$ であり,$p,q$ は $x^2-4x-1=0$ の二解である。$a_n=p^n+q^n$ $(n\geqq0)$ であって,
$$
a_{n+2}=4a_{n+1}+a_n\qquad(n\geqq0). \tag{R}
$$
$p+q=4$,$pq=4-5=-1$ は直接の計算による。$p^2=4p+1$ の両辺に $p^n$ を掛けると $p^{n+2}=4p^{n+1}+p^n$ であり,$q$ についても同様である。辺々加えて (R) を得る。
$pq=-1$ は,$p$ が $\mathcal{O}$ の単数(逆元が $\mathcal{O}$ に属する元)であることを意味する。実際 $p^{-1}=-q=\sqrt5-2\in\mathcal{O}$ である。本問の整数論的な結論は,すべてこの事実に由来する。また (R) と $a_0=2$,$a_1=4$ から,すべての $a_n$ は整数である。
第2項の符号は整数性に不可欠である。$p^{-1}=-q$ より
$$
p^n+p^{-n}=p^n+(-1)^nq^n=
\begin{cases}
a_n & (n\ \text{が偶数})\\
p^n-q^n=2c_n\sqrt5 & (n\ \text{が奇数})
\end{cases}
$$
であり,$c_n\geqq1$ $(n\geqq1)$ であるから,符号を除いた $p^n+p^{-n}$ は $n$ が奇数のとき無理数となる。$\left(-\frac1p\right)^n$ の符号は,第2項をちょうど $p^n$ の共役にするための設定である。
(R) は隣接二項の組を整数行列で移す:
$$
\begin{pmatrix}a_{n+1}\\ a_{n+2}\end{pmatrix}=T\begin{pmatrix}a_n\\ a_{n+1}\end{pmatrix},\qquad
T=\begin{pmatrix}0&1\\1&4\end{pmatrix},\qquad \det T=pq=-1 .
$$
$\det T=\pm1$ であるから $T^{-1}=\begin{pmatrix}-4&1\\1&0\end{pmatrix}$ も整数行列であり,$T$ は $\mathbb{Z}^2$ の可逆な線形変換(単模変換)である。
整数 $x,y,k$ と $\varepsilon\in\lbrace1,-1\rbrace$ に対し,組 $(x,y)$ と組 $(y,\,ky+\varepsilon x)$ の公約数全体は一致する。特に $(x,y)\neq(0,0)$ ならば
$$
\gcd(y,\,ky+\varepsilon x)=\gcd(x,y).
$$
$d\mid x$ かつ $d\mid y$ ならば $d\mid ky+\varepsilon x$ である。逆に $d\mid y$ かつ $d\mid ky+\varepsilon x$ ならば,$x=\varepsilon\bigl((ky+\varepsilon x)-ky\bigr)$ より $d\mid x$ である。また $(x,y)=(0,0)$ と $(y,ky+\varepsilon x)=(0,0)$ は同値であるから,後半も従う。
補題3 を (R) に繰り返し適用すると,$\gcd(a_n,a_{n+1})$ は $n$ によらず $\gcd(a_0,a_1)=\gcd(2,4)=2$ に等しい。イデアルの言葉では,$a_n\mathbb{Z}+a_{n+1}\mathbb{Z}=2\mathbb{Z}$ が $n$ によらないということである。本質は (R) の末項の係数 $-pq$ が $\pm1$ であることにあり,$pq$ が単数でなければこの保存は破れる( 5.6 節 )。
$d$ が $x,y$ の公約数ならば,整数係数の斉次二次式 $Ax^2+Bxy+Cy^2$ は $d^2$ で割り切れる。一次結合が $d$ を制限するのに対し,斉次二次式は $d^2$ を制限する。本問では,隣接二項に対して値が符号を除き一定となる二次形式が存在する。
$Q(x,y)=y^2-4xy-x^2$ について,次が成り立つ。
$$
\text{(i)}\ \ Q(x,y)=(y-px)(y-qx),\qquad \text{(ii)}\ \ Q(y,\,4y+x)=-Q(x,y),
$$
$$
\text{(iii)}\ \ Q(a_n,a_{n+1})=20\cdot(-1)^{n+1}\qquad(n\geqq0). \tag{Q}
$$
(i) 右辺 $=y^2-(p+q)xy+pq\,x^2$ に
補題2
を用いる。(ii) $(4y+x)^2-4y(4y+x)-y^2=x^2+4xy-y^2=-Q(x,y)$。(iii) $a_{n+1}-pa_n=q^{n+1}-pq^n=(q-p)q^n$,同様に $a_{n+1}-qa_n=(p-q)p^n$ であるから,(i) より
$$
Q(a_n,a_{n+1})=-(p-q)^2(pq)^n=-20\cdot(-1)^n .
$$
((ii) と $Q(a_0,a_1)=16-32-4=-20$ から帰納的に導くこともできる。)
ゆえに $d=\gcd(a_n,a_{n+1})$ は $d^2\mid20=2^2\cdot5$ を満たし,$d\mid2$ である。定数 $20=(p-q)^2$ は特性方程式 $x^2-4x-1=0$ の判別式に等しい。
補題4
の証明に現れた元
$$
\eta_n=a_{n+1}-pa_n=(q-p)q^n=-2\sqrt5\,q^n\in\mathcal{O} \tag{H}
$$
は,$a_n,a_{n+1}$ の整数係数一次式であり,同時に単数 $q^n$ と定数 $-2\sqrt5$ の積である。この一つの元の四つの側面が,四つの解法を生む。
問題文と数値設定から読み取れる設計を整理する。
| 着目する構造 | 数学的翻訳 | 対応する解法 |
|---|---|---|
| $p,q$ の和と積が整数 | 整数係数の漸化式 (R) | 本解 (2)(3), 3.2 節 |
| (R) の末項係数 $-pq=1$ | 単模変換による $\gcd$ の保存 | 本解 (4) |
| 共役の二項展開で奇数次が相殺 | 二項定理 | 3.1 節 |
| $Q(x,y)=(y-px)(y-qx)$ の符号不変性 | $d^2\mid20$ | 別解1 |
| $p^n$ の整数座標とノルム $\pm1$ | Bézout 型等式 | 参考解1 |
| $p,q$ が $\mathcal{O}$ の単数 | $\mathcal{O}$ における整除 | 参考解2 |
| $p$ が代数的整数 | トレースの整数性 | 参考解3 |
| $p,q$ が非負整数行列の固有値 | 閉歩道の数え上げ | 参考解4 |
$-1/p$ を有理化して共役 $q=2-\sqrt5$ を見出し,和と積から (2) を得る。(2) を漸化式 (R) に読み替え,(3) は二項ずつの数学的帰納法で,(4) は 補題3 により最大公約数を初期値まで下降させて処理する。
$$
a_1=4,\qquad a_2=18 .
$$
($q=-1/p=2-\sqrt5$ として $a_1=p+q=4$,$a_2=(p+q)^2-2pq=18$。)
$q=-\dfrac1p=\dfrac{-1}{2+\sqrt5}=2-\sqrt5$ であるから $p+q=4$,$pq=-1$,$a_n=p^n+q^n$ である。$n\geqq2$ のとき
$$
\begin{aligned}
a_1a_n&=(p+q)(p^n+q^n)=p^{n+1}+q^{n+1}+pq\,(p^{n-1}+q^{n-1})\\
&=a_{n+1}-a_{n-1}.
\end{aligned}
$$
よって
$$
a_1a_n=a_{n+1}-a_{n-1}.
$$
(1)(2) より $a_{n+1}=4a_n+a_{n-1}$ $(n\geqq2)$,すなわち
$$
a_{n+2}=4a_{n+1}+a_n\qquad(n\geqq1)
$$
である((R) の $n\geqq1$ の部分)。$n\geqq1$ に対する命題 $P(n)$:「$a_n,\ a_{n+1}$ はともに正の整数である」を帰納法で示す。$P(1)$ は (1) より成り立つ。$P(n)$ を仮定すると $a_{n+2}=4a_{n+1}+a_n$ は正の整数であるから $P(n+1)$ が成り立つ。ゆえにすべての自然数 $n$ について $a_n$ は自然数である。
$(2\pm\sqrt5)^n$ を展開すると,$\sqrt5$ の奇数乗の項は符号が逆で相殺する。漸化式を用いずに,整数性・正値性・偶数性が同時に得られる。
二項定理より
$$
p^n=\sum_{k=0}^{n}\binom nk 2^{n-k}(\sqrt5)^k,\qquad q^n=\sum_{k=0}^{n}\binom nk 2^{n-k}(-\sqrt5)^k .
$$
辺々加えると $k$ が奇数の項は相殺し,
$$
a_n=2\sum_{j=0}^{\lfloor n/2\rfloor}\binom n{2j}2^{n-2j}5^j . \tag{E}
$$
和の各項は非負整数であり,$j=0$ の項 $2^n$ は正である。ゆえに $a_n$ は正の偶数であり,特に自然数である。
$n=2$:$2(4+5)=18$。$n=3$:$2\bigl(8+\binom32\cdot2\cdot5\bigr)=76$。(E) は $b_n=\sum_j\binom n{2j}2^{n-2j}5^j\in\mathbb{Z}$ を示しており,以下の別解・参考解で用いる下界 $2\mid\gcd(a_n,a_{n+1})$ の根拠となる。偶数性は $a_1,a_2$ が偶数であることと (R) からも帰納的に従う。
積 $a_1a_n$ を展開する代わりに,$p,q$ が満たす二次方程式に $p^{n-1},q^{n-1}$ を掛ける。
$p^2=4p+1$ の両辺に $p^{n-1}$ を掛けて $p^{n+1}=4p^n+p^{n-1}$,$q$ についても同様である。辺々加えて $a_{n+1}=4a_n+a_{n-1}$ $(n\geqq2)$。$a_1=4$ であるから $a_1a_n=a_{n+1}-a_{n-1}$。
二つの導出の違いは,$pq=-1$ を積の交差項で使うか,特性方程式の定数項で使うかにある。一般に $\alpha,\beta$ が $x^2-sx+\varepsilon=0$ の解ならば,いずれの導出からも $V_{n+1}=sV_n-\varepsilon V_{n-1}$($V_n=\alpha^n+\beta^n$)を得る( 5.6 節 )。行列 $M=\begin{pmatrix}4&1\\1&0\end{pmatrix}$ に対する Cayley–Hamilton の定理 $M^2=4M+I$ も同じ関係を与える(参考解4)。
公約数を初期値まで遡らせる代わりに,隣接二項の斉次二次式で値が一定となるものを用い,$d^2$ を一度に制限する。$Q(x,y)=(y-px)(y-qx)$ に隣接二項を代入すると,$p^n$ と $q^n$ の寄与が互いに打ち消し合い,$(pq)^n$ だけが残る。
本解と同じである。
3.1 節 により $a_n$ は正の偶数である。
$n\geqq1$ とし,$d=\gcd(a_n,a_{n+1})$ とおく。$a_n=p^n+q^n$ より
$$
a_{n+1}-pa_n=(q-p)q^n,\qquad a_{n+1}-qa_n=(p-q)p^n .
$$
辺々掛けると,左辺は $a_{n+1}^2-(p+q)a_na_{n+1}+pq\,a_n^2$,右辺は $-(p-q)^2(pq)^n$ であるから,$p+q=4$,$pq=-1$,$(p-q)^2=20$ を用いて
$$
a_{n+1}^2-4a_na_{n+1}-a_n^2=20\cdot(-1)^{n+1}.
$$
左辺の各項は $d^2$ の倍数であるから $d^2\mid20=2^2\cdot5$。素因数ごとの指数を比べて $d\mid2$ である。一方 (3) より $a_n,a_{n+1}$ はともに偶数であるから $2\mid d$。ゆえに
$$
\gcd(a_{n+1},a_n)=2 .
$$
$b_n=a_n/2$ に対しては $b_{n+1}^2-4b_nb_{n+1}-b_n^2=5\cdot(-1)^{n+1}$ であり,$\gcd(b_n,b_{n+1})^2\mid5$ より $\gcd(b_n,b_{n+1})=1$。$5$ が平方因子をもたないことが互いに素性を直接与える。
$p^n$ を整数座標 $(b_n,c_n)$ で表すと,$pq=-1$ はノルムの等式 $b_n^2-5c_n^2=(-1)^n$ に翻訳される。隣接する二つの座標ベクトルの行列式がこのノルムに等しいことから,$a_n,a_{n+1}$ の整数係数一次結合で $\pm2$ を表す等式が得られる。
$$
b_n=\sum_{j=0}^{\lfloor n/2\rfloor}\binom n{2j}2^{n-2j}5^j,\qquad
c_n=\sum_{j=0}^{\lfloor (n-1)/2\rfloor}\binom n{2j+1}2^{n-2j-1}5^j
$$
とおくと $b_n,c_n$ は整数であり,二項定理より $p^n=b_n+c_n\sqrt5$,$q^n=b_n-c_n\sqrt5$ である。ゆえに $a_n=2b_n$ であり,$b_n\geqq2^n > 0$ より $a_n$ は正の偶数,特に自然数である。なお $c_n\geqq n\cdot2^{n-1}\geqq1$ である。
$n\geqq1$ とする。$pq=-1$ より
$$
b_n^2-5c_n^2=(b_n+c_n\sqrt5)(b_n-c_n\sqrt5)=(pq)^n=(-1)^n . \tag{N}
$$
$p^{n+1}=p\cdot p^n$,$q^{n+1}=q\cdot q^n$ を展開すると
$$
b_{n+1}\pm c_{n+1}\sqrt5=(2b_n+5c_n)\pm(b_n+2c_n)\sqrt5\qquad(\text{複号同順})
$$
であり,複号の二式の和と差から $b_{n+1}=2b_n+5c_n$,$c_{n+1}=b_n+2c_n$ を得る。よって
$$
b_nc_{n+1}-b_{n+1}c_n=b_n(b_n+2c_n)-(2b_n+5c_n)c_n=b_n^2-5c_n^2=(-1)^n ,
$$
$a_n=2b_n$ を用いて
$$
a_nc_{n+1}-a_{n+1}c_n=2\cdot(-1)^n . \tag{D}
$$
$c_n,c_{n+1}$ は整数であるから,$a_n,a_{n+1}$ の任意の正の公約数 $d$ は $d\mid2$ を満たす。(3) より $2\mid d$ でもあるから,$\gcd(a_{n+1},a_n)=2$。
$a_{n+1}$ から $pa_n$ を引くと $p^{n+1}$ が消え,$(q-p)q^n$ だけが残る((H))。$q$ は $\mathcal{O}$ において可逆であるから,共通因子 $d$ は $\mathcal{O}$ の中で $q-p=-2\sqrt5$ を割り切る。漸化式も二次形式も用いない。
(1)(2) は本解と同じであり,(3) と全項の偶数性は 3.1 節 による。
$n\geqq1$ とし,$d$ を $a_n,a_{n+1}$ の正の公約数,$a_n=dx$,$a_{n+1}=dy$ $(x,y\in\mathbb{Z})$ とする。
$$
a_{n+1}-pa_n=(p^{n+1}+q^{n+1})-p(p^n+q^n)=(q-p)q^n
$$
より $d\,(y-px)=(q-p)q^n$ である。$pq=-1$ より $q^{-1}=-p$ であるから,両辺に $q^{-n}=(-p)^n$ を掛けて
$$
-2\sqrt5=q-p=d\,(y-px)(-p)^n .
$$
$y-px$ と $(-p)^n$ は $\mathcal{O}$ に属し,$\mathcal{O}$ は乗法について閉じているから,$(y-px)(-p)^n=u+v\sqrt5$ $(u,v\in\mathbb{Z})$ と書ける。よって $-2\sqrt5=du+dv\sqrt5$,すなわち $(dv+2)\sqrt5=-du$ である。$\sqrt5$ は無理数であるから $dv+2=0$,$du=0$ であり,特に $d\mid2$。偶数性より $2\mid d$ であるから,$\gcd(a_{n+1},a_n)=2$。
$a_n$ を,二次体 $K=\mathbb{Q}(\sqrt5)$ における $p^n$ のトレース(共役との和)とみる。整数性は「代数的整数のトレースは有理整数である」という一般定理から従う。高校数学の範囲外であり,(3) の構造的な説明として位置づける。
$p$ はモニック整数係数多項式 $x^2-4x-1$ の根であるから代数的整数であり,代数的整数全体は環をなすから $p^n$ も代数的整数である。$K$ の非自明な自己同型 $\sigma:\sqrt5\mapsto-\sqrt5$ について $\sigma(p^n)=q^n$ であるから
$$
\operatorname{Tr}_{K/\mathbb{Q}}(p^n)=p^n+\sigma(p^n)=p^n+q^n=a_n .
$$
代数的整数の最小多項式は整数係数であり,トレースはその係数の整数倍として表されるから,$a_n\in\mathbb{Z}$ である。さらに $p > 1$,$-1 < q < 0$ より $p^n > 1 > \lvert q\rvert^n$,ゆえに $a_n=p^n+q^n > 0$。
トレースの整数性は正値性を含まない。正値性には $\lvert q\rvert < 1 < p$ という実数としての評価が別に必要である。また本解法は (4) を与えない。
$p,q$ を固有値にもつ非負整数行列を構成し,$a_n$ をその冪のトレース,すなわち有向グラフの閉歩道の個数として解釈する。
$M=\begin{pmatrix}4&1\\1&0\end{pmatrix}$ とおくと $\det(xI-M)=x(x-4)-1=x^2-4x-1$ であり,$M$ の固有値は相異なる $p,q$ である。$M$ は対角化可能で,$M^n$ の固有値は $p^n,q^n$ であるから $\operatorname{tr}(M^n)=p^n+q^n=a_n$。
$M$ を,頂点 $1,2$ をもつ有向多重グラフ(頂点 $1$ にループ $4$ 本,$1\to2$ と $2\to1$ に辺各 $1$ 本)の隣接行列とみる。$(M^n)_{ii}$ は頂点 $i$ から出て $i$ に戻る長さ $n$ の歩道の個数であるから,$\operatorname{tr}(M^n)$ は長さ $n$ の閉歩道の総数であり,非負整数である。頂点 $1$ のループだけを用いる閉歩道が $4^n$ 個あるから
$$
a_n=\operatorname{tr}(M^n)\geqq4^n > 0 .
$$
以下は,上記のいずれかと発想の核を共有するか,(3)(4) の独立した決定原理を与えないため,独立の解法として数えない。
| 解法 | 対象 | 核となる構造 | 公約数 $d$ に課す条件 | 前提 |
|---|---|---|---|---|
| 本解 | (1)〜(4) | 単模な漸化式 (R) | $\gcd$ の保存(等式) | 対称式,帰納法,互除法 |
| 3.1 節 | (3) | 共役展開の相殺 | なし(偶数性を与える) | 二項定理 |
| 3.2 節 | (2) | 特性方程式 | なし | 二次方程式 |
| 別解1 | (4) | 二次形式 $Q$ の符号不変性 | $d^2\mid20$ | 斉次式の整除 |
| 参考解1 | (3)(4) | ノルム $\pm1$ と行列式 | $d\mid2$(Bézout 型等式) | 整数座標,二項定理 |
| 参考解2 | (4) | $\mathcal{O}$ の単数 $q$ | $\mathcal{O}$ で $d\mid2\sqrt5$ | $\mathcal{O}$ の閉性,無理数性 |
| 参考解3 | (3) | 代数的整数 | なし | 代数的整数論 |
| 参考解4 | (3) | 非負整数行列 | なし | 線形代数,グラフ |
本解は,(2) の誘導を (3)(4) へ直結させ,対称式・帰納法・互除法という高校数学の標準的な道具だけで完結する。上界と下界を分けずに等式 $\gcd(a_n,a_{n+1})=\gcd(a_1,a_2)$ で結論でき,論証の分岐も最少である。これが本解として採用する理由である。
別解1は,ただ一つの恒等式 (Q) から $\gcd$ を決定し,(4) について誘導 (2) すら要しない。ただし $Q$ の発見に工夫を要し,下界のために偶数性を別に示す必要がある。参考解1・2は (H) の座標と整除という代数的構造を明示し,
5.5 節
〜
5.7 節
の一般化に直結するが,補助変数や環 $\mathcal{O}$ の取り扱いの説明を要する。参考解3・4は (3) の説明原理であり,(4) を与えない。
本問から抽出される手順を,「代数的数の冪和」と「隣接項の最大公約数」に関する問題一般に適用できる形で述べる。以下 $\alpha,\beta$ を $x^2-sx+\varepsilon=0$ $(s,\varepsilon\in\mathbb{Z})$ の二解,$V_n=\alpha^n+\beta^n$,$\Delta=(\alpha-\beta)^2=s^2-4\varepsilon$ とする。
| 症状 | 検討する表現・道具 | 本問での対応 |
|---|---|---|
| 無理数とその符号付き逆数が並ぶ | 有理化して共役か確認 | $-1/p=2-\sqrt5$ |
| 二数の和と積が整数 | 整数係数の三項間漸化式 | 補題2 |
| 漸化式の末項係数が $\pm1$ | 互除法,単模行列 | 本解 |
| 末項係数が $\pm1$ でない | 不変量,Bézout 型等式,合同式 | 5.6 節 の例 |
| 隣接二項の二次式の値が一定 | $d^2\mid C$ | 別解1 |
| 二次無理数の冪 | 整数座標とノルム | 参考解1 |
| 冪の差に単数が掛かっている | 環における整除 | 参考解2 |
| 上界に候補素数が残る | その素数を法とする計算 | 3.8 節 |
| 冪和の整数性だけが問われる | 二項展開,トレース,行列 | 3.1 節,参考解3・4 |
本問の構造は類題の設計原理としても読める。
各節で,高校数学の範囲で完結する内容(高校数学の範囲)と,それを超える一般論(発展)とを区別して記す。
| 主題 | 高校数学の範囲 | 一般理論 |
|---|---|---|
| $\gcd$ の保存 | 互除法, 補題3 | $\mathrm{GL}_2(\mathbb{Z})$ の作用と原始ベクトル |
| 二次の不変量 | $d^2\mid Q(x,y)$ | 二元二次形式,判別式,ノルム形式 |
| 共役とノルム | 有理化,$(u+v\sqrt5)(u-v\sqrt5)$ | 二次体,整環,単数群,Pell 方程式 |
| 環での整除 | $\sqrt5$ の無理数性による係数比較 | イデアル,剰余環,冪零元,結果式 |
| 整数性 | 帰納法,二項定理 | 代数的整数のトレース |
| 数え上げ | なし | 隣接行列,閉軌道,ゼータ関数 |
| 特殊な数列 | 漸化式の計算 | Lucas 列の整除性 |
有理化と $(u+v\sqrt5)(u-v\sqrt5)=u^2-5v^2$ の計算,$\sqrt5$ の無理数性による係数比較で,本問の議論はすべて完結する。
発展 $K=\mathbb{Q}(\sqrt5)$ の整数環は $\mathcal{O}_K=\mathbb{Z}[\varphi]$($\varphi=\frac{1+\sqrt5}{2}$)であり,$\mathcal{O}=\mathbb{Z}[\sqrt5]$ はその指数 $2$ の部分環(導手 $2$ の整環)である。$\xi\in\mathcal{O}$ が単数であることは $N(\xi)=\pm1$ と同値であり,Dirichlet の単数定理と,$1$ より大きい最小の単数が $2+\sqrt5$ であること($x^2-5y^2=\pm1$ の解で $y=1$ のものから分かる)により
$$
\mathcal{O}^{\times}=\lbrace\pm(2+\sqrt5)^k\mid k\in\mathbb{Z}\rbrace
$$
となる。すなわち $p=2+\sqrt5$ は整環 $\mathcal{O}$ の基本単数である。一方 $\mathcal{O}_K$ の基本単数は $\varphi$ であり,$p=\varphi^3$,かつ $\varphi^k\in\mathcal{O}\iff3\mid k$ が成り立つ。したがって $x^2-5y^2=\pm1$ の正の整数解は $(x,y)=(b_n,c_n)$ $(n\geqq1)$ に限られ,(N) により二本の双曲線 $x^2-5y^2=-1$,$x^2-5y^2=1$ の上を交互に移る。本問は,$\mathcal{O}$ の単数群の生成元 $p$ に関する問題として読み直せる。
補題3
とその反復で十分である。
発展 $\boldsymbol{v}\in\mathbb{Z}^2\setminus\lbrace\boldsymbol{0}\rbrace$ の成分の最大公約数を $\operatorname{cont}(\boldsymbol{v})$ と書く。整数行列 $W$ に対し $\operatorname{cont}(\boldsymbol{v})\mid\operatorname{cont}(W\boldsymbol{v})$ であり,$\operatorname{adj}(W)\,W=(\det W)I$ より $\operatorname{cont}(W\boldsymbol{v})\mid(\det W)\operatorname{cont}(\boldsymbol{v})$ である。特に $W\in\mathrm{GL}_2(\mathbb{Z})$($\det W=\pm1$)は $\operatorname{cont}$ を保つ。本解は $(a_n,a_{n+1})^{\top}=T^n(a_0,a_1)^{\top}$ と $\det T=-1$ からの帰結である。
参考解1の座標 $\boldsymbol{v}_n=(b_n,c_n)^{\top}$ は $\boldsymbol{v}_{n+1}=U\boldsymbol{v}_n$,$U=\begin{pmatrix}2&5\\1&2\end{pmatrix}$(基底 $1,\sqrt5$ に関する $p$ 倍写像)に従い,$\det U=N(p)=-1$ である。(D) は $\det(\boldsymbol{v}_n,\boldsymbol{v}_{n+1})=(-1)^n$,すなわち $\boldsymbol{v}_n,\boldsymbol{v}_{n+1}$ が $\mathbb{Z}^2$ の基底をなす(張る平行四辺形の面積が $1$)ことを意味する。
一方,座標の取り替え $(b_n,c_n)\mapsto(b_n,b_{n+1})$ の行列 $W=\begin{pmatrix}1&0\\2&5\end{pmatrix}$ は $\det W=5$ である。上の整除関係から $\gcd(b_n,b_{n+1})\mid5\gcd(b_n,c_n)=5$ となり,Cassini 型の解法で現れる候補 $5$ はこの単模でない座標変換に由来する。それを消すには,法 $5$ の計算か,二次形式による $d^2$ の制限が必要になる。
補題4
の (i)(ii) と,$d\mid x,y\Rightarrow d^2\mid Q(x,y)$ で十分である。
発展 $Q(x,y)=-x^2-4xy+y^2$ は判別式 $(-4)^2-4\cdot(-1)\cdot1=20$ の二元二次形式である。$\mathcal{O}=\mathbb{Z}+\mathbb{Z}p$ であるから $(x,y)\mapsto y-xp$ は $\mathbb{Z}^2$ から $\mathcal{O}$ への全単射であり,
$$
Q(x,y)=N(y-xp)
$$
が成り立つ。すなわち $Q$ は $\mathcal{O}$ のノルム形式である。この対応のもとで
$$
T:(x,y)\mapsto(y,\,4y+x)\quad\longleftrightarrow\quad \xi\mapsto q\,\xi
$$
である($(4y+x)-yp=q(y-xp)$ は $q=4-p$ から直接確かめられる)。したがって
$$
\det T=N(q)=-1,\qquad Q\circ T=N(q)\,Q=-Q
$$
であり,本解の単模性と別解1の符号反転は同じ事実 $N(q)=-1$ の二つの現れである。$T^2$ は行列式 $1$ で $Q$ を保つ($Q$ の真の自己同型である)。正規化版では $b_{n+1}-pb_n=-\sqrt5\,q^n$ より $Q(b_n,b_{n+1})=N(-\sqrt5)N(q)^n=5\cdot(-1)^{n+1}$ である。一般に $Q(x,y)$ は $\operatorname{cont}(x,y)^2$ で割り切れるから,$Q$ の値が平方因子をもたなければ $(x,y)$ は原始的である。
参考解2の係数比較で十分である。
発展 素数 $r$ が $a_n,a_{n+1}$ を割り切れば $r\mid Q(a_n,a_{n+1})=\pm(p-q)^2$ であり,候補は判別式 $20$ の素因数 $2,5$ に限られる。ところが $5$ は実際には現れない。その理由は剰余環の構造にある:
$$
\mathcal{O}/5\mathcal{O}\cong\mathbb{F}_5[\epsilon]/(\epsilon^2)\qquad(\epsilon=\sqrt5\bmod5)
$$
は零でない冪零元 $\epsilon$ をもつ。$(p-q)^2=20\in5\mathcal{O}$ であっても $p-q=2\sqrt5\notin5\mathcal{O}$ である。参考解2は平方する前の $p-q$ を直接扱い,$\mathcal{O}$ における $d\mid2\sqrt5$ を得るから,候補 $5$ が最初から現れない。別解1は平方したノルムを用いるが,$d$ についても平方 $d^2$ を用いるため情報を失わない。$5$ が残るのは,平方されたノルムに対して $d$ を一次でしか用いない Cassini 型の議論だけである。
参考解2の系列は結果式で統一される。モニックな $f\in\mathbb{Z}[X]$ と $g\in\mathbb{Z}[X]$ に対し,$\operatorname{Res}(f,g)=\prod_{f(\zeta)=0}g(\zeta)$ であり,$Af+Bg=\operatorname{Res}(f,g)$ を満たす $A,B\in\mathbb{Z}[X]$ が存在する。$f=1+X^n$,$g=1+X^{n+1}$ のとき,$f$ の根 $\zeta$ について $g(\zeta)=1-\zeta$ であるから
$$
\operatorname{Res}_X(1+X^n,\,1+X^{n+1})=\prod_{\zeta^n=-1}(1-\zeta)=f(1)=2 .
$$
3.8 節
の Bézout 等式はその具体形である。
さらに $\gcd(m,n)=1$ かつ $m+n$ が奇数ならば $\operatorname{Res}_X(1+X^m,1+X^n)=2$ である。実際,$\operatorname{Res}(f,g)=(-1)^{mn}\operatorname{Res}(g,f)$ と $mn$ が偶数であることから,$n$ が奇数として示せばよい。$1+X^m$ の根は $e^{\pi ik/m}$($k$ は法 $2m$ の奇数剰余類)であり,$\gcd(n,2m)=1$ より $k\mapsto nk$ は奇数剰余類の置換であるから,$\zeta\mapsto\zeta^n$ は根の置換となる。よって $\operatorname{Res}=\prod(1+\zeta)=(-1)^m(1+(-1)^m)=2$($m$ は偶数)。$X=r=q/p$ を代入すれば,この場合 $\gcd(a_m,a_n)\mid2$,すなわち $\gcd(a_m,a_n)=2$ が従う。これは
定理6
と整合する。
次の定理の証明は 補題3 と帰納法のみによる。
$s\in\mathbb{Z}$,$\varepsilon\in\lbrace1,-1\rbrace$ とし,$\alpha,\beta$ を $x^2-sx+\varepsilon=0$ の二解,$V_n=\alpha^n+\beta^n$ $(n\geqq0)$ とする。このとき $V_n\in\mathbb{Z}$ であり,すべての $n\geqq0$ に対して $(V_n,V_{n+1})\neq(0,0)$ かつ
$$
\gcd(V_n,V_{n+1})=\gcd(2,s).
$$
$V_0=2$,$V_1=s$,$V_{n+2}=sV_{n+1}-\varepsilon V_n$ より,帰納的に $V_n\in\mathbb{Z}$。 補題3 ($k=s$,符号 $-\varepsilon\in\lbrace1,-1\rbrace$)により $(V_n,V_{n+1})$ と $(V_{n+1},V_{n+2})$ の公約数全体は一致するから,$(V_n,V_{n+1})$ の公約数全体は $(V_0,V_1)=(2,s)$ のそれに等しい。$(2,s)\neq(0,0)$ であるから主張が従う。
本問は $s=4$,$\varepsilon=-1$ の場合である。$\alpha=k+\sqrt{k^2+1}$ $(k\in\mathbb{Z}_{>0})$ では $s=2k$ であり,$\gcd(V_n,V_{n+1})=2$,正規化した $V_n/2$ の隣接二項は互いに素である。$s$ が奇数ならば隣接二項は互いに素である。
発展 $\varepsilon=\alpha\beta$ が単数でなければ結論は破れる。$x^2-4x+2=0$ の解 $\alpha,\beta=2\pm\sqrt2$ では $V_n=2,4,12,40,136,464,\ldots$,$\gcd(V_n,V_{n+1})=2,4,4,8,8,16,\ldots$ である。$\alpha=\sqrt2(\sqrt2+1)$,$\beta=\sqrt2(\sqrt2-1)$ と書けば $V_n$ は $2^{\lceil n/2\rceil}$ で割り切れ,隣接二項の $\gcd$ は有界でない。
4.1 節
(5) の不変量の値 $(V_{n+1}-\alpha V_n)(V_{n+1}-\beta V_n)=-\Delta\,\varepsilon^n=-8\cdot2^n$ が $n$ とともに増大することと対応している。隣接冪和の共通因子を有界に保つ本質的な条件は
$$
\alpha\beta=\pm1\qquad(\alpha,\beta\ \text{が単数})
$$
であり,$\sqrt5$ や係数 $4$ は本質ではない。
本問は隣接二項に限られ,互除法の一段の下降で済む。
発展 $\varphi=\frac{1+\sqrt5}{2}$,$\psi=\frac{1-\sqrt5}{2}$ とすると $\varphi^3=2+\sqrt5=p$,$\psi^3=2-\sqrt5=q$ である。Lucas 数 $L_m=\varphi^m+\psi^m$,Fibonacci 数 $F_m=\frac{\varphi^m-\psi^m}{\sqrt5}$ を用いると
$$
a_n=L_{3n},\qquad b_n=\frac{L_{3n}}{2},\qquad c_n=\frac{F_{3n}}{2}
$$
であり,(N) は恒等式 $L_m^2-5F_m^2=4\cdot(-1)^m$ の $m=3n$ の場合である。隣接しない二項については次が成り立つ。
$m,n\geqq1$,$g=\gcd(m,n)$ とする。このとき
$$
\gcd(a_m,a_n)=
\begin{cases}
a_g & (v_2(m)=v_2(n)),\\
2 & (v_2(m)\neq v_2(n)).
\end{cases}
$$
すべての整数 $k$ に対し $b_k=\frac{p^k+q^k}{2}$ と定めると,$p^{-1}=-q$,$q^{-1}=-p$ より $b_{-k}=(-1)^kb_k$ である。任意の整数 $i,j$ について $p^iq^j+q^ip^j=(pq)^j(p^{i-j}+q^{i-j})$ であるから
$$
2b_ib_j=b_{i+j}+(-1)^jb_{i-j}.
$$
$i=m-n$,$j=n$ とおくと $b_m=2b_{m-n}b_n-(-1)^nb_{m-2n}$ であり,
補題3
と同様にして
$$
\gcd(b_m,b_n)=\gcd(b_{\lvert m-2n\rvert},\,b_n)\qquad(m > n\geqq1).
$$
$m=n$ の場合は自明であり,対称性から $m > n$ としてよい。$v_2(0)=\infty$ と約束し,組 $(m,n)$ $(m > n\geqq1)$ を組 $\lbrace n,\lvert m-2n\rvert\rbrace$ に置き換える操作を考える。この操作で (a) $\gcd(b_m,b_n)$,(b) 添字の最大公約数($\gcd(\lvert m-2n\rvert,n)=\gcd(m,n)$),(c) 「$v_2$ が等しいか否か」は不変である。(c) は $k=v_2(n)$ として,$v_2(m) < k$ なら $v_2(m-2n)=v_2(m)$,$v_2(m)=k$ なら $m-2n=2^k\cdot(\text{奇数})$,$v_2(m) > k$ なら $v_2(m-2n)\geqq k+1$ となることによる。$\lvert m-2n\rvert\notin\lbrace0,n\rbrace$ ならば新しい組は相異なる正の添字からなり,その大きい方は $m$ より小さい。ゆえに操作は有限回で $\lvert m-2n\rvert=0$ または $\lvert m-2n\rvert=n$ に達する。前者では組 $(0,n)$ となり,(b) より $n=g$,(c) より $v_2$ は相異なり,$\gcd=\gcd(b_0,b_g)=1$。後者では組 $(n,n)$ となり,$n=g$,$v_2$ は等しく,$\gcd=b_g$。したがって $\gcd(b_m,b_n)$ は $v_2(m)=v_2(n)$ のとき $b_g$,そうでないとき $1$ であり,$a_k=2b_k$ から主張を得る。
$v_2(n)\neq v_2(n+1)$ であるから, 定理6 は本問の結論 $\gcd(a_n,a_{n+1})=2$ を含む。例えば $\gcd(a_1,a_3)=\gcd(4,76)=4=a_1$,$\gcd(a_2,a_4)=\gcd(18,322)=2$ である。$a_m=L_{3m}$ と読めば,$v_2(3m)=v_2(m)$,$\gcd(3m,3n)=3g$ であり, 定理6 は Lucas 数の整除性に関する古典的な結果の特殊化に当たる。
互除法の各段の商を記録すれば連分数が得られる。
発展 $b_{n+1}=4b_n+b_{n-1}$,$0 < b_{n-1} < b_n$ $(n\geqq1)$ と $b_1=2b_0$ より,$(b_{n+1},b_n)$ に対する互除法の商の列は $4,\ldots,4,2$ であり,
$$
\frac{b_{n+1}}{b_n}=[4;\underbrace{4,\ldots,4}_{n-1},2]\qquad(n\geqq1)
$$
となる(例:$\frac{9}{2}=[4;2]$,$\frac{38}{9}=[4;4,2]$)。$\frac{b_{n+1}}{b_n}\to p$ であり,$p-4=\sqrt5-2=\frac1p$ より $p=[4;4,4,\ldots]=[\overline{4}]$ である。また $\sqrt5=2+\frac{1}{p}=[2;\overline{4}]$ の近似分数の列は $\frac{b_1}{c_1},\frac{b_2}{c_2},\ldots=\frac21,\frac94,\frac{38}{17},\ldots$ であり,$\lvert b_n-c_n\sqrt5\rvert=\lvert q\rvert^n=p^{-n}$ がその近似の精度を与える。Pell 方程式の解が $\sqrt D$ の近似分数から得られるという古典的事実の一例である。
三項間漸化式と $\lvert q\rvert < 1$ の評価で十分である。
発展 $a_0=2$ を含めた母関数は
$$
G(z)=\sum_{n\geqq0}a_nz^n=\frac{1}{1-pz}+\frac{1}{1-qz}=\frac{2-4z}{1-4z-z^2}
$$
である。参考解4の行列 $M$ について $a_n=\operatorname{tr}(M^n)$ は,$M$ を隣接行列とするグラフ上の長さ $n$ の閉歩道の数であり,
$$
\zeta_M(z)=\exp\Bigl(\sum_{n\geqq1}\frac{a_n}{n}z^n\Bigr)=\frac{1}{\det(I-zM)}=\frac{1}{1-4z-z^2},\qquad G(z)=2+z\,\frac{\zeta_M'(z)}{\zeta_M(z)}
$$
が成り立つ。前者は,有限型シフトのゼータ関数に対する Bowen–Lanford の公式の一例である。
$t=\log p$ とおくと $\sinh t=\frac{p-p^{-1}}{2}=2$,すなわち $t=\operatorname{arsinh}2$ であり,$p=e^t$,$q=-e^{-t}$ より
$$
a_{2k}=2\cosh 2kt,\qquad a_{2k+1}=2\sinh(2k+1)t .
$$
$p$ は $1$ より大きい代数的整数で,共役 $q$ が $\lvert q\rvert < 1$ を満たす。このような数を Pisot 数という。$p^n=a_n-q^n$ であるから,$p^n$ と最も近い整数との距離は $\lvert q\rvert^n=p^{-n}$ であり,指数的に $0$ に近づく($n$ が奇数なら $p^n$ はわずかに整数より大きく,偶数なら小さい)。これらの表示は大きさを精密に記述するが,最大公約数の決定原理は与えない。
ユークリッドの互除法は『原論』第7巻に現れる。整数の最大公約数を一次結合で表す等式は Bachet(1624)にさかのぼり,多項式に対する同種の等式は Bézout の名で呼ばれる。$x^2-Dy^2=\pm1$ の研究はインドの Brahmagupta(7世紀)と Bhāskara II(12世紀)にさかのぼり,一般の可解性は18世紀に Lagrange が連分数を用いて証明した。「Pell 方程式」という名称は,Euler による John Pell への誤った帰属に由来する。Fibonacci 数の恒等式 $F_{n+1}F_{n-1}-F_n^2=(-1)^n$ は Cassini(1680)によるとされ,$\alpha^n+\beta^n$ 型の数列の整除性は Lucas(1878)が体系的に研究した。
$$
\begin{array}{c}
p=2+\sqrt5,\qquad -\dfrac1p=2-\sqrt5=q\qquad(\text{有理化による共役の発見})\\
\Downarrow\\
p+q=4,\qquad pq=-1\qquad(p\ \text{は}\ \mathbb{Z}[\sqrt5]\ \text{の単数})\\
\Downarrow\\
a_{n+2}=4a_{n+1}+a_n,\qquad \det T=N(q)=-1\\
\Downarrow\\
\begin{array}{c|c}
\text{(3) 整数性・正値性} & \text{(4) 最大公約数}\\ \hline
\text{帰納法(本解)} & \text{保存:互除法(本解)}\\
\text{二項展開(3.1 節)} & \text{二次の制限:}d^2\mid20\ \text{(別解1)}\\
\text{トレース(参考解3)} & \text{一次の制限:Bézout 型等式(参考解1)}\\
\text{閉歩道(参考解4)} & \text{環での整除:}d\mid2\sqrt5\ \text{(参考解2)}
\end{array}\\
\Downarrow\\
\text{本解:}\gcd(a_n,a_{n+1})=\gcd(a_1,a_2)\qquad\text{他:上界 }d\mid2\ \text{と下界 }2\mid d\\
\Downarrow\\
\gcd(a_{n+1},a_n)=2
\end{array}
$$
四つの (4) の解法は,一つの元 $\eta_n=a_{n+1}-pa_n$ の異なる側面である。
$$
\eta_n=-2\sqrt5\,q^n\ \ \Longrightarrow\ \
\begin{cases}
\eta_{n+1}=q\,\eta_n\ \ (\det T=N(q)=-1) & \to\ \text{本解}\\
N(\eta_n)=Q(a_n,a_{n+1})=20\cdot(-1)^{n+1} & \to\ \text{別解1}\\
\eta_n=10c_n-2b_n\sqrt5 & \to\ \text{参考解1}\\
d\mid\eta_n\ \Rightarrow\ d\mid-2\sqrt5\ \ (\text{in}\ \mathcal{O}) & \to\ \text{参考解2}
\end{cases}
$$
| 設問 | 結論 | 根拠 |
|---|---|---|
| (1) | $a_1=4,\ a_2=18$ | $a_1=p+q$,$a_2=(p+q)^2-2pq$ |
| (2) | $a_1a_n=a_{n+1}-a_{n-1}$ | $pq=-1$ |
| (3) | $a_n$ は自然数(正の偶数) | (R) と二項ずつの帰納法 |
| (4) | $\gcd(a_{n+1},a_n)=2$ | 単模性により $\gcd(a_2,a_1)$ に帰着 |