$x^2-x+1$ has a root $\!\bmod p\,$ for infinitely many primes $p$

Question

Prove that the equation $$x^2 - x + 1 = p(x+y)$$ has integral solutions for infinitely many primes $p$.

First, we prove that there is a solution for at least one prime, $p$. Now, $x(x-1) + 1$ is always odd so there is no solution for $p=2$. We prove there is a solution for $p=3$. If $p=3$, $y = (x-2)^2/3-1$. We get integral solutions whenever we get $x = 3m +2$, where $m$ is any integer.$\\$ We provide a proof by contradiction which is similar to Euclid's proof of there being infinitely many primes. \Let us assume that it is is true for only finitely many primes, and name the largest prime for which the equation is true $P$.\\We set $$x = 2\cdot3\cdot5\dots P$$ $x$ is the product of all primes upto $P.\\$ Then, the term $x(x-1) + 1$ is either prime or composite. If it is prime, then we set $p = x(x-1) + 1, y = 1 - x$ and get a solution. If it is composite, we write $x(x-1) + 1 = p\times q$, where $p$ is any prime factor of $x(x-1)+1$, and $q$ is an integer, $q = (x(x-1)+1)/p$. Now, $x(x-1) + 1$ is not divisible by any prime upto $P$ since it leaves a remainder of $1$ with all of them. So, $p > P$. We set $y=q-x$ for a solution.$\\$In either case, we get a solution for a prime $p > P$, which means there's no largest prime for which this equation has solutions. This contradicts the assumption that there are solutions for only finitely many primes.

I feel like I'm missing some step. Is this correct ?

Answer 1

This answer uses Quadratic Reciprocity (QR).

$$x^2 - x + 1 = p(x+y)$$

$$\iff x^2-x+1-px=py$$

for a fixed $x\in\mathbb Z$ and prime $p$ has a solution $y\in\mathbb Z$ if and only if $p\mid x^2-x+1-px$, i.e. if and only if $p\mid x^2-x+1$.

Your problem is equivalent to proving that $p\mid x^2-x+1$ has a solution $x\in\mathbb Z$ for infinitely many primes $p$.

Let $p\ge 5$. $$\exists x\in\mathbb Z\left(x^2-x+1\equiv 0\pmod{p}\right)$$

$$\stackrel{\cdot 4}\iff \exists x\in\mathbb Z\left((2x-1)^2\equiv -3\pmod{p}\right)$$

$$\stackrel{(*)}\iff \left(\frac{-3}{p}\right)=1$$

$$\stackrel{(\text{QR})}\iff p\equiv 1\pmod{3}$$

$(*)$: I'll explain a few things. Firstly, I'm using the Legendre Symbol. Secondly, the equivalence holds because if $t^2\equiv -3\pmod{p}$ for some $t\in\mathbb Z$ (i.e. if $-3$ is a quadratic residue mod $p$), then the congruence $t\equiv 2x-1\pmod{p}$ has the solution $x\equiv 2^{-1}(t+1)\pmod{p}$.

Therefore your equation has a solution $(x,y)\in\mathbb Z^2$ if and only if either $p=3$ or $p\equiv 1\pmod{3}$ ($p=3$ gives a solution $(x,y)=(2,-1)$ and you can find that $p=2$ gives no solutions, because $x^2-x=x(x-1)$ is always even).

There are infinitely many primes $p\equiv 1\pmod{3}$. It follows from the more general Dirichlet's Theorem or from a simpler proof that only uses QR, e.g. the one given in the last page of this paper.

Answer 2

Assumptions

$$0\notin\mathbb N\\n\in\mathbb N$$

$x^2-x+1$ is composite for infinitely many $x\in\mathbb N$

Proof: $$ x=3n+2\implies x^2-x+1=\color{red}{3}\times(3n^2+3n+1) $$

There are infinitely many primes that can divide natural numbers of form $x^2-x+1$.

Proof: Suppose our claim is not true and in fact $q_1=\color{red}{3},q_2,\cdots,q_k$ are the only primes that can divide a natural number of form $x^2-x+1$. Borrowing Euclid's argument let $$n=\prod_{j=1}^kq_j\\ x=3n+2$$ Therefore, $x^2-x+1$ is not a prime and $$ x^2-x+1\equiv3\not\equiv0\mod q_j\;\forall j\neq1\\ \implies q_j\not| x^2-x+1\;\forall j\neq1 $$ Therefore our assumption and the fundamental theorem of arithmatic indicate, for some $q\in\mathbb N$ $$\begin{align} &x^2-x-1=\color{red}{3}^q \\ \implies& 3n^2+3n+1=3^{q-1}\\ \implies& 1\equiv 3^{q-1}\mod 3\\ \implies& q=1\\ \implies& x^2-x+1=3 \end{align} $$ which contradicts $$ x^2-x+1>(x-1)^2=(3n+1)^2\ge(3q_1+1)^2=100 $$

Solution to the current problem

Suppose $p_1,p_2,\cdots,p_m$ are the only primes for which integral solution exists. Using the above lemma we can find a prime $p$ not in this list such that $p| x^2-x+1$ for some $x\in\mathbb N$. Set $$ y={x^2-x+1\over p}-x $$ which is definitely an integer (but not necessarily a natural number). Thus we have found a new prime $p$ for which an integral solution to the given equation exists. Therefore, our assumption that the given equation has integral solutions for finitely many choices of $p$ can't be true.

Answer 3

Euclid's proof of infinitely many primes easily generalizes to show that infinitely many primes divide values of $\,f(x) = x^2 -x + 1.\,$ First $\,3\mid f(2).\,$ Given primes $\,3,p_2,\ldots\,p_k\,$ that divide values of $\,f,\,$ let $\,k\,$ be their product. $\,f(k)\,$ is coprime to $\,k\,$ since $\ {\rm mod}\ k\!:\ f(k) \equiv f(0)\equiv 1.\,$ Thus choosing any prime factor of $\,f(k)\,$ yields a new prime divisor (note $\,k>1\,$ $\Rightarrow\,$ $\,f(k)>1\,$ so $\,f(k)\,$ does have a prime factor).

Clearly the same type of argument works for any polynomial $\,f(x)\in\Bbb Z[x]\,$ with $\,f(0) = \pm1$.