作問サークル　NFビラ問題　2018年

322

問題

$q = 1 + \sqrt{2}$ とする.1以上の整数 $n$ に対して
$a_{n} = \frac{1}{2 \sqrt{2}} {q^{n} - {(- \frac{1}{q})}^{n}}$
と定める.また, $p = 2^{16} + 1$ とする.

$a_{n + 2}$ を $a_{n + 1}, a_{n}$ を使って表せ.
$a_{p}, a_{p + 1}$ を $p$ で割った余りを求めよ.なお, $p$ が素数であることは用いてよい.
すべての $n \geq 1$ に対して $a_{n + p - 1} - a_{n}$ は $p$ の倍数であることを証明せよ.

出典：作問サークル　2018年ビラ問題
この記事では,この問題の別解法について書きたいと思います.

解答

$- \frac{1}{q} = - \frac{1}{1 + \sqrt{2}} = 1 - \sqrt{2}$ より,
$a_{n} = \frac{1}{2 \sqrt{2}} {(1 + \sqrt{2})^{n} - (1 - \sqrt{2})^{n}}$
である.ここで, $1 \pm \sqrt{2}$ は $x^{2} - 2 x - 1 = 0$ の解なので,
$a_{n + 2} = 2 a_{n + 1} + a_{n}$
である.

ここで, $F_{p}$ を位数 $p$ の有限体とする.
このとき, $x^{2} - 2$ は $F_{p} [x]$ とみたときに可約である.
具体的には, $x^{2} - 2 = (x - 4080) (x - 61457)$ である.ここで, $c = 4080 \in F_{p}$ とおく.このとき,

$a_{n} \equiv \frac{1}{2 c} {(1 + c)^{n} - (1 - c)^{n}} (\mod p)$
と書くことができる.
ここで, $a_{1} = 1, a_{2} = 2$ である.
ここで, $1 + c, 1 - c$ は $p$ と互いに素であるような整数であるため,フェルマーの小定理により, $p - 1$ の周期を持つ.よって $a_{n + p - 1} \equiv a_{n} (\mod 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 F_{p^{2}} ∖ F_{p}$ となる.
$F_{p^{2}}$ の元 $x$ は $x^{p^{2}} = x$ を満たすことから, $a_{n + p^{2} - 1} \equiv a_{n} (\mod p)$ が成立することがわかる.