NF杯2023(N) - 行列を使って周期を求める方法

（公式解説の補足）

周期を特性方程式の解$\alpha,\beta$の位数で表す部分は，有限体上の行列を考えると楽である．

以下，$x$を$\mathbb{F_p}$の元とし，$y$を$\mathbb{F_p^\times}$の元とする． $\mathbb{F_p}$上の行列$A_n$および$B$を $$A_n=\begin{pmatrix}a_{n+2}&a_{n+1}\\ a_{n+1}&a_n\end{pmatrix},\quad B=\begin{pmatrix}x&y\\ 1&0\end{pmatrix}$$ により定めると，$a_n$の初期値及び漸化式は次のように言い換えられる： $$A_0=\begin{pmatrix}x&1\\ 1&0\end{pmatrix},\quad A_{n+1}=BA_n.$$ $A_0,B$は正則行列なので$A_n$は常に正則行列である． 数列$a_n$のmod $p$での周期は，任意の$n$に対して$B^kA_n=A_n$が成り立つような最小の正整数$k$に等しい． $A_n$は正則なのでこれは$B$の$\mathrm{GL_2}(\mathbb{F_p})$における位数に等しいことがわかる．

$B$の固有方程式$t^2-xt-y=0$（これは数列$a_n$の特性方程式でもある）の解を$\alpha,\beta$とする．$y\in \mathbb{F_p^\times}$より$\alpha,\beta\in \mathbb{F_{p^2}^\times}$である．

• $\alpha,\beta\in \mathbb{F_p^\times}$の場合：$\alpha\neq \beta$ならば$B$は $$\begin{pmatrix}\alpha&0\\ 0&\beta\end{pmatrix}$$ と対角化されるため，その位数は$\mathrm{lcm}(\mathrm{ord}(\alpha),\mathrm{ord}(\beta))$に等しい．$\alpha=\beta$の場合，$B$はスカラー行列ではないことに注意すると，$B$のJordan標準形は $$\begin{pmatrix}\alpha&1\\ 0&\alpha\end{pmatrix}$$ となり，その位数は$p\cdot \mathrm{ord}(\alpha)$である．

• $\alpha,\beta\in \mathbb{F_{p^2}^\times} \setminus\mathbb{F_p^\times}$の場合，$\alpha$と$\beta$は$\mathbb{F_p}$上共役である．$\alpha\neq \beta$なので$B$は以下のように対角化される： $$\begin{pmatrix}\alpha&0\\ 0&\beta\end{pmatrix}.$$ よって$B$の位数は$\mathrm{lcm}(\mathrm{ord}(\alpha),\mathrm{ord}(\beta))=\mathrm{ord}(\alpha)$である．