How to prove that no prime factor of $x^2-x+1$ is of the form $6k-1$ 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)?
 A: 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}$.
A: 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
A: 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.
A: 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$ .
A: First, some facts about numbers in your sequence. Let $n=x^2-x+1$. If $x=3k-1$, then
\begin{align*}
n=x^2-x+1 &= (3k-1)^2-(3k-1)+1\\
&= 9k^2-6k+1-3k+1+1\\
&= 9k^2-9k+3\\
\implies n/3 &= 3k^2-3k+1
\end{align*}
$k^2$ and $k$ have the same parity. Therefore
$n/3=1\mod 6$. If $x$ is any other integer then $n=1\mod 6$ as can be easily checked. Thus $n$ is odd; and, after a factor of 3 has been extracted, if there is one, the result is 1, modulo 6. In any case $n\ne 5\mod 6$.
Suppose your conjecture is wrong, and let $p$ be the lowest prime counterexample, i.e. lowest prime $p\ne3$, not of the form $6k+1$, which divides a number that is in your sequence.
Let prime $p$ divide $n=x^2-x+1$. Then $p\ne 2$. Because $p\ne3$ and $p\ne1\mod 6$, $p=5\mod 6$.
Let $x=sp+r$ where $s$ is the nearest integer to $x/p$, so $|r|<p/2$. Then
\begin{align*}
n=x^2-x+1 &= (sp+r)^2-(sp+r)+1\\
&= s^2p^2+2srp+r^2-sp-r+1\\
&= Ap+r^2-r+1
\end{align*}
where $A=s^2p+2sr-s$. Thus
$p\mid r^2-r+1$, so, for some integer $m'$,
\begin{align*}
m'p &= r^2-r+1\\
&\leqslant r^2\\
&<p^2/4\\
\implies m' &< p/4.
\end{align*}
If $3\mid m'$, let $m=m'/3$, otherwise let $m=m'$. Then $3\nmid m$, and $m\leqslant m'<p/4$.
Because $m<p$ and $p$ is the smallest counterexample, each prime factor $q$ of $m$ is 1, modulo 6 (because $q\leqslant m<p$ so $q$ is not a counterexample). So, modulo 6, $m=1$, $p=5$, so $mp=5$. But $mp = r^2-r+1$ is in your sequence, so $mp\ne 5\mod 6$. This is a contradiction. (In fact, for any integer $m$ where $m=5\mod 6$, at least one prime factor of $m$ is $q=5\mod 6$.)
Therefore your conjecture is correct.
