$q=1+\sqrt{2}$とする.1以上の整数$n$に対して
$$a_n=\frac{1}{2\sqrt{2}}\left\{q^n-\left(-\frac{1}{q}\right)^n\right\}$$
と定める.また,$p=2^{16}+1$とする.
出典：作問サークル 2018年ビラ問題
この記事では,この問題の別解法について書きたいと思います.
$-\frac{1}{q}=-\frac{1}{1+\sqrt{2}}=1-\sqrt{2}$より,
$$a_n=\frac{1}{2\sqrt{2}}\left\{(1+\sqrt{2})^n-(1-\sqrt{2})^n\right\}$$
である.ここで,$1\pm\sqrt{2}$は$x^2-2x-1=0$の解なので,
$$a_{n+2}=2a_{n+1}+a_n$$
である.
ここで,$\mathbb{F}_p$を位数$p$の有限体とする.
このとき,$x^2-2$は$\mathbb{F}_p[x]$とみたときに可約である.
具体的には,$x^2-2=(x-4080)(x-61457)$である.ここで,$c=4080\in\mathbb{F}_p$とおく.このとき,
$$a_n\equiv\frac{1}{2c}\left\{(1+c)^n-(1-c)^n\right\}\pmod{p}$$
と書くことができる.
ここで,$a_1=1,a_2=2$である.
ここで,$1+c,1-c$は$p$と互いに素であるような整数であるため,フェルマーの小定理により,$p-1$の周期を持つ.よって$a_{n+p-1}\equiv a_{n}\pmod{p}$となる.
よって$a_p\equiv a_1\equiv 1,a_{p+1}\equiv a_2\equiv 2$となる.
以上の議論が何故成り立つのかと言うと,$2$が$\mod p$において平方剰余だからである.$p\mod 8=1,7$ならば$2$が平方剰余となる.$2^{16}+1\mod 8=1$である.
もし$2$が平方剰余とならないような$p$の場合どうなるかというと,$c\in\mathbb{F}_{p^2}\setminus \mathbb{F}_p$となる.
$\mathbb{F}_{p^2}$の元$x$は$x^{p^2}=x$を満たすことから,$a_{n+p^2-1}\equiv a_n\pmod{p}$が成立することがわかる.
また,この手法は一般の$k$項間漸化式に応用することができる.
例えば,フィボナッチ数列の$\mod p$での周期($p$は素数,$p\neq 2,5$)は,
となる.