東大数理院試2009年度専門問3解答
東大数理の院試（2009年度専門問3）の解答です．
自分が作った解答は
ここ
に置いてあり，代数の問題も数問解いてpdfにまとめてはあります．でもまだ公開するつもりはないので，ここで個別に書いておくことにします．
整数$\lambda, \mu$に対して，連立漸化式
$$
\left\{
\begin{aligned}
&a_{n + 1} = \lambda a_n + b_n \\
&b_{n + 1} = a_n + \mu b_n \\
&a_1 = 0, b_1 = 1
\end{aligned}
\right. \qquad
n = 1, 2, \dots
$$
を考える．$2$ではない素数$p$を固定し，$(\lambda - \mu)^2 + 4$は$p$で割り切れないと仮定する．
(1) 全ての正の整数$n$に対して
$$
p \mid a_{n + p^2 - 1} - a_n
\quad \text{かつ} \quad
p \mid b_{n + p^2 - 1} - b_n
$$
が成り立つことを示せ．
(2) $\lambda = 2, \mu = 1$とする．全ての正の整数$n$に対して
$$
p \mid a_{n + p - 1} - a_n
\quad \text{かつ} \quad
p \mid b_{n + p - 1} - b_n
$$
が成り立つような$13$以下の奇素数$p$を全て求めよ．
(1)
自然な射影$\ZZ \to \ZZ / p\ZZ = \FF_p$による$a_n, b_n$の像をそれぞれ$c_n, d_n$とし，以下$\FF_p$の代数閉包$\overline{\FF_p}$上で考える．
$c_{n + p^2 - 1} = c_n, d_{n + p^2 - 1} = d_n$を示せば良い．
$A =
\begin{pmatrix}
\lambda & 1 \\
1 & \mu
\end{pmatrix}
\in M_2(\FF_p)$とおくと
$$
\begin{pmatrix}
c_{n + k} \\ d_{n + k}
\end{pmatrix}
= A
\begin{pmatrix}
c_{n + k - 1} \\ d_{n + k - 1}
\end{pmatrix}
= \cdots = A^k
\begin{pmatrix}
c_n \\ d_n
\end{pmatrix}
\tag{$\ast$}
$$
である．$A$の固有多項式は$t^2 - (\lambda + \mu)t + \lambda \mu - 1$で判別式は$D = (\lambda - \mu)^2 + 4 \not= 0$だから，$A$は相異なる固有値を持つ．よって$A$の Jordan 標準形は対角行列である．また固有値は$\FF_{p^2}$の元だから$A^{p^2} = A.$
$\bullet$ $\lambda \mu \not= 1$の時：
$A$は正則だから$A^{p^2 - 1} = I.$よって$(\ast)$より$c_{n + p^2 - 1} = c_n, d_{n + p^2 - 1} = d_n$となる．
$\bullet$ $\lambda = \mu = 1$の時：
帰納的に$a_n = b_n = 2^{n - 2} \, (n \geq 2)$である．$p \not= 2$だから，$n \geq 2$に対し
$c_{n + p^2 - 1} = 2^{n - 2} \cdot (2^{p - 1})^{p + 1} = 2^{n - 2} = c_n$
となる．$d_n$も同様．
$\bullet$ $\lambda = \mu = -1$の時：
帰納的に $a_n = (-1)^n 2^{n - 2}, b_n = (-1)^{n + 1} 2^{n - 2} \, (n \geq 2)$となる．$p^2 - 1$が偶数であることに注意すると，$\lambda = \mu = 1$の時と同様に$n \geq 2$に対し$c_{n + p^2 - 1} = c_n, d_{n + p^2 - 1} = d_n$となる．
(2)
$\lambda \mu \not= 1$だから，条件を満たすことは$A^p = A,$すなわち$A$の全ての固有値が$\FF_p$の元であることと同値．これは$D = 5$が$\bmod p$の平方剰余であることと同値．仮定から$p \not= 5$である．また明らかに$p \not= 3.$$p > 5$の時は Euler の規準と平方剰余の相互法則より
$$
\bigg( \frac{5}{p} \bigg)
= (-1)^{\frac{5 - 1}{2} \frac{p - 1}{2}} \bigg( \frac{p}{5} \bigg)
= \bigg( \frac{p}{5} \bigg)
\equiv p^{(5 - 1) / 2}
= p^2 \pmod 5
$$
だから，これが$1$となるのは$p \equiv \pm 1 \bmod 5$の時．よって答えは$p = 11$のみ．
$\lambda = \mu = \pm 1$の時は$a_{p^2} - a_1$は$2$のべき乗なので$p$で割り切れない．
これ以前にも以下の類題が出題されており，そこでもパラメータによっては$n = 1$で成り立たない．
誤植だと思うが，似た問題のほぼ同じ箇所に誤植があるとも考えにくいので，自分が間違えてるかもしれない．
整数$\lambda, \mu$に対し数列$\{ a_n\}$を帰納的に
$$
\left\{
\begin{aligned}
&a_1 = 1, a_2 = 1, \\
&a_{n + 2} = \lambda a_{n + 1} + \mu a_n
\end{aligned}
\right.
$$
と定める．
(1)素数$p$が$\lambda^2 + 4\mu$の約数でないとき，任意の整数$n \geq 1$に対し$p$は$a_{n + p^2 - 1} - a_n$の約数であることを示せ．
(2)$\lambda = 2, \mu = -4$とする．$5$以上の素数$p$が，任意の整数$n \geq 1$に対し$a_{n + p - 1} - a_n$の約数であるための必要十分条件を求めよ．（$p$ に対する合同式で表わせ．）
$$
\begin{pmatrix}
a_{n + 2} \\ a_{n + 1}
\end{pmatrix}
=
\begin{pmatrix}
\lambda & \mu \\
1 & 0
\end{pmatrix}
\begin{pmatrix}
a_{n + 1} \\ a_n
\end{pmatrix}
$$
だから，上と同様にできる．（$A$が正則にならない$\mu = 0$の時は$n = 1$で成り立たない．）
(2)の答えは$p \equiv 1 \bmod 3.$
