整数の性質の問題

手順1：$2^n$ を $5$ で割った余りの周期を調べる。

$2^1=2,2^2=4,2^3=8\equiv 3,2^4=16\equiv 1(\mathrm{mod}5)$ である。

$2^4\equiv 1(\mathrm{mod}5)$ なので、$2^{n+4}=2^n\cdot 2^4\equiv 2^n(\mathrm{mod}5)$ となる。よって $2^n$ を $5$ で割った余りは $2,4,3,1$ を周期 $4$ でくり返す。

手順2：$n$ を $5$ で割った余りの周期を調べる。

$n$ を $5$ で割った余りは $1,2,3,4,0$ を周期 $5$ でくり返す。

手順3：和の周期を求める。

$4$ と $5$ の最小公倍数は $20$ である。$n$ を $n+20$ に変えても、$2^n$ の余りも $n$ の余りも変わらない。したがって $2^n+n$ を $5$ で割った余りは周期 $20$ でくり返す。

手順4：1 周期分（$n=1$ から $20$）を調べる。

$2^n+n$ を $5$ で割った余りは次のようになる。

$n=1$: $2+1=3$、$n=2$: $4+2=6\equiv 1$、$n=3$: $3+3=6\equiv 1$、$n=4$: $1+4=5\equiv 0$、$n=5$: $2+0=2$、

$n=6$: $4+1=5\equiv 0$、$n=7$: $3+2=5\equiv 0$、$n=8$: $1+3=4$、$n=9$: $2+4=6\equiv 1$、$n=10$: $4+0=4$、

$n=11$: $3+1=4$、$n=12$: $1+2=3$、$n=13$: $2+3=5\equiv 0$、$n=14$: $4+4=8\equiv 3$、$n=15$: $3+0=3$、

$n=16$: $1+1=2$、$n=17$: $2+2=4$、$n=18$: $4+3=7\equiv 2$、$n=19$: $3+4=7\equiv 2$、$n=20$: $1+0=1$。

よって、$1$ 周期の中で割り切れるのは $n=4,6,7,13$ の $4$ 個である。

手順5：範囲内の個数を数える。

$110=20\times 5+10$ なので、$1\leqq n\leqq 100$ には周期がちょうど $5$ 回入り、条件を満たす $n$ は $4\times 5=20$ 個ある。

残りの $101\leqq n\leqq 110$ は、周期の $n=1$ から $10$ の部分と余りが同じである。この中で条件を満たすのは $n\equiv 4,6,7$ にあたる $104,106,107$ の $3$ 個である。

以上より、求める個数は $20+3=23$ 個である。

$2^n\mathrm{mod}5$ は周期 4 で、$n\equiv 1,2,3,0(\mathrm{mod}4)$ のときそれぞれ $2,4,3,1$ になる。$2^n+n\equiv 0(\mathrm{mod}5)$ となる条件を $n\mathrm{mod}4$ で場合分けする。

• $n\equiv 1(\mathrm{mod}4)$ のとき、$2^n\equiv 2$ なので $n\equiv 3(\mathrm{mod}5)$ が必要。これと合わせて $n\equiv 13(\mathrm{mod}20)$。
• $n\equiv 2(\mathrm{mod}4)$ のとき、$2^n\equiv 4$ なので $n\equiv 1(\mathrm{mod}5)$ が必要。これと合わせて $n\equiv 6(\mathrm{mod}20)$。
• $n\equiv 3(\mathrm{mod}4)$ のとき、$2^n\equiv 3$ なので $n\equiv 2(\mathrm{mod}5)$ が必要。これと合わせて $n\equiv 7(\mathrm{mod}20)$。
• $n\equiv 0(\mathrm{mod}4)$ のとき、$2^n\equiv 1$ なので $n\equiv 4(\mathrm{mod}5)$ が必要。これと合わせて $n\equiv 4(\mathrm{mod}20)$。

よって条件を満たすのは $n\equiv 4,6,7,13(\mathrm{mod}20)$ のときである。

$1\le n\le 100$ には周期 20 が 5 回あり、各周期に 4 個ずつあるので $20$ 個。
$101\le n\le 110$ は 20 で割った余りが $1\sim 10$ に相当し、そのうち $4,6,7$ の 3 個が条件を満たす。

合計は $20+3=23$ 個。

検算: $n=4$ のとき $16+4=20$、$n=6$ のとき $64+6=70$、$n=7$ のとき $128+7=135$、$n=13$ のとき $8192+13=8205$。いずれも 5 で割り切れる。