# 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)?

• Hint: Consider the possible values of $x^2-x+1$ modulo $3$. – Joey Zou Aug 4 '16 at 22:14
• Not sure this helps. Of course, all of the members of the sequence are $1 (mod\ 6)$, but so is, e.g., 55, whereas both 5 and 11 are $-1 (mod\ 6)$ – Boris Aug 4 '16 at 22:16
• The proof is analogous to the proof that any odd prime factor of $x^2+1$ is of the form $4k+1$. One uses the theory of quadratic residues to show that any odd prime divisor of $x^2-x+1$ other than $3$ is of the form $6k-1$. – André Nicolas Aug 4 '16 at 22:24

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}$.

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 slight elaboration may help some readers who are not very familiar with orders or group theory. By the Order Test, since $\,n^6\equiv 1\,$ we deduce $\,n\,$ has order $\,6\iff n^3\not\equiv 1\not\equiv n^2\$ – Bill Dubuque Aug 4 '16 at 23:47
• Thanks, @Bill. You are right in that it is not clear from the post alone whether the OP is familiar with basic group concepts. We can similarly ask whether they are familiar with quadratic reciprocity (used in the accepted answer). – Jyrki Lahtonen Aug 5 '16 at 7:25
• Interestingly, I am more familiar with the group theory, I accepted the other answer exactly for the reason of guiding me to learn something new. I appreciate your answer, too, but AFAIU, I cannot accept more than one answer. – Boris Aug 5 '16 at 8:29
• @Boris That's very much ok. I applaud your thinking to accept an answer that makes you learn something more! – Jyrki Lahtonen Aug 5 '16 at 11:16
• @Jyrki It seems that many students often struggle with instances of the Order Test (perhaps because it is often never explicitly presented in textbooks). So it is helpful to explicitly mention it in cases like this where it plays an essential role. – Bill Dubuque Aug 5 '16 at 12:18

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.

• Your second sentence is false for $\,p = 3,\ x = 2.\$ At this level you should probably explain how you made the inference that the order $= 6.\$ – Bill Dubuque Aug 4 '16 at 23:02
• @BillDubuque: fixed. What you mention follows from the fact that the roots of $x^2-x+1$ are the primitive sixth roots of unity. – Jack D'Aurizio Aug 4 '16 at 23:13
• My point was that if you elaborate on that a little in your answer the it will be much more accessible to many readers. – Bill Dubuque Aug 4 '16 at 23:20

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$ .

• Simply notice that any prime divisor $p$ of $x^2-x+1$ must be odd (because $x^2-x+1=x(x-1)+1$ is even for all $x\in\mathbb Z$) and so, assuming $p$ is an odd prime, we have that $p\mid x^2-x+1$ if and only if $(2x-1)^2\equiv -3\pmod{p}$ if and only if $t^2\equiv -3\pmod{p}$ for some $t\in\mathbb Z$ because the congruence $2x-1\equiv t\pmod{p}$ has the unique solution $x\equiv 2^{-1}(1+t)\pmod{p}$. Here $2^{-1}\bmod p$ exists because $p$ is odd. – user236182 Aug 5 '16 at 12:32
• I meant $x(x-1)+1$ is odd for all $x\in\mathbb Z$. – user236182 Aug 5 '16 at 12:39
• OK, thank you. But actually, my main point was to stress that the quadratic form x^2 - xy + y^2 is in fact a norm form from the quadratic field Q(j), and hence one can modify (not arbitrarily of course) the coefficients in the original question and still can solve it without changing the approach. – nguyen quang do Aug 5 '16 at 13:25