NF杯2024(I)

　$S_i = \dfrac{i(i+1)}{2}$ とおき，条件を満たさない $n$ が，$3$ および非負整数 $k$ によって $2^k$ と表される正整数のみであることを示そう．

　まず，$n=3$ と $n=2^k$ が条件を満たさないことを示す．$n=1,2,3$ のときは明らか．$n=2^k$ $(k\geq 2)$ のとき，$1\leq a\lt b\leq 2^k-1$ なる整数 $a,b$ であって $S_a\equiv S_b\pmod{2^k}$ をみたすものがあるとすると， $$\frac{1}{2}(b-a)(a+b+1)\equiv 0\pmod{2^k}$$ となる．$b-a$ と $a+b+1$ のうち一方は奇数なので，上式をみたすためには $b-a$ と $a+b+1$ のうちどちらかが $2^{k+1}$ で割り切れる必要がある．しかし，$1\leq b-a\leq 2^k-2$ と $4\leq a+b+1\leq 2^{k+1}-2$ よりこれは不適．

　逆に，上記以外の全ての正整数 $n$ が条件を満たすことを示す．まず，$n$ が $5$ 以上の奇数の約数をもつとき，$S_c\equiv S_1\pmod{n}$ なる $2$ 以上 $n-1$ 以下の整数 $c$ が存在することを示そう．このとき $n$ は $5$ 以上の奇数 $m$ と非負整数 $k$ を用いて $n=m\cdot 2^k$ と表せて，$m-1$ 個の整数 $1\cdot 2^k,2\cdot 2^k,\cdots ,(m-1)2^k$ はいずれも $m$ で割り切れず，かつ $m$ で割った余りがすべて異なるので，これらは $\hspace{-3mm}\mod{m}$ において $1,2,\cdots,m-1$ の並び替えになっている．$m\geq 5$ より $$m_0\cdot 2^k\equiv m-3\pmod{m}$$ なる $m-1$ 以下の正の整数 $m_0$ が存在する．$k\geq 2$ のとき $$1\lt m_0\cdot 2^k+1\leq (m-1)\cdot 2^k+1\lt n-1$$ $$1\lt 2^k-2\leq (m-m_0)2^k-2\leq (m-1)2^k-2\lt n-1$$ であり，$m_0$ が偶数なら $S_{m_0\cdot 2^k+1}\equiv S_1\pmod{n}$，$m_0$ が奇数なら $S_{(m-m_0)2^k-2}\equiv S_1\pmod{n}$ となるのでよい．$k=1$ のときは $m_0$ が偶数のときは同様であり，$m_0$ が奇数のとき $m_0\leq m-2$ より $$1\lt 2^{k+1}-2\leq (m-m_0)2^k-2\leq (m-1)2^k-2\lt n-1$$ なのでこれも先ほどと同様である．$k=0$ のとき $$(m-1)\cdot 2^k+3\equiv 2\pmod{n}$$ $$(m-2)\cdot 2^k+3\equiv 1\pmod{n}$$ より $m_0\leq m-3$ なので $$1\lt m_0\cdot 2^k+1\leq (m-3)\cdot 2^k+1\lt n-1$$ $$1\leq 3\cdot 2^k-2\leq (m-m_0)2^k-2\leq (m-1)2^k-2\lt n-1$$ となるため，このときも同様によい．また，$n=3\cdot 2^k(k\geq 1)$ と表されるときは $k\geq 2$ とすると $$m_0\cdot 2^k\equiv 1\pmod{3}$$ なる $m_0$ ( $=1$ または $2$ )が存在し $$1\lt m_0\cdot 2^k+2\leq 2^{k+1}+2\lt n-1$$ $$1\leq 2^k-3\leq (3-m_0)2^k-3\leq 2^{k+1}-3\lt n-1$$ なので $m_0=1$ のとき $S_{2^{k+1}-3}\equiv S_{2}\pmod{n}$, $m_0=2$ のとき $S_{2^{k+1}+2}\equiv S_2\pmod{n}$ なのでよい．さらに，$n=6$ のときは $S_5\equiv S_2\pmod{6}$ なのでよい．

　以上より，条件を満たさないものは $3$ および $2^k$ $(k\geq 0)$ のみである．特に $100$ 以下の正整数で条件を満たさないものは $3, 2^k$ $(k=0,1,\dots ,6)$ であるので，解答すべき値は $$\sum_{n=1}^{100}n-\sum_{k=0}^{6}2^k-3=\mathbf{4920}$$ である．