0

2017年 東京大学 理系 第4問

7
0
$$$$
2017年 東京大学 理系 第4問

$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$ の最大公約数を求めよ。

1. 問題の構造

1.1 記法

  • 自然数は正の整数を指す。整数 $x,y$ について $x\mid y$ は「$x$ が $y$ を割り切る」ことを表す。
  • 同時には $0$ でない整数 $x,y$ に対し,$\gcd(x,y)$ は $x,y$ の正の公約数の最大値である。これは $x\mathbb{Z}+y\mathbb{Z}=\gcd(x,y)\,\mathbb{Z}$ を満たす唯一の正整数でもある。
  • $q=-\dfrac1p$ とおく。問題は $a_n$ を $n\geqq1$ でのみ定義しているが,補助的に $a_0=p^0+q^0=2$ とし,$b_n=\dfrac{a_n}{2}$ $(n\geqq0)$ とおく($b_0=1$)。
  • $\mathcal{O}=\mathbb{Z}[\sqrt5]=\lbrace u+v\sqrt5\mid u,v\in\mathbb{Z}\rbrace$ とおく。$\mathcal{O}$ は加法と乗法について閉じている。$\sqrt5$ は無理数であるから $\xi\in\mathcal{O}$ の表示 $\xi=u+v\sqrt5$ は一意であり,共役 $\overline{\xi}=u-v\sqrt5$ とノルム $N(\xi)=\xi\overline{\xi}=u^2-5v^2\in\mathbb{Z}$ が定まる。$N$ は乗法的である。
  • $p^n=b_n+c_n\sqrt5$ $(b_n,c_n\in\mathbb{Z})$ と表す(整数性は 3.4 節 で示す)。共役をとれば $q^n=b_n-c_n\sqrt5$ であるから,この $b_n$ は上の $b_n=a_n/2$ と一致する。
  • $Q(x,y)=y^2-4xy-x^2$,$T=\begin{pmatrix}0&1\\1&4\end{pmatrix}$,$\eta_n=a_{n+1}-pa_n$ とおく。$v_2(k)$ は正整数 $k$ を割り切る $2$ の最大指数を表す。

1.2 共役数と対称式

有理化により
$$ 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$ の共役にするための設定である。

1.3 単模性と最大公約数の保存

(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 節 )。

1.4 二次の不変量

$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$ の判別式に等しい。

1.5 中心となる元 $\eta_n=a_{n+1}-pa_n$

補題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$ の積である。この一つの元の四つの側面が,四つの解法を生む。

  • 推移:$\eta_{n+1}=q\,\eta_n$。座標 $(x,y)\mapsto y-px$ のもとで $T$ は $q$ 倍写像に対応し,$\det T=N(q)=-1$ である( 5.4 節 )。$\to$ 本解
  • ノルム:$N(y-px)=(y-px)(y-qx)=Q(x,y)$ より $N(\eta_n)=Q(a_n,a_{n+1})=N(-2\sqrt5)\,N(q)^n=20\cdot(-1)^{n+1}$。$\to$ 別解1
  • 座標:$-2\sqrt5\,q^n=-2\sqrt5\,(b_n-c_n\sqrt5)=10c_n-2b_n\sqrt5$ と $\eta_n=(a_{n+1}-2a_n)-a_n\sqrt5$ を比べて,$a_n=2b_n$,$a_{n+1}-2a_n=10c_n$。$\to$ 参考解1
  • 整除:$d\mid a_n,a_{n+1}$ ならば $\mathcal{O}$ において $d\mid\eta_n$,$q$ が単数であるから $d\mid-2\sqrt5$。$\to$ 参考解2

1.6 整数性・正値性・偶数性

  1. の「自然数」は整数性と正値性の両方を要求する。$q < 0$ であるから $n$ が奇数のとき $a_n=p^n-\lvert q\rvert^n$ であり,正値性は自明ではない。非負係数の漸化式 (R) を用いれば両者は同時に得られる。
  2. は整数性だけからは決まらず,隣接二項の共通因子を制御する追加の構造を要する。その方法は次の四つに分類される。
  1. 保存:単模な漸化式で $\gcd$ を初期値まで下降させる(本解)。
  2. 二次の制限:$d^2\mid Q(a_n,a_{n+1})$(別解1)。
  3. 一次の制限:整数 $X,Y$ による $a_nX+a_{n+1}Y=\pm2$(Bézout 型等式)を構成する(参考解1)。
  4. 環での整除:$\mathcal{O}$ において $d\mid-2\sqrt5$(参考解2)。
    方法 1 は等式 $\gcd(a_n,a_{n+1})=\gcd(a_1,a_2)$ を直接与える。方法 2〜4 が与えるのは上界 $d\mid2$ であり,これに下界 $2\mid d$ を合わせて結論する。下界は全項の偶数性による:$a_0=2$,$a_1=4$ と (R) から,すべての $a_n$ は偶数である。
    偶数性を用いて $b_n=a_n/2$ に正規化すると
    $$ b_0=1,\qquad b_1=2,\qquad b_{n+2}=4b_{n+1}+b_n,\qquad \gcd(a_n,a_{n+1})=2\gcd(b_n,b_{n+1}) $$
    であり,(4) は $\gcd(b_n,b_{n+1})=1$ の証明に帰着する。互除法の終点が $b_0=1$ となり, 補題4 は $Q(b_n,b_{n+1})=5\cdot(-1)^{n+1}$ となる。

1.7 作問の設計

問題文と数値設定から読み取れる設計を整理する。

  • 共役の秘匿:第2項の底を $2-\sqrt5$ ではなく $-1/p$ と書くことで,共役であることを有理化によって発見させる。同時に,この表記は $pq=-1$($p$ が単数であること)を前面に出している。1.2 節のとおり,符号を落とすと奇数番目は無理数になる。
  • (2) の形式:漸化式そのものではなく積 $a_1a_n$ を問う。これは加法公式 $a_ia_j=a_{i+j}+(pq)^j a_{i-j}$ $(i\geqq j\geqq0)$ の $j=1$ の場合であり,移項すると末項係数 $-pq=1$ の漸化式 (R) になる。この係数が単数であることが (3)(4) の両方を支える。(2) は計算問題の体裁をとりつつ,後続二問の鍵を作らせる誘導である。
  • $n\geqq2$ の制限:問題は $a_0$ を定義しないため,(2) は $n\geqq2$ に限られ,(4) の下降の終点は $\gcd(a_2,a_1)$ となる。$a_0=2$ を補えば終点は $\gcd(a_1,a_0)$ であり,結論は同じである。
  • 答が $1$ でなく $2$ であること:$p+q=4$ が偶数であるため全項が偶数となり,「隣接項は互いに素」という早合点を排除する。一般に $pq=\pm1$ ならば隣接二項の $\gcd$ は $\gcd(2,\,p+q)$ である( 定理5 )。また $p=\varphi^3$($\varphi$ は黄金比)であって $a_n=L_{3n}$(Lucas 数)となり,$L_m$ が偶数であるのは $3\mid m$ のときに限られる( 5.7 節 )。本問の数列は,Lucas 数列から値が偶数である項(添字が $3$ の倍数の項)だけを抜き出したものとも読める。
  • 「自然数」:整数性に加えて正値性を問うことで,帰納法の命題設定(二項ずつ,正の整数)を正確に書かせる。
  • 段階構造:(1) 計算,(2) 構造の抽出,(3) 帰納法,(4) 互除法という標準的な誘導の背後に,(4) には不変量・Bézout 等式・環での整除という複数の深い解法が控えている。隣接二項に限定することで,任意の二項の $\gcd$( 定理6 )を要する一般論を避けている。

1.8 構造から導かれる解法の分岐

着目する構造数学的翻訳対応する解法
$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

2. 本解:漸化式とユークリッドの互除法

2.1 方針

$-1/p$ を有理化して共役 $q=2-\sqrt5$ を見出し,和と積から (2) を得る。(2) を漸化式 (R) に読み替え,(3) は二項ずつの数学的帰納法で,(4) は 補題3 により最大公約数を初期値まで下降させて処理する。

2.2 解答

(1)

$$ a_1=4,\qquad a_2=18 . $$
($q=-1/p=2-\sqrt5$ として $a_1=p+q=4$,$a_2=(p+q)^2-2pq=18$。)

(2)

$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}. $$

(3)

(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$ は自然数である。

(4)

  1. より,$n\geqq1$ に対して $g_n=\gcd(a_n,a_{n+1})$ が定まる。$n\geqq2$ のとき $a_{n+1}=4a_n+a_{n-1}$ であり,$d\mid a_n$ のもとで $d\mid 4a_n+a_{n-1}\iff d\mid a_{n-1}$ であるから( 補題3 ),$(a_n,a_{n+1})$ と $(a_{n-1},a_n)$ の公約数全体は一致する。よって
    $$ g_n=\gcd(a_n,\,4a_n+a_{n-1})=\gcd(a_{n-1},a_n)=g_{n-1}\qquad(n\geqq2), $$
    したがって $g_n=g_1=\gcd(4,18)=2$ である。
    $$ \gcd(a_{n+1},a_n)=2\qquad(n=1,2,3,\ldots). $$

2.3 検証

  • 直接計算:$a_3=p^3+q^3=(p+q)^3-3pq(p+q)=64+12=76=4\cdot18+4$,$a_4=4\cdot76+18=322$。$\gcd(76,18)=\gcd(322,76)=2$。
  • 符号:$pq=-1$ のため (2) は $a_{n+1}-a_{n-1}$,(R) は $+a_{n-1}$ となる。$n=2$ で $a_1a_2=72=a_3-a_1$。
  • $a_0$ による整合:$a_0=2$ を補えば (2) は $n=1$ でも成り立ち($16=18-2$),$\gcd(a_0,a_1)=\gcd(2,4)=2$ は下降の終点を一段延ばしても答が変わらないことを示す。
  • 法 $4$:(R) を法 $4$ で見ると $a_n\equiv2\ (n\ \text{偶数})$,$a_n\equiv0\ (n\ \text{奇数})$ であり,隣接二項が同時に $4$ で割り切れることはない。$\gcd$ の $2$ 成分がちょうど $2$ であることと整合する。
  • 大きさ:$\lvert q\rvert=\sqrt5-2 < \tfrac12$ より $a_n$ は $p^n$ に最も近い整数である。$p^3=38+17\sqrt5=76.01\ldots$ と整合する。

3. 別解と参考解

3.1 (3) の別証:二項定理による直接展開

着想・方針

$(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) からも帰納的に従う。

3.2 (2) の他の導出:特性方程式

着想・方針

積 $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)。

3.3 別解1:二次形式の不変量による平方の制限

着想・方針

公約数を初期値まで遡らせる代わりに,隣接二項の斉次二次式で値が一定となるものを用い,$d^2$ を一度に制限する。$Q(x,y)=(y-px)(y-qx)$ に隣接二項を代入すると,$p^n$ と $q^n$ の寄与が互いに打ち消し合い,$(pq)^n$ だけが残る。

解答

(1)(2)

本解と同じである。

(3)

3.1 節 により $a_n$ は正の偶数である。

(4)

$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$ が平方因子をもたないことが互いに素性を直接与える。

検証・検算

  • $Q(a_1,a_2)=18^2-4\cdot4\cdot18-4^2=20$,$Q(a_2,a_3)=76^2-4\cdot18\cdot76-18^2=-20$。符号だけが交代する。正規化版では $Q(b_0,b_1)=Q(1,2)=-5$。
  • 要点は $d\mid C$ ではなく $d^2\mid C$ が得られることにある。Cassini 型の恒等式 $a_{n+1}a_{n-1}-a_n^2=20\cdot(-1)^{n-1}$ は $a_{n-1}=a_{n+1}-4a_n$ を代入すれば同じ式になるが,$a_{n-1}$ を含むため $d\mid20$ しか得られない( 3.8 節 )。
  • $d^2\mid20$ は $d\in\lbrace1,2\rbrace$ までしか決めない。下界 $2\mid d$ は偶数性から別に得る必要がある。
  • 本解法の (4) は (2) の結果を用いていない。$Q$ の値は $p,q$ の和・積と判別式 $(p-q)^2$ だけで決まる。

3.4 参考解1:Pell 型ノルムと Bézout 等式

着想・方針

$p^n$ を整数座標 $(b_n,c_n)$ で表すと,$pq=-1$ はノルムの等式 $b_n^2-5c_n^2=(-1)^n$ に翻訳される。隣接する二つの座標ベクトルの行列式がこのノルムに等しいことから,$a_n,a_{n+1}$ の整数係数一次結合で $\pm2$ を表す等式が得られる。

解答

(3)

$$ 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$ である。

(4)

$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$。

検証・検算

  • $(b_1,c_1)=(2,1)$,$(b_2,c_2)=(9,4)$ より $a_1c_2-a_2c_1=16-18=-2=2\cdot(-1)^1$。
  • 1.5 節 より $c_n=\dfrac{a_{n+1}-2a_n}{10}$ である($c_1=\frac{18-8}{10}=1$)。これを (D) に代入すると,(D) は Cassini 型恒等式 $a_na_{n+2}-a_{n+1}^2=20\cdot(-1)^n$ を $10$ で割ったものに一致する。Cassini 型恒等式だけでは $d\mid20$ しか得られないが,合同式 $a_{n+1}\equiv2a_n\pmod{10}$($c_n$ の整数性)により $10$ で割れることが,候補 $4,5,10,20$ を一度に排除している。
  • (N) だけからは $\gcd(b_n,c_n)=1$ しか従わない。$\gcd(b_n,b_{n+1})=1$ を得るには隣接二組を結ぶ行列式 (D) が必要である。座標変換 $(b_n,c_n)\mapsto(b_n,b_{n+1})$ の行列式は $5$ であり,ここに候補 $5$ の起源がある( 5.3 節 )。

3.5 参考解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)〜(3)

(1)(2) は本解と同じであり,(3) と全項の偶数性は 3.1 節 による。

(4)

$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$。

検証・検算

  • $n=1$:$a_2-pa_1=18-4(2+\sqrt5)=10-4\sqrt5$,$(q-p)q=-2\sqrt5\,(2-\sqrt5)=10-4\sqrt5$。一致する。
  • 本解法は $\gcd$ に限らず,任意の公約数が $2$ を割り切ることを直接示す。
  • 逆元を掛ける操作は,逆元が $\mathcal{O}$ に属する単数 $q$ に対してのみ行っている。$q^{-1}=-p$($+p$ ではない)である。

3.6 参考解3:代数的整数のトレース

着想・方針

$a_n$ を,二次体 $K=\mathbb{Q}(\sqrt5)$ における $p^n$ のトレース(共役との和)とみる。整数性は「代数的整数のトレースは有理整数である」という一般定理から従う。高校数学の範囲外であり,(3) の構造的な説明として位置づける。

解答

(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) を与えない。

3.7 参考解4:非負整数行列と閉歩道の数え上げ

着想・方針

$p,q$ を固有値にもつ非負整数行列を構成し,$a_n$ をその冪のトレース,すなわち有向グラフの閉歩道の個数として解釈する。

解答

(3)

$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 . $$

検証・検算

  • $n=2$:頂点 $1$ のループを2回たどる閉歩道 $16$ 個と,$1\to2\to1$,$2\to1\to2$ の計 $18=a_2$ 個。
  • 整数行列のトレースは一般には正とは限らない。ここでは成分の非負性と閉歩道の存在を用いている。
  • 下界 $a_n\geqq4^n$ は $a_n\approx p^n$($p\approx4.236$)と整合する。

3.8 同じ系列に属する変形

以下は,上記のいずれかと発想の核を共有するか,(3)(4) の独立した決定原理を与えないため,独立の解法として数えない。

本解の系列(単模変換による保存)

  • 行列表示と法 $d$ での可逆性:$(b_n,b_{n+1})^{\top}=T^n(1,2)^{\top}$ であり,$T^{-1}$ は整数行列である。$d\mid b_n,b_{n+1}$ ならば法 $d$ で $T^n(1,2)^{\top}\equiv0$,両辺に $T^{-n}$ を作用させて $(1,2)^{\top}\equiv0$,すなわち $d\mid1$。逐次の下降を一度の可逆性に置き換えた表現である。
  • 正規化:$b_0=1$ を終点にとれば $\gcd(b_n,b_{n+1})=\gcd(b_0,b_1)=1$ となり,終点の計算が自明になる。
  • 連分数・一次分数変換:$\dfrac{b_{n+1}}{b_n}=4+\dfrac{1}{b_n/b_{n-1}}$ により $\dfrac{b_{n+1}}{b_n}$ は有限単純連分数で表され,分数 $\dfrac{x}{y}\mapsto\dfrac{4x+y}{x}$ は既約性を保つ。これはユークリッドの互除法の記録そのものである( 5.8 節 )。
  • 漸化式の他の導出:Newton の公式,Cayley–Hamilton の定理,母関数はいずれも (R) を与えるにとどまる。

別解1 の系列(二次の不変量)

  • Cassini 型恒等式と法 $5$:$b_{n+1}b_{n-1}-b_n^2=5\cdot(-1)^{n-1}$ $(n\geqq1)$ より,$d=\gcd(b_n,b_{n+1})$ は $d\mid5$ を満たす。(E) より $b_n\equiv2^n\not\equiv0\pmod5$ であるから $d=1$。正しい証明であるが,同じ量を $(b_n,b_{n+1})$ の二次形式として読めば $d^2\mid5$ となり,法 $5$ の計算は不要である。
  • 判別式による素因数の制限:素数 $r$ が $a_n,a_{n+1}$ を割り切れば $r\mid Q(a_n,a_{n+1})=\pm20$,すなわち $r\in\lbrace2,5\rbrace$。$r=5$ の排除には追加の議論を要する( 5.5 節 )。
  • 二次形式の発見法:$Q(x,y)=Ax^2+Bxy+Cy^2$ に $Q(y,4y+x)=-Q(x,y)$ を課して係数を比較すると $C=-A$,$B=4A$ を得る。不変形式は定数倍を除き一意に $Q$ に定まる。

参考解1 の系列(ノルムと整数座標)

  • ノルムと合同式による仕上げ:(N) より $\gcd(b_n,c_n)=1$ であるから,$\gcd(b_{n+1},b_n)=\gcd(2b_n+5c_n,\,b_n)=\gcd(5c_n,\,b_n)=\gcd(5,\,b_n)$。(N) より $b_n^2\equiv\pm1\pmod5$ であるから $5\nmid b_n$,ゆえに $\gcd(b_n,b_{n+1})=1$。
  • 格子の面積:(D) は,隣接する整数ベクトル $(b_n,c_n),(b_{n+1},c_{n+1})$ が張る平行四辺形の面積が $1$ であることの言い換えである( 5.3 節 )。

参考解2 の系列(乗法的消去)

  • 単数比と法 $d\mathcal{O}$ の合同式:$r=q/p=-q^2$ は $\mathcal{O}$ の単数であり,$a_n=p^n(1+r^n)$。$d\mid a_n,a_{n+1}$ ならば,$p^{-1}\in\mathcal{O}$ より $r^n\equiv r^{n+1}\equiv-1\pmod{d\mathcal{O}}$。第1式に $r$ を掛けて第2式と比べると $r\equiv1$,これを第1式に戻して $1\equiv-1$,すなわち $2\in d\mathcal{O}$。係数比較により $d\mid2$。
  • 多項式の Bézout 等式と結果式:$E_n(X)=1+X+\cdots+X^{n-1}$ とおくと $(1-X)E_n(X)=1-X^n$ より
    $$ 2=\bigl(1-XE_n(X)\bigr)(1+X^n)+E_n(X)\,(1+X^{n+1}). $$
    $X=r$ を代入すると $2\in a_n\mathcal{O}+a_{n+1}\mathcal{O}$ となり,$d\mid2$ が従う。この $2$ は結果式 $\operatorname{Res}_X(1+X^n,1+X^{n+1})$ に等しい( 5.5 節 )。

決定原理とならない表示

  • Lucas 数への読み替え:$a_n=L_{3n}$( 5.7 節 )。整数性は Lucas 数の整数性に帰着するが,それは同じ漸化式による。
  • 双曲線関数:$t=\log p$ とおくと $a_{2k}=2\cosh 2kt$,$a_{2k+1}=2\sinh(2k+1)t$。増大度と正値性を説明するが,整数性も共通因子も制御しない。
  • 法 $4$ の計算のみ:隣接二項が同時に $4$ の倍数でないことは $\gcd$ の $2$ 成分を決めるだけで,奇素因数を排除しない。
  • 解析的方法:極限,単調性,凸性などは数列の大きさを記述するが,共通素因数を制限しない。

3.9 解法の比較

解法対象核となる構造公約数 $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) を与えない。

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$ とする。

4.1 意思決定の流れ

  1. 底の関係を調べる:無理数とその逆数・符号付き逆数が並べば,有理化して共役か否かを確かめる。和 $s$ と積 $\varepsilon$ が整数かを確認する。
  2. 漸化式を作る:$V_{n+2}=sV_{n+1}-\varepsilon V_n$,$V_0=2$,$V_1=s$。設問が積や和の形で問うていても,この形に読み替える。
  3. 整数性と正値性を分けて確認する:整数性は初期値と係数の整数性から,正値性は係数の符号,または($\alpha,\beta$ が実数のとき)$\alpha > \lvert\beta\rvert$ の評価から得る。
  4. 末項係数を見る:$\varepsilon=\pm1$ ならば 補題3 により $\gcd(V_n,V_{n+1})=\gcd(V_0,V_1)=\gcd(2,s)$。これが第一選択である。
  5. 不変量を作る:$Q(x,y)=(y-\alpha x)(y-\beta x)$ とおくと $Q(V_n,V_{n+1})=-\Delta\,\varepsilon^n$。ゆえに $\gcd(V_n,V_{n+1})^2\mid\Delta\,\varepsilon^n$。下降が使えないとき,あるいは一つの式で決着させたいときに用いる。
  6. Bézout 型等式または環での整除を作る:整数座標の行列式,あるいは $V_{n+1}-\alpha V_n=(\beta-\alpha)\beta^n$ と $\beta$ の可逆性から,公約数が割り切るべき小さな数を作る。
  7. 残った素因数を合同式で排除する:上界に候補素数 $r$ が残れば,法 $r$ で数列を調べる。ただし $d^2$ の制限で候補が消える場合は不要である。
  8. 上界と下界を合わせる:(5)〜(7) は上界を与える。下界(全項の偶数性など)を別に示し,等号を確定する。
  9. 検算する:初めの数項の直接計算,符号の確認($pq$ の符号と漸化式の符号),不変量の値の交代,法 $2$・法 $4$ での周期を確かめる。

4.2 症状と有効な表現

症状検討する表現・道具本問での対応
無理数とその符号付き逆数が並ぶ有理化して共役か確認$-1/p=2-\sqrt5$
二数の和と積が整数整数係数の三項間漸化式 補題2
漸化式の末項係数が $\pm1$互除法,単模行列本解
末項係数が $\pm1$ でない不変量,Bézout 型等式,合同式 5.6 節 の例
隣接二項の二次式の値が一定$d^2\mid C$別解1
二次無理数の冪整数座標とノルム参考解1
冪の差に単数が掛かっている環における整除参考解2
上界に候補素数が残るその素数を法とする計算 3.8 節
冪和の整数性だけが問われる二項展開,トレース,行列3.1 節,参考解3・4

4.3 誤りやすい推論

  • $q=-1/p=2-\sqrt5$ であり,$1/p=\sqrt5-2$ とは符号が異なる。$pq=-1$ であって $pq=1$ ではない。
    1. の答は $a_{n+1}-a_{n-1}$,漸化式は $a_{n+1}=4a_n+a_{n-1}$ である。両者の符号を混同しない。
    1. で整数性のみを示し,正値性を落とす。
    1. を「隣接項は互いに素」と早合点する。全項が偶数である。
  • 斉次二次式から得られるのは $d^2\mid C$ であり,一次の恒等式(Cassini 型など)から得られる $d\mid C$ より強い。両者を区別する。
  • 法 $4$ の情報だけで奇素因数を排除したとする。
  • 環 $\mathcal{O}$ で逆元を掛けてよいのは単数に限る。剰余環 $\mathcal{O}/d\mathcal{O}$ は一般に零因子をもつ(例えば $\mathcal{O}/5\mathcal{O}$ では $\sqrt5\neq0$ だが $(\sqrt5)^2=0$)。
  • 末項係数が $\pm1$ でない漸化式に $\gcd$ の下降を無条件に適用する。

4.4 類題設計への応用

本問の構造は類題の設計原理としても読める。

  • 底を $k+\sqrt{k^2+1}$ $(k\in\mathbb{Z}_{>0})$ に替えると,$s=2k$,$\varepsilon=-1$ であり,(2)〜(4) は同型で答は常に $2$ となる( 定理5 )。
  • $s$ を奇数にとる(例えば底を $\varphi=\frac{1+\sqrt5}{2}$ とし,Lucas 数 $L_n$ を扱う)と,答は $1$ になる。
  • 積を単数でなくする(例えば $2\pm\sqrt2$,$\varepsilon=2$)と互除法による保存は破れ,隣接二項の $\gcd$ は $n$ とともに増大する。「$\gcd$ が有界でないことを示せ」という設問が作れる。
  • 隣接しない二項 $\gcd(a_m,a_n)$ を問えば,添字に対する互除法( 定理6 )が主題となる。

5. 発展事項

各節で,高校数学の範囲で完結する内容(高校数学の範囲)と,それを超える一般論(発展)とを区別して記す。

5.1 高校数学と一般理論の境界

主題高校数学の範囲一般理論
$\gcd$ の保存互除法, 補題3 $\mathrm{GL}_2(\mathbb{Z})$ の作用と原始ベクトル
二次の不変量$d^2\mid Q(x,y)$二元二次形式,判別式,ノルム形式
共役とノルム有理化,$(u+v\sqrt5)(u-v\sqrt5)$二次体,整環,単数群,Pell 方程式
環での整除$\sqrt5$ の無理数性による係数比較イデアル,剰余環,冪零元,結果式
整数性帰納法,二項定理代数的整数のトレース
数え上げなし隣接行列,閉軌道,ゼータ関数
特殊な数列漸化式の計算Lucas 列の整除性

5.2 二次体・整環・単数・Pell 方程式

高校数学の範囲

 有理化と $(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$ に関する問題として読み直せる。

5.3 整数格子と $\mathrm{GL}_2(\mathbb{Z})$

高校数学の範囲

  補題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$ の制限が必要になる。

5.4 二元二次形式とノルム形式

高校数学の範囲

  補題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)$ は原始的である。

5.5 判別式・冪零元・結果式

高校数学の範囲

 参考解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 と整合する。

5.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$ は本質ではない。

5.7 Lucas 列と任意の二項の最大公約数

高校数学の範囲

 本問は隣接二項に限られ,互除法の一段の下降で済む。
発展 $\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 数の整除性に関する古典的な結果の特殊化に当たる。

5.8 連分数

高校数学の範囲

 互除法の各段の商を記録すれば連分数が得られる。
発展 $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$ の近似分数から得られるという古典的事実の一例である。

5.9 母関数・ゼータ関数・Pisot 数

高校数学の範囲

 三項間漸化式と $\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$ はわずかに整数より大きく,偶数なら小さい)。これらの表示は大きさを精密に記述するが,最大公約数の決定原理は与えない。

5.10 歴史的背景

ユークリッドの互除法は『原論』第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)が体系的に研究した。

6. 最終整理

6.1 構造マップ

$$ \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} $$

6.2 解答一覧

設問結論根拠
(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)$ に帰着

6.3 数学的教訓

  • 無理数とその符号付き逆数が並べば,有理化して共役か否かを確かめる。本問では $-1/p$ の符号が,第2項を共役にし整数性を成立させる。
  • 二数の和と積が整数ならば冪和は整数係数の漸化式を満たす。末項係数が $\pm1$(単模)ならば,隣接二項の最大公約数は保存され,初期値 $\gcd(V_0,V_1)=\gcd(2,s)$ に帰着する。
  • 一次結合は公約数 $d$ を,斉次二次式は $d^2$ を制限する。二次の不変量の値が平方因子の少ない整数であれば,強い結論が一度に得られる。
  • 最大公約数の決定は,上界($d\mid2$)と下界($2\mid d$)の二つに分けて考えられる。偶数性という下界を落とすと「互いに素」と誤る。
  • 本解・別解1・参考解1・参考解2は,一つの元 $\eta_n=a_{n+1}-pa_n=-2\sqrt5\,q^n$ の推移・ノルム・座標・整除という四つの側面に対応し,その共通の源は $N(q)=-1$ である。
  • 平方は情報を失う。$(p-q)^2=20$ から生じる候補 $5$ は,$\mathcal{O}/5\mathcal{O}$ の冪零元による見かけのものであり,平方前の $p-q=2\sqrt5$ を扱えば現れない。
  • 整数性と正値性は別の性質であり,「自然数」の証明には両方が要る。
  • 行列,連分数,Cassini 型恒等式,結果式などの多様な表示は,保存・二次の制限・一次の制限・環での整除のいずれかに帰着する。解法の数と原理の数とを区別する。
  • 隣接冪和の共通因子を有界に保つ本質は $\alpha\beta=\pm1$ であり,$\sqrt5$ や係数 $4$ は本質ではない。
投稿日:12日前
数学の力で現場を変える アルゴリズムエンジニア募集 - Mathlog served by OptHub

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

医学部・難関大受験生の指導を行っています。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中