整数の性質の問題

以下、合同式はすべて $7$ を法とする。

$2^n$ の余り

$2^3=8\equiv 1$ である。よって $2^n$ を $7$ で割った余りは、$n$ を $3$ で割った余りで決まる。

• $n\equiv 0(\mathrm{mod}3)$ のとき $2^n\equiv 1$
• $n\equiv 1(\mathrm{mod}3)$ のとき $2^n\equiv 2$
• $n\equiv 2(\mathrm{mod}3)$ のとき $2^n\equiv 4$

$n^2$ の余り

$n^2$ を $7$ で割った余りは、$n$ を $7$ で割った余り $r$ で決まる。

• $r=0$ のとき $0$
• $r=1,6$ のとき $1$
• $r=2,5$ のとき $4$
• $r=3,4$ のとき $9\equiv 2$ および $16\equiv 2$ より $2$

条件 $2^n\equiv n^2$ を満たす場合

$2^n$ の余りは $1,2,4$ のいずれかである。したがって次の $3$ 通りに分かれる。

• $n\equiv 0(\mathrm{mod}3)$ のとき、$n^2\equiv 1$ が必要なので $r=1,6$
• $n\equiv 1(\mathrm{mod}3)$ のとき、$n^2\equiv 2$ が必要なので $r=3,4$
• $n\equiv 2(\mathrm{mod}3)$ のとき、$n^2\equiv 4$ が必要なので $r=2,5$

$3$ と $7$ は互いに素であるから、$n$ を $21$ で割った余りで条件が決まる。$1$ から $21$ までの中で各組合せに当てはまる数を探す。

• $3$ で割り切れ $7$ で割って $1$ 余る数：$15$
• $3$ で割り切れ $7$ で割って $6$ 余る数：$6$
• $3$ で割って $1$ 余り $7$ で割って $3$ 余る数：$10$
• $3$ で割って $1$ 余り $7$ で割って $4$ 余る数：$4$
• $3$ で割って $2$ 余り $7$ で割って $2$ 余る数：$2$
• $3$ で割って $2$ 余り $7$ で割って $5$ 余る数：$5$

よって条件は、$n$ を $21$ で割った余りが $2,4,5,6,10,15$ のいずれかであることと同値である。

(確認) $n=5$ のとき $2^5-5^2=7$、$n=6$ のとき $2^6-6^2=28$ となり、確かに $7$ で割り切れる。

個数を数える

$100=21\times 4+16$ である。

• $1\leqq n\leqq 84$ の範囲には $21$ 個ずつの区切りが $4$ つあるので、$6\times 4=24$ 個ある。
• $85\leqq n\leqq 100$ の範囲では、$21$ で割った余りは $1$ から $16$ までである。このうち $2,4,5,6,10,15$ の $6$ 個がすべて含まれる。

したがって、求める個数は $24+6=30$ である。

$2^n\equiv n^2(\mathrm{mod}7)$ となる $n$ を数える。$2^n\mathrm{mod}7$ は周期 3 で、$n\equiv 1,2,0(\mathrm{mod}3)$ のときそれぞれ $2,4,1$。$n^2\mathrm{mod}7$ は周期 7 で、$n\equiv 0,1,2,3,4,5,6(\mathrm{mod}7)$ のときそれぞれ $0,1,4,2,2,4,1$。したがって条件は周期 21 で繰り返す。

$n=1,\dots ,21$ を調べると、条件を満たすのは $n=2,4,5,6,10,15$ の 6 個。

(確認: $n=2$ は $4-4=0$。$n=10$ は $2^{10}=1024\equiv 2$、$10^2=100\equiv 2$ で一致。$n=15$ は $2^{15}\equiv 1$、$15^2=225\equiv 1$ で一致。)

$100=21\cdot 4+16$。$n=1,\dots ,84$ に 4 周期分で $6\cdot 4=24$ 個ある。残りの $n=85,\dots ,100$ は $n\equiv 1,\dots ,16(\mathrm{mod}21)$ に対応し、そのうち条件を満たすのは $2,4,5,6,10,15$ の 6 個。

合計 $24+6=30$ 個。