整数の性質の問題

$21=3\times 7$ で、$3$ と $7$ は互いに素である。よって、$n^2+n+1$ が $21$ で割り切れることは、$3$ でも $7$ でも割り切れることと同じである。

(1) $3$ で割り切れる条件

$n$ を $3$ で割った余りで分類する。$f(n)=n^2+n+1$ とおくと
$$n\equiv 0:f\equiv 1,n\equiv 1:f\equiv 3\equiv 0,n\equiv 2:f\equiv 7\equiv 1(\mathrm{mod}3)$$
となる。したがって、条件は $n\equiv 1(\mathrm{mod}3)$ である。

(2) $7$ で割り切れる条件

$n$ を $7$ で割った余りで分類する。
$$\begin{array}{rlrlrl}n\equiv 0& :f\equiv 1,& n\equiv 1& :f\equiv 3,& n\equiv 2& :f\equiv 7\equiv 0,\\ n\equiv 3& :f\equiv 13\equiv 6,& n\equiv 4& :f\equiv 21\equiv 0,& n\equiv 5& :f\equiv 31\equiv 3,\\ n\equiv 6& :f\equiv 43\equiv 1& & & & \end{array}$$
したがって、条件は $n\equiv 2$ または $n\equiv 4(\mathrm{mod}7)$ である。

(3) 条件を組み合わせる

$n\equiv 1(\mathrm{mod}3)$ かつ $n\equiv 2(\mathrm{mod}7)$ のとき、$n=2,9,16,\dots$ を順に調べる。$16=3\cdot 5+1$ より $n\equiv 16(\mathrm{mod}21)$ である。

$n\equiv 1(\mathrm{mod}3)$ かつ $n\equiv 4(\mathrm{mod}7)$ のとき、$4=3\cdot 1+1$ より $n\equiv 4(\mathrm{mod}21)$ である。

(確認: $f(4)=21$, $f(16)=273=21\times 13$ で、どちらも $21$ で割り切れる。)

よって、条件は $n$ を $21$ で割った余りが $4$ または $16$ であることである。

(4) 個数を数える

• $n=4+21k(k\text{ は }0\text{ 以上の整数})$ のとき、$4+21k\leqq 300$ より $k\leqq \frac{296}{21}=14.09\cdots$ である。よって $k=0,1,\dots ,14$ の $15$ 個。
• $n=16+21k$ のとき、$16+21k\leqq 300$ より $k\leqq \frac{284}{21}=13.52\cdots$ である。よって $k=0,1,\dots ,13$ の $14$ 個。

以上より、求める個数は $15+14=29$ である。

$21=3\times 7$ なので、$n^2+n+1$ が $3$ と $7$ の両方で割り切れる条件を考える。

【mod 3】$n\equiv 0,1,2$ のとき $n^2+n+1\equiv 1,0,1$ となる。よって $n\equiv 1(\mathrm{mod}3)$。

【mod 7】$n\equiv 0,1,\dots ,6$ のとき $n^2+n+1\equiv 1,3,0,6,0,3,1$ となる。よって $n\equiv 2,4(\mathrm{mod}7)$。

【mod 21】中国剰余定理より、$n\equiv 1(\mathrm{mod}3)$ かつ $n\equiv 2(\mathrm{mod}7)$ なら $n\equiv 16(\mathrm{mod}21)$、$n\equiv 1(\mathrm{mod}3)$ かつ $n\equiv 4(\mathrm{mod}7)$ なら $n\equiv 4(\mathrm{mod}21)$。

検算：$n=4$ で $21$、$n=16$ で $273=21\times 13$ となり、どちらも $21$ で割り切れる。

【個数】
$n=4+21k\le 300$ より $k=0,\dots ,14$ で $15$ 個。
$n=16+21k\le 300$ より $k=0,\dots ,13$ で $14$ 個。

合計 $15+14=29$ 個。