整数論の問題

$10000=2^4\cdot 5^4=16\cdot 625$ で、$16$ と $625$ は互いに素である。中国剰余定理より、$0\leqq x\leqq 9999$ の整数 $x$ は ($x\mathrm{mod}16$, $x\mathrm{mod}625$) の組と 1 対 1 に対応し、
$$x^3\equiv x(\mathrm{mod}10000)⟺x^3\equiv x(\mathrm{mod}16)\text{ かつ }{x}^3\equiv x(\mathrm{mod}625).$$
よって、法 $16$ での解の個数と法 $625$ での解の個数の積が答えである。

法 $16$: $x^3-x=x(x^2-1)$。
- $x$ が偶数のとき、$x^2-1$ は奇数なので、$16\mid x(x^2-1)⟺16\mid x$。$0\leqq x\leqq 15$ では $x=0$ の $1$ 個。
- $x$ が奇数のとき、$x$ は $16$ と互いに素なので $16\mid x^2-1⟺x^2\equiv 1(\mathrm{mod}16)$。奇数 $1,3,5,\dots ,15$ の平方を法 $16$ で計算すると $1,9,9,1,1,9,9,1$ なので、$x=1,7,9,15$ の $4$ 個。

法 $16$ での解は $5$ 個。

法 $625$: $x^3-x=(x-1)x(x+1)$。3 つの因数は互いの差が $2$ 以下なので、$5$ で割り切れるのは高々 1 つである。したがって $5^4\mid (x-1)x(x+1)$ となるのは、どれか 1 つの因数が $5^4$ で割り切れるとき、すなわち $$x\equiv 0,1,-1(\mathrm{mod}625)$$ のときに限る。これらは互いに異なるので、法 $625$ での解は $3$ 個。

以上より、求める個数は $5\times 3=15$ である。

$x^3\equiv x(\mathrm{mod}10000)$ は $x(x-1)(x+1)\equiv 0$ で、$10000=16\cdot 625$ なので法 $16$ と法 $625$ に分け、中国剰余定理で合成する。

法 $625=5^4$: $x,x-1,x+1$ のうち $5$ の倍数になりうるのは高々 $1$ つ（差が $1,2$ だから）。よって $625$ で割り切れるのはそのどれか $1$ つが $625$ の倍数のとき、$x\equiv 0,1,-1(\mathrm{mod}625)$ の $3$ 個。

法 $16$: $x$ が偶数なら $x\pm 1$ は奇数なので $16\mid x$、すなわち $x\equiv 0$ の $1$ 個。$x$ が奇数なら $(x-1)(x+1)$ が $16$ の倍数となる条件は、$x\pm 1$ の一方が $2$ だけ、他方が $8$ の倍数になることで $x\equiv \pm 1(\mathrm{mod}8)$。法 $16$ では $x\equiv 1,7,9,15$ の $4$ 個（例: $7\cdot 6\cdot 8=336=16\cdot 21$）。計 $5$ 個。

合計 $5\times 3=15$ 個。

検算: 法 $16$ の全数調べで $x=0,1,7,9,15$ が $x^3\equiv x$ をみたす（$x=3$: $24\not\equiv 0$, $x=5$: $120=16\cdot 7+8$ で不可）。