Prime divisors of n² + n + 1

1. Since $p\mid n^2+n+1$, we have $p\nmid n$ (otherwise $p\mid1$), and $p\mid n^3-1$, so $n^3\equiv1\pmod p$. The order $d$ of $n$ modulo $p$ divides $3$, so $d\in\{1,3\}$.

• If $d=1$, then $n\equiv1$ and $0\equiv n^2+n+1\equiv3\pmod p$, so $p=3$.
• If $d=3$, then by Fermat's little theorem $n^{p-1}\equiv1$, so $d=3$ divides $p-1$, that is $p\equiv1\pmod3$.

2. Let $k\ge3$ and put $m=k!$, $N=m^2+m+1$. For every prime $q\le k$ we have $q\mid m$, hence $N\equiv1\pmod q$. So every prime divisor of $N$ is larger than $k$, in particular different from $3$. By part 1 each prime divisor of $N$ is $\equiv1\pmod 3$; and $N>1$ has at least one. So for every $k$ there is a prime $\equiv1\pmod3$ larger than $k$.

Lesson. A prime factor of $\Phi_d(n)$ (here $\Phi_3(n)=n^2+n+1$) is $\equiv1\pmod d$ unless it divides $d$: this is the standard route to "infinitely many primes $\equiv1\pmod d$".