院解8 京大数学系H27 基礎II 4 整数の個数

$3500=7\cdot 5^3\cdot 2^2$である.$ x^3+3x=x(x^2+3)$と変形し各素因数が含まれるかどうかをみる.$x\equiv 0,\pm 1\pm 2\ (\text{mod}\ 5)$のとき,それぞれ$x^2+3\equiv 3,-1,2\ (\text{mod}\ 5)$なので$x^2+3$は$5$の倍数にならない.よって$3500$の倍数であるためには$x$は$5^3$の倍数である必要があり,そのとき明らかに$x^3+3x$は$5^3$で割り切れる.そこで$n\in \mathbb{N}$とし$x=125n$とおく.
$125\equiv -1\ (\text{mod}\ 7)$なので$x^2+3\equiv n^2+3\ (\text{mod}\ 7)$.よって$7$で割り切れるためには$n\equiv 0,\pm 2\ (\text{mod}\ 7)$である必要がある.逆にこのとき$x^3+3x$は$7$で割り切れる.
$ x$が偶数のとき$x^2+3$は奇数だから$x$は$4$の倍数である必要がある.
以上から残る候補は$n=5,7,9,12,16,19,21,23,28$.これらに対し$x^3+3x$が$4$の倍数になるかをみればよい.$n$が偶数なら上で述べたように$4$の倍数である.$n$が奇数なら$x^2+3$が$4$の倍数ならよいが,$k$を整数として$x=2k+1$とおくと$x^2+3=4(k^2+k+1)$となり$4$の倍数.よって$9$こ.$\Box$