1

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

295
0
$$$$

問題

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

  1. $a_{n+2}$$a_{n+1},a_n$を使って表せ.
  2. $a_p,a_{p+1}$$p$で割った余りを求めよ.なお,$p$が素数であることは用いてよい.
  3. すべての$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}}\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$)は,

  • $\left(\frac{5}{p}\right)=1$のとき 周期は$p-1$の約数
  • $\left(\frac{5}{p}\right)=-1$のとき 周期は$p^2-1$の約数

となる.

投稿日:2021319

この記事を高評価した人

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

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

バッジはありません。

投稿者

コメント

他の人のコメント

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