NF杯2023(I)

条件を満たす$x$の集合を$S(n)$で表す.

補題. $x\in S(n)$ならば $x^{22} = 1$または$x^{24} = 1$である．

(証明) $x\in S(n)$のとき$x^{2024} = 1$なので，とくに$|x| = 1$．よって$x^{n}(x-1) = x^{23} - 1$ から $|x-1| = |x^{23}-1|$ を得る．この式を複素数平面上で考えれば，$x,x^{23}$ は単位円周 $|z| = 1$ 上にあり，かつ $1$ から等距離であるので，$x = \overline{x^{23}}$ または $x = x^{23}$ となる．前者のとき，$|x| = 1$ より$x^{24} = 1$となる．$x\neq 0$なので後者のときは $x^{22} = 1$ となる．(証明終)

この補題をもとに方程式を整理する．以下に注意する．

• $x^{22} = 1$のとき，$x^{n}(x-1) = x^{23} - 1 = x-1$ なので $x^{n}=1$となる．$x^{2024} = 1$ かつ $x^{22} = 1$ かつ $x^n = 1$ であることは $x^{\mathrm{gcd}(n,22)} = 1$ であることと同値である．
• $x^{24} = 1$ のとき，$x^{n}(x-1) = x^{23} - 1 = x^{-1} - 1$ を整理して $x^{n+1} = -1$ を得る．このとき $x^{2n+2} = 1$ であり，複素数$x$に対して $x^{2024} = 1$ かつ $x^{24} = 1$ かつ $x^{2n+2} = 1$ であることは $x^{{\rm gcd}(8,2n+2)} = 1$ であることと同値である．
• $x^{22} = 1$ かつ $x^{24} = 1$ を満たす 複素数 $x$ は $x=\pm 1$ のみである．常に $1\notin S(n)$ であり， $-1\in S(n)$ であるのは $n$ が偶数のときに限る．

　ここで，$g(n)={\rm gcd}(n,22)$，$h(n) = {\rm gcd}(8,2n+2)$ とおく．上より $S(n)$ は次の3種類の集合 $A(n), B(n), C(n)$ に分割される： $$\begin{aligned} A(n)&= \{ x\neq \pm 1 \mid x^{{\rm gcd}(n,22)} = 1\}\\ B(n)&= \{ x\neq \pm 1 \mid x^{\mathrm{gcd}(8,2n+2)} = 1, \quad x^{n+1} = -1\} \\ C(n)&= \begin{cases} \varnothing \quad (n\text{が奇数})\\ \{ -1 \} \quad (n\text{が偶数}) \end{cases} \end{aligned}$$

　$f(n) = |A(n)| + |B(n)| + |C(n)|$ と書けるので，以下の場合に分けて計算する．

• $n$ が偶数のとき，$h(n)=2$ なので $B(n) = \varnothing$ である．よって $$f(n) = (\mathrm{gcd}(n,22) - 2) + 0 + 1 = g(n) - 1.$$
• $n$ が奇数のときは $A(n) = \{ x \mid x^{g(n)} = 1 \}\setminus{\{ 1 \}}$ なので $f(n) = g(n) - 1 + |B(n)|$ である．

$n$ が奇数のときの $|B(n)|$ を調べるために，以下の3つの場合分けを行う．$k$は $0$ 以上の整数とする．

　(Case 1.) $n = 4k+1$ のとき，$h(n) = 4$ なので $B(n) = \{x\neq \pm 1\mid x^{4} = 1, x^{2} = -1\}$ より $|B(n)| = 2$．

　(Case 2.) $n=8k+3$のとき，$h(n) = 8$，$x^{n+1} = (x^{8})^k \cdot x^4$ なので $B(n) =\{x\neq \pm 1\mid x^8 = 1, x^4 = -1\}$ より $|B(n)| = 4$．

　(Case 3.) $n = 8k+7$ のとき， $h(n) = 8$，$x^{n+1} = (x^8)^{k+1}$ である．$x\in B(n)$ のとき $x^{n+1} = 1 \neq -1$ となるため $B(n) = \varnothing$である．

　以上をまとめると，$f(n)$ は 以下で与えられる． $$f(n) = g(n) + r(n),\quad \text{ただし} r(n) = \begin{cases} -1 & (n \text{は偶数, または} n\equiv 7 \pmod{8}) \\ 1 & (n \equiv 1\pmod{4}) \\ 3 & (n \equiv 3 \pmod{8}) \end{cases}$$ 　これにより，求めるべき総和は以下のように計算される： $$\begin{aligned} \sum_{n=0}^{2023} f(n) &= \sum_{k=0}^{253} \{g(8k) + \dots + g(8k+7) + (r(8k) + \dots + r(8k+7))\} \\ &= \sum_{k=0}^{252} \{g(8k) + \dots + g(8k+7) + 0\} \\ &= \sum_{n=0}^{2023} \mathrm{gcd}(n,22) \\ &= 92\sum_{n=0}^{21} \mathrm{gcd}(n,22) \\ &= 92(1\times \varphi(22) + 2\times \varphi(11) + 11\times \varphi(2) + 22\times \varphi(1)) \\ &= 92(10 + 20 + 11 + 22) \\ &= 92\times 63\\ &= \mathbf{5796} \end{aligned}$$