NF杯2023(M)

$2^{n! + 1} - 1$ が $2n+3$ で割り切れるような $n$ の必要十分条件を求める．$n=1$は不適であるので，以降 $n\geq 2$とする．

まず，$2^{n! + 1} - 1$ が $2n+3$ で割り切れると仮定する．

　$2n+3$ の 素因数 $p$ を任意にとり，$p\lt 2n+3$ であると仮定する．$2n+3$ は奇数なので $p$ も奇数である．$2n+3=pk$ ($k\geq 2$)と書けたとすると，$p \leq \frac{2n+3}{2}$ より $p\leq n+1$．よって $n!+1$ を $p-1$ で割った余りは $1$ である．条件より $2^{n! + 1} \equiv 1 \pmod{p}$ であり，フェルマーの小定理より $2^{p-1}\equiv 1\pmod{p}$ であるから， $$2^{\mathrm{gcd}(p-1, n!+1)} = 2^1 \equiv 1 \pmod{p}$$ を得るが，明らかに矛盾である．よって $2n+3$ は素数である必要があるので，$2n+3 = p$ とおく．$2^{(\frac{p-3}{2})! + 1} \equiv 1\pmod{p}$ となるような素数 $p$ を決定しよう．

　$2^{d} \equiv 1\pmod{p}$ を満たす最小の正の整数 $d$ ($2 \bmod{p}$ の位数) を考える．明らかに $d\leq p-1$．いま $d\leq n$ と仮定すると，$2^d, 2^{n! + 1}\equiv 1 \pmod{p}$ から同様に $2\equiv 1 \pmod{p}$ が得られるから不適．よって $n \lt d$，すなわち $\frac{p-1}{2} \leq d$ を得る．

　位数の一般論により，$d$ は $p-1$ と $n! + 1$ を割り切る．$d = p-1$ と仮定すると $p-1$ が $n! + 1$ を割り切るが，$n!+1$は奇数 ( $\because n\geq 2$ )であり $p-1$は偶数なので不適．よって $d \lt p-1$ である．$\frac{p-1}{2} \leq d \lt p-1$ かつ $d$ は $p-1$の約数なので $$d = \frac{p-1}{2}$$ が確定する．さらにこのとき，$2^{\frac{p-1}{2}}\equiv 1\pmod{p}$ より $2\bmod{p}$ は平方剰余なので，平方剰余第二補充則により $p\equiv 1,7\pmod{8}$ である．$d-1 = \frac{p-3}{2}$ に注意して， $$2^{(d-1)! + 1} \equiv 1\pmod{p}, \quad 2^d \equiv 1\pmod{p}$$ を得る．よって $$2^{\mathrm{gcd}((d-1)! + 1, d)} \equiv 1\pmod{p}$$ が導かれる．ここで指数について，次に注意せよ．

補題. $d = \frac{p-1}{2}$ が $1$， または合成数であるとき $$\mathrm{gcd}((d-1)! + 1, d) = 1.$$

(証明) それぞれの場合において $(d-1)!$ が $d$ の倍数であることを示せばよい． $d=1$のときは明らか．$p\neq 9$ なので $d\neq 4$ に注意．$d$が $4$ と異なる合成数である場合，$d$ は ある奇素数 $q$ の二乗であるか，$1 \lt a \lt b \lt d$ であるような整数 $a,b$ によって $d = ab$ と書ける．前者の場合，$(d-1)!$ は　$q\cdot 2q$ で割れるから $d$ の倍数である．後者の場合，$(d-1)!$ は $a\cdot b$ で割れるから $d$ の倍数である．(証明終)

　よって 補題のような $d$ に関しては $2^1 \equiv 1 \pmod{p}$ となるので不適．よって $d$は素数でなければならない．

　また，$p\equiv 1\pmod{8}$ の場合は $d$ が $4$ の倍数になるので不適．よって　$p\equiv 7\pmod{8}$，すなわち $d\equiv 3\pmod{4}$であることが必要．

以上をまとめると， 「$4$ で割って $3$ 余るソフィージェルマン素数$d$ (すなわち $d$ と $2d+1$ が素数) を用いて $n = d-1$ と書けること」が必要である．

　逆に上のような $n$ が十分であることを示す．実際，$(d-1)! + 1$ はウィルソンの定理 より $dr$ (ただし $r$ は奇数) と書くことができ，$2d + 1 \equiv 7\pmod{8}$ および第二補充則より $2\bmod{(2d+1)}$ は平方剰余であるので，フェルマーの小定理，$r$ が奇数であることから $$2^{dr}\equiv 2^{d(r-1) + d} \equiv 1 \pmod{(2d+1)}$$ となる．つまり，$\frac{2^{(d-1)! + 1} -1}{2d+1}$は整数となる．

　よって解答するべきは $2\leq d \leq 201$ なるソフィージェルマン素数 $d$ であって$d\equiv 3\pmod{4}$ となるものすべてに対する $(d-1)$ の総積である．このような $d$ は $$3,11,23,83,131,179,191$$ である ( $d \gt 3$ のときは $d\equiv 11\pmod{12}$ を利用すると探しやすい)．

　以上より, 求める総積は $$\begin{aligned} & (3-1)(11-1)(23-1)(83-1)(131-1)(179-1)(191-1) \\ =& \mathbf{158629328000} \end{aligned}$$