NF杯2023(N)

　特性方程式は $$t^2-xt-y=0$$ である．$x,y$ を固定したとき，これの解を $\alpha,\beta$ とすると，以下が成り立つ： $$a_n=\begin{cases} \dfrac{\beta^n-\alpha^n}{\beta-\alpha} & (\alpha\neq \beta) \\ n\alpha^{n-1} & (\alpha=\beta) \end{cases}$$ 　以下，特性方程式を $\mathbb{F}_p$ 係数として考え，以下の三つのパターンに場合分けして考える．ただし，$\mathbb{F}_p$ は位数 $p$ の有限体である．

• (1) $\alpha=\beta$であるような場合 $(p-1)$通り
• (2) $\alpha\neq \beta$かつ解が$\mathbb{F}_p$上に存在する場合 $\dfrac{(p-1)(p-2)}{2}$通り
• (3) 解 $\alpha,\beta$ が $\mathbb{F}_p$ 上に存在しない場合．このとき解は$\mathbb{F}_{p^2}\setminus \mathbb{F}_p$の元である．$\dfrac{p(p-1)}{2}$通り

(1)について

このとき,一般項は $$a_n=n\alpha^{n-1}$$ である.そして, $k$を周期としたとき $$n\alpha^{n-1}\equiv (n+k)\alpha^{n+k-1}$$ 十分大きな整数$m$について,$n=mp$としたときに等号が成立する.

$$\begin{aligned} mp\alpha^{mp-1}&\equiv (mp+k)\alpha^{mp+k-1}\\ 0&\equiv k\alpha^{mp+k-1}\\ \end{aligned}$$

よって,$k$が$p$の倍数であることが必要である.さらに,$n=mp+1$の場合について考察すると $$\begin{aligned} (mp+1)\alpha^{mp}&\equiv (mp+1+k)\alpha^{mp+k}\\ \alpha^{mp}&\equiv \alpha^{mp+k}\\ \end{aligned}$$ よって,$\alpha^k=1$であることが必要である.

よって,周期となるためには,$p$と$\alpha$の位数で両方割り切れることが必要である.逆にこの場合$a_{n+k}\equiv a_n \forall n\in\mathbb{N}$なので周期としての条件を満たしている.よって,$f(x,y)$は$p$と${\rm ord}(\alpha)$の最小公倍数である.

ここで,$\alpha$の位数は$p-1$の約数となる.これは$p$とは互いに素なので$f(x,y)=p\cdot {\rm ord}(\alpha)$である.さらに,$\mathbb{F}_p$の乗法群は$\mathbb{Z}/(p-1)\mathbb{Z}$に同型であることに気をつけると, 位数が$d$であるような$\alpha\in \mathbb{F}_p^{\times}$の個数はトーシェント関数を使って$\varphi(d)$と書ける. よって,(1)の範囲での総和は $$\sum_{d|(p-1)}dp\varphi(d)$$ である.

(2)について

このとき,一般項は

$$a_n=\dfrac{\beta^n-\alpha^n}{\beta-\alpha}$$

である.

さらに, $$(\alpha,\beta);1\leq \alpha\lt \beta\leq p-1$$ のペアがそれぞれ1つずつ登場するので,これらについての総和を求める.

周期が$k$だとした場合,ある整数$m$が存在して, $$a_{m(p-1)}\equiv a_{m(p-1)+k}\pmod{p}$$ であるため, $$\beta^{m(p-1)}-\alpha^{m(p-1)}=\beta^{m(p-1)+k}-\alpha^{m(p-1)+k}$$ である.ここで,フェルマーの小定理より, $$0=\beta^{k}-\alpha^{k}$$

さらに, $$a_{m(p-1)+1}\equiv a_{m(p-1)+k+1}\pmod{p}$$ であるため, $$\beta^{m(p-1)+1}-\alpha^{m(p-1)+1}=\beta^{m(p-1)+k+1}-\alpha^{m(p-1)+k+1}$$ であるが, $$\beta-\alpha=\beta^{k+1}-\alpha^{k+1}$$ が必要だが, $$\beta^{k+1}-\alpha^{k+1}=\beta^{k+1}-\alpha \cdot \beta^{k}=\beta^k (\beta-\alpha)$$ である.よって,$k$が周期であるためには $$\alpha^k\equiv \beta^k\equiv 1\pmod{p}$$ が必要である.逆にこのときに周期となる. よって, $$f(x,y)={\rm lcm}({\rm ord}(\alpha),{\rm ord}(\beta))$$

である. $1\leq \alpha,\beta\leq p-1$の範囲内での${\rm lcm}({\rm ord}(\alpha),{\rm ord}(\beta))$の総和は $$\sum_{d_1|(p-1)}\sum_{d_2|(p-1)}\varphi(d_1)\varphi(d_2){\rm lcm}(d_1,d_2)$$ である.さらに,$1\leq \alpha=\beta\leq p-1$の範囲内での${\rm lcm}({\rm ord}(\alpha),{\rm ord}(\beta))$の総和は $$\sum_{d|(p-1)}d\varphi(d)$$ である.

よって,(2)の場合の答えの総和は

$$\dfrac{1}{2}\sum_{d_1|(p-1)}\sum_{d_2|(p-1)}\varphi(d_1)\varphi(d_2){\rm lcm}(d_1,d_2)-\dfrac{1}{2}\sum_{d|(p-1)}d\varphi(d)$$ である.

(3)について

このときも(2)と同様に一般項は

$$a_n=\dfrac{\beta^n-\alpha^n}{\beta-\alpha}$$

である.ただし,$\alpha,\beta$は$\mathbb{F}_{p^2}\setminus \mathbb{F}_p$の範囲内を動く.ただし,$\alpha$と$\beta$を入れ替えているものは同一視しているため,該当の$(x,y)$の組み合わせは$\dfrac{p(p-1)}{2}$通りである.

(2)と同様にすると, $$f(x,y)={\rm lcm}({\rm ord}(\alpha),{\rm ord}(\beta))$$ だが,このときのordとは,$\mathbb{F}_{p^2}^{\times}$における位数である.

さらにこのとき,$\alpha,\beta$は$\mathbb{F}_{p^2}$の元の中で共役元の関係になっている.よって位数は等しい. つまり${\rm ord}(\alpha)={\rm ord}(\beta)$ということである.なので,結局周期の総和は $$\dfrac{1}{2}\sum_{\alpha\in\mathbb{F}_{p^2}\setminus\mathbb{F}_p}{\rm ord}(\alpha)$$ ここで,実は$\mathbb{F}_{p^2}^{\times}$は群$\mathbb{Z}/(p^2-1)\mathbb{Z}$に同型であることに注意. さらにこのとき,$\mathbb{Z}/(p^2-1)\mathbb{Z}$の元の中で$(p+1)$の倍数であるようなもの$(p-1)$個が$\mathbb{F}_p$の元に対応している. よって,(3)についての総和は

$$\dfrac{1}{2}\sum_{d|(p^2-1)}d\varphi(d)-\dfrac{1}{2}\sum_{d|(p-1)}d\varphi(d)$$

である.

結局合計すると,最終的な答えは

$$(p-1)\sum_{d|(p-1)}d\varphi(d) + \dfrac{1}{2}\sum_{d|(p^2-1)}d\varphi(d)+\dfrac{1}{2}\sum_{d_1|(p-1)}\sum_{d_2|(p-1)}\varphi(d_1)\varphi(d_2){\rm lcm}(d_1,d_2)$$

となる.この値を$p-1$や$p^2-1$の約数全てについて値を求めるのは人力では大変である.

便宜上以下のように関数$F(n),G(n)$を定める.

$$F(n):=\sum_{d|n} d\varphi(d); G(n):=\sum_{d_1|n}\sum_{d_2|n}\varphi(d_1)\varphi(d_2){\rm lcm}(d_1,d_2)$$

このとき,求めるべき答えは

$$(p-1)F(p-1) + \dfrac{1}{2}F(p^2-1)+\dfrac{1}{2}G(p-1)$$

つまり,$p=2017$であるため,

$$2016\cdot F(2016) + \dfrac{1}{2}F(2016\cdot 2018)+\dfrac{1}{2}G(2016)$$

実は$F(n),G(n)$は乗法的関数である.つまり,$n,m$が互いに素な正の整数とした場合,$F(nm)=F(n)F(m),G(nm)=G(n)G(m)$となるという性質がある.

この性質を使うことで,求めるべき答えは

$$2016\cdot F(2^5)F(3^2)F(7) + \dfrac{1}{2}F(2^6)F(3^2)F(7)F(1009)+\dfrac{1}{2}G(2^5)G(3^2)G(7)$$

であるとわかる.それぞれについて答えを求める.

$$\begin{aligned} F(7)&=&1\cdot \varphi(1)+7\cdot \varphi(7)&=&1\cdot 1+7\cdot 6&=&43\\ F(1009)&=&1\cdot \varphi(1)+1009\cdot \varphi(1009)&=&1\cdot 1+1009\cdot 1008&=&1017073\\ F(3^2)&=&1\cdot \varphi(1)+3\cdot \varphi(3)+9\cdot \varphi(9)&=&1+6+54&=&61\\ F(2^5)&=&1\cdot 1+2\cdot 1+4\cdot 2+\cdots+32\cdot 16&=&1+2(1+4+\cdots +4^{4})&=&683\\ F(2^6)&=&1\cdot 1+2\cdot 1+4\cdot 2+\cdots+64\cdot 32&=&1+2(1+4+\cdots +4^{5})&=&2731\\ G(7)&=&1\cdot 1+(7^2-1)\cdot 7&&&=&337\\ G(3^2)&=&1\cdot 1+(3^2-1)\cdot 3+(3^4-3^2)\cdot 9&&&=&673\\ G(2^5)&=&1\cdot 1+ (2^2-1)\cdot 2+\cdots+ (2^{10}-2^8)\cdot 2^5&=& 1+6\cdot(1+8+\cdots+8^4)&=&28087\\ \end{aligned}$$

よって答えは

$$\begin{aligned} &2016\cdot 683\cdot 61\cdot 43+\dfrac{1}{2}\cdot (2731\cdot 61\cdot 43\cdot 1017073+28087\cdot 673\cdot 337)\\ &=3611682144+\dfrac{1}{2}\cdot(7285713950149+6370159687)\\ &=\bm{3649653737062}\\ \end{aligned}$$