How to prove that no prime factor of $x^2-x+1$ is of the form $6k-1$

Question

Consider sequence $x^2-x+1$ ($1,3,7,13,21,31,43,57,73,91,\dots$). Let's consider prime factorization of each term. $$3=3$$ $$7=7$$ $$13=13$$ $$21=3\times7$$

It seems that the only prime factors we ever get are 3 and those of the form $6k+1$. In fact, prime factorization of the first 10 000 terms of the sequence gives 7233 distinct primes and all of them (except 3) are $6k+1$.

That no member of the sequence is ever divisible by a prime of the form $6k-1$ is a purely empirical conjecture. Is there a formal proof for it (or a counterexample)?

Answer 1

Let $p$ be a prime.

$$p\mid x^2-x+1$$

$$\implies p\mid 4\left(x^2-x+1\right)=(2x-1)^2+3$$

$$\iff (2x-1)^2\equiv -3\pmod{p}$$

By Quadratic Reciprocity this implies either $p=2$ or $p=3$ or $p\equiv 1\pmod{3}$.

$2$ and $3$ are not of the form $6k-1$. And if $p\equiv 1\pmod{3}$, then $p$ is not of the form $6k-1$ because $6k-1\not\equiv 1\pmod{3}$.

Answer 2

Assume that a prime $p|n^2-n+1$ form some integer $n$. Then we also have that $p$ is a factor of $(n+1)(n^2-n+1)=n^3+1$. In other words $$ n^3\equiv-1\pmod p.\qquad(*) $$ Let's try to figure out the order of the residue class of $n$ modulo $p$. From $(*)$ it follows that $n^6\equiv1\pmod p$, so the order is a factor of six, but not a factor of three.

We cannot have $n^2\equiv1\pmod p$, for then $p$ is also a factor of $(n^2-1)-(n^2-n+1)=n-2$. When $n\equiv 2\pmod p$, then $n^2-n+1\equiv3\pmod p$, so we must be in the exceptional case $p=3$. Otherwise the order is not a factor of two.

So if $p>3$ the order is six. But by Lagrange's theorem from elementary group theory the order is a factor of $p-1$. QED

Answer 3

We may notice that $$ q(x)=x^2-x+1 = \Phi_6(x) = \frac{(x^6-1)(x-1)}{(x^3-1)(x^2-1)}$$ is a cyclotomic polynomial. If for some prime $p>6$ we have $q(x)\equiv 0\pmod{p}$, that means that $x$ has order $6$ in $\mathbb{F}_p^*$, since by the above identity the roots of $q(x)$ are exactly the primitive sixth roots of unity. By Lagrange's theorem, the order of an element of $\mathbb{F}_{p}^*$ has to be a divisor of the order of the group, that is $p-1$. So: $$ x^2-x+1\equiv 0\pmod{p}\quad\Longrightarrow\quad p\equiv 1\pmod{6}.$$ This argument is also the key for an elementary proof of the following fact: for every $n\geq 2$, there are infinite primes of the form $kn+1$. It is interesting to point out that nowadays an elementary proof of the more general Dirichlet's theorem, avoiding the Selberg-Erdos machinery involved in the elementary proof of the PNT, is still missing.

Answer 4

As a complement to @user236182, let us show that $(\frac{-3}{p})=1$ is a necessary and sufficient condition for an odd prime $p$ to divide $x^2 - x + 1$ (where $x$ is an integer). Just notice that $x^2 - x + 1 = (x + j)(x + j^2)$, where $j$ denotes a primitive cubic root of $1$. Since the ring $\mathbf Z [j]$ is an UFD, the division condition above is equivalent to the splitting of $p$ in the quadratic field $ \mathbf Q (j) = \mathbf Q (\sqrt-3)$, and this is known to be equivalent to $(\frac{-3}{p})=1$ .