n²+n+1 の素因数の性質

$n$ を正の整数とする。

(1) $n^2+n+1$ が3で割り切れるための必要十分条件を、$n$ を3で割った余りを用いて述べよ。

(2) $p$ を3以外の素数とする。ある正の整数 $n$ に対して $n^2+n+1$ が $p$ で割り切れるとき、$p \equiv 1 \pmod{3}$ であることを示せ。

(3) 1以上1000以下の整数 $n$ のうち、$n^2+n+1$ が7で割り切れるものの個数を求めよ。

(1) $n\equiv1\pmod3$ のとき、かつそのときに限り $n^2+n+1$ は3で割り切れる。 (2) 上記の通り $p\equiv1\pmod3$ が成り立つ。 (3) 286個

(1) $n$ を3で割った余りで場合分けする。 $n\equiv0$: $n^2+n+1\equiv1$ $n\equiv1$: $n^2+n+1\equiv1+1+1=3\equiv0$ $n\equiv2$: $n^2+n+1\equiv4+2+1=7\equiv1$ よって3で割り切れるのは $n\equiv1 \pmod3$ のときに限る。

(2) $p\neq3$ が素数で、$n^2+n+1\equiv0\pmod p$ とする。

まず $n\not\equiv0\pmod p$（さもないと $n^2+n+1\equiv1\not\equiv0$）。

$n^3-1=(n-1)(n^2+n+1)\equiv0\pmod p$ より $n^3\equiv1\pmod p$。

もし $n\equiv1\pmod p$ なら $n^2+n+1\equiv3\equiv0\pmod p$ となり $p\mid3$、$p=3$ となって矛盾。よって $n\not\equiv1\pmod p$。

もし $n^2\equiv1\pmod p$ なら $(n-1)(n+1)\equiv0\pmod p$ で $n\not\equiv1$ より $n\equiv-1\pmod p$。これを $n^2+n+1\equiv0$ に代入すると $1-1+1=1\equiv0\pmod p$ となり $p=1$ で矛盾。よって $n^2\not\equiv1\pmod p$。

次に、$1\le a\le p-1$ を任意にとり、$a,\,an,\,an^2 \pmod p$ を考える（$a$ は $p$ と互いに素）。

• $a\equiv an\pmod p \iff n\equiv1\pmod p$（矛盾）
• $a\equiv an^2\pmod p \iff n^2\equiv1\pmod p$（矛盾）
• $an\equiv an^2\pmod p \iff n\equiv n^2\pmod p \iff n(n-1)\equiv0\pmod p$。$n\not\equiv0,1$ なので矛盾。

ゆえに $a,an,an^2$ は $\bmod p$ で相異なる3つの値をとる。また $n^3\equiv1$ なので、$a$ に $n$ 倍を施す操作で $\{1,2,\dots,p-1\}$ 上の関係「$b\equiv a,\,an,\,an^2\pmod p$ のいずれか」は同値関係になり、各同値類の要素数はちょうど3である。

したがって $\{1,2,\dots,p-1\}$（要素数 $p-1$）はちょうど3個ずつの同値類に分割されるので、$3\mid (p-1)$、すなわち $p\equiv1\pmod3$ が示された。

(3) $\bmod7$ で $n^2+n+1$ を調べる。 $n\equiv0$:1, $1$:3, $2$:7≡0, $3$:13≡6, $4$:21≡0, $5$:31≡3, $6$:43≡1

よって解は $n\equiv2,4\pmod7$。

$1\le n\le1000$ で $n\equiv2\pmod7$: $n=2,9,\dots,996$（$2+7\cdot142=996$）、個数は143。

$n\equiv4\pmod7$: $n=4,11,\dots,998$（$4+7\cdot142=998$）、個数は143。

合計 $143+143=286$ 個。