NF杯2024(I) - 別の絞り方（割合を見る）

$n$ が $5$ 以上かつ奇素因数 $p$ を持つときに条件を満たすことを別の方法で示す．

　方針の概略 ： $\frac{k(k+1)}{2} \bmod{p}$ が取りうる値の個数が $p$ に対して十分少ないことから，$\frac{k(k+1)}{2}\bmod{n}$ が取りうる値の種類も少ないということを示して，ある $n=a,b$ で重複が生じていなくてはならないということを導く。

　まず集合 $I(n)$ を

$$I(n) = \left\{ \frac{k(k+1)}{2} \bmod{n} \mid k=1,2,\dots, n-1 \right\}$$

で定める．もし条件を満たさないなら，$k$ ごとに剰余類は異なるから $$\frac{\# I(n)}{n} = \frac{n-1}{n} \geqq \frac{4}{5}$$ である（取りうる値の種類は十分多いと考える）．一方で，$\frac{k(k+1)}{2} \equiv 2^{-1}(k+2^{-1})^2 - 2^{-3} \pmod{p}$ なので （※） $$\begin{aligned} \left\{ \frac{k(k+1)}{2} \bmod{p} \mid k=1,2,\dots, n-1 \right\} \subset \left\{ 2^{-1}x - 2^{-3} \mid x は 0 または平方剰余 \right\} \end{aligned}$$ だから，左辺の集合の要素数は高々 $\frac{p+1}{2}$個である（実際はちょうど$\frac{p+1}{2}$個でもある）．そこで，$h$を左辺の要素数として $$\left\{ \frac{k(k+1)}{2} \bmod{p} \mid k=1,2,\dots, n-1 \right\} = \{ c_1 \bmod{p}, \dots, c_{h} \bmod{p}\}$$ であるような $c_1,\dots, c_{h} \in \mathbb{Z}$ を取る($i\neq j$ならば$c_i \not\equiv c_j \pmod{p}$ に注意)．このとき $$I(n) \subset \{ (c_i + pk) \bmod{n} \mid k=1,2,\dots, \frac{n}{p},\quad i=1,2,\dots, h \}$$ であるから，個数を評価して $$\#I(n) \leqq \frac{n}{p}\cdot h \implies \frac{\#I(n)}{n} \leqq \frac{h}{p} \leqq \frac{p+1}{2p} \leqq \frac{2}{3}$$ を得るが，これは $\frac{\# I(n)}{n} \geqq \frac{4}{5}$ に反する．よって矛盾であり，この場合は条件を満たす．

　したがって，あとは $n=3, 2^{k}$ ($k=0,1,2,\dots$) が条件を満たさないことを確認すればよい（本解と同様である）．

（※）$2^{-1}$の意味が有理数から剰余体の元に変わっていることに注意（間違ってはいない）．$2^{-1} \equiv\frac{p+1}{2} \pmod{p}$ なので，$4k(k+1) \bmod{p} = (2k+1)^2 - 1 \bmod{p}$ を $\left(\frac{p+1}{2}\right)^{3}$ 倍した式と読み替えてもよい．その場合は，$x - 1$ ($x$ は平方剰余) の集合の各要素を $\left(\frac{p+1}{2}\right)^{3}$ 倍した剰余が，$\frac{k(k+1)}{2} \bmod{p}$ が取りうる値の集合になる．