整数の性質の問題

$1000=2^3\cdot 5^3$ で、$8$ と $125$ は互いに素である。よって
$$n^5\equiv n(\mathrm{mod}1000)⟺n^5\equiv n(\mathrm{mod}8)\text{ かつ }{n}^5\equiv n(\mathrm{mod}125)$$
が成り立つ。それぞれの条件を満たす余りを調べる。

(1) $\mathrm{mod}8$ について

• $n$ が奇数のとき、$n^2\equiv 1(\mathrm{mod}8)$ である（奇数の平方は $8$ で割ると $1$ 余る）。よって $n^4\equiv 1$ となり、$n^5\equiv n(\mathrm{mod}8)$ は常に成り立つ。$8$ で割った余りは $1,3,5,7$ の $4$ 通りである。
• $n$ が偶数のとき、$n=2m$ とおくと $n^5=32m^5\equiv 0(\mathrm{mod}8)$ である。よって条件は $n\equiv 0(\mathrm{mod}8)$ となり、余りは $0$ の $1$ 通りである。

したがって、$\mathrm{mod}8$ で条件を満たす余りは $5$ 通りである。

(2) $\mathrm{mod}125$ について

- $n\equiv 0(\mathrm{mod}5)$ のとき、$n^5$ は $5^5$ で割り切れるので $n^5-n\equiv -n(\mathrm{mod}125)$ である。よって条件は $n\equiv 0(\mathrm{mod}125)$ となる（$1$ 通り）。
- $n$ が $5$ の倍数でないとき、条件は $125\mid n(n^4-1)$ すなわち $125\mid n^4-1$ である。ここで
$$n^4-1=(n-1)(n+1)(n^2+1)$$
と因数分解できる。
- $n\equiv 1(\mathrm{mod}5)$ のとき、$n+1\equiv 2$、$n^2+1\equiv 2(\mathrm{mod}5)$ であり、これらは $5$ で割り切れない。よって $125\mid n-1$ となり、$n\equiv 1(\mathrm{mod}125)$ の $1$ 通りである。
- $n\equiv 4(\mathrm{mod}5)$ のとき、同様に $n\equiv -1(\mathrm{mod}125)$ の $1$ 通りである。
- $n\equiv 2,3(\mathrm{mod}5)$ のとき、$n\pm 1$ は $5$ で割り切れないので、条件は $n^2\equiv -1(\mathrm{mod}125)$ である。

$n\equiv 2(\mathrm{mod}5)$ の場合を考える。$n=2+5a$ とおくと、$\mathrm{mod}25$ で $4+20a\equiv -1$、すなわち $5(1+4a)\equiv 0(\mathrm{mod}25)$ となる。よって $4a\equiv -1(\mathrm{mod}5)$ より $a\equiv 1(\mathrm{mod}5)$ で、$n\equiv 7(\mathrm{mod}25)$ である。

次に $n=7+25k$ とおくと、$\mathrm{mod}125$ で $49+350k\equiv -1$ となる。$350\equiv 100(\mathrm{mod}125)$ なので $100k\equiv -50(\mathrm{mod}125)$ である。両辺を $25$ で割って $4k\equiv -2\equiv 3(\mathrm{mod}5)$ となり、$k\equiv 2(\mathrm{mod}5)$ である。よって $n\equiv 57(\mathrm{mod}125)$ を得る。実際、$57^2+1=3250=125\cdot 26$ である。

この解はただ $1$ つである。実際、$x,y$ がともに $x\equiv y\equiv 2(\mathrm{mod}5)$ で $x^2\equiv y^2\equiv -1(\mathrm{mod}125)$ を満たすとすると、$(x-y)(x+y)\equiv 0(\mathrm{mod}125)$ である。ここで $x+y\equiv 4(\mathrm{mod}5)$ は $5$ で割り切れないので、$x\equiv y(\mathrm{mod}125)$ となる。

同様に、$n\equiv 3(\mathrm{mod}5)$ のときは $n\equiv -57\equiv 68(\mathrm{mod}125)$ のただ $1$ 通りである。

以上より、$\mathrm{mod}125$ で条件を満たす余りは $0,1,57,68,124$ の $5$ 通りである。

(3) 個数と和

中国剰余定理（$8$ と $125$ が互いに素であること）により、$\mathrm{mod}8$ の余りと $\mathrm{mod}125$ の余りの組 $5\times 5=25$ 通りのそれぞれに対して、$\mathrm{mod}1000$ の余りがちょうど $1$ つ対応する。よって $1\leqq n\leqq 1000$ に条件を満たす $n$ は $25$ 個ある。

• $n=1000$（余り $0$）は条件を満たす。
• 残りの $24$ 個は $1\leqq n\leqq 999$ にある。$(-n{)}^5-(-n)=-(n^5-n)$ なので、$n$ が条件を満たせば $1000-n$ も条件を満たす。また $n=1000-n$ となるのは $n=500$ のときだけだが、$500\equiv 4(\mathrm{mod}8)$ なので $500$ は条件を満たさない。

したがって、残りの $24$ 個は和が $1000$ になる $12$ 組に分けられる。求める和は
$$12\cdot 1000+1000=13000$$
である。

$n^5-n$ が $1000=8\cdot 125$ で割り切れる条件を、$8$ と $125$ に分けて考える。

【mod 8】$n^5-n=n(n^4-1)$ とする。
- $n$ が偶数のとき、$n^4-1$ は奇数なので $8\mid n$ が必要。
- $n$ が奇数のとき、$n^4\equiv 1(\mathrm{mod}16)$ なので常に成り立つ。

よって $n\equiv 0,1,3,5,7(\mathrm{mod}8)$ の $5$ 通り。

【mod 125】
- $5\mid n$ のとき、$n^4-1$ は $5$ と互いに素なので $125\mid n$ が必要。
- $5\nmid n$ のとき、$n^4\equiv 1(\mathrm{mod}125)$ が必要。$125$ を法とする既約剰余類群は位数 $100$ の巡回群なので、解は $4$ 個。具体的には $n\equiv \pm 1,\pm 57(\mathrm{mod}125)$ である。$57^2=3249=26\cdot 125-1$ より $57^2\equiv -1$ となり、$57^4\equiv 1$ が確認できる。

よって $n\equiv 0,1,124,57,68(\mathrm{mod}125)$ の $5$ 通り。

【合わせる】中国剰余定理より、$0\le n\le 999$ の範囲に解は $5\times 5=25$ 個ある。

解の集合は $n\mapsto -n$ で閉じている。これは、各条件が $n$ と $-n$ で同じように成り立つためである。そこで $1\le n\le 999$ の解を $n$ と $1000-n$ の組にまとめる。

$n=0$ 以外の解は $24$ 個ある。$n=500$ は $500\equiv 4(\mathrm{mod}8)$ より解ではないので、自己対応する解はなく、$12$ 組ができる。各組の和は $1000$ なので、合計は $12000$。

$1\le n\le 1000$ では $n=0$ の代わりに $n=1000$ が入る（$1000$ は解）ので、全体の和は $12000+1000=13000$。

【検算】$n=1$、$n=57$、$n=1000$ が条件を満たすことを確認した。$57\equiv 1(\mathrm{mod}8)$ なので mod 8 の条件も満たす。また対称性による和の計算は、解の個数 $25$ と整合している。