Number of primes that can divide ...

Question

Find the number of primes $p$ less than $100$ such that $p$ divides $x^2+x+1$ for some positive integer $x$. I do not understand how to approach this problem. Is there a formula I need to use? I don't need the answer.

Answer 1

You can solve the problem with the law of quadratic reciprocity.

Note that $2$ never divides $x^2+x+1$, so we restrict our attention to odd primes.

An odd prime $p$ divides $x^2+x+1$ for some natural number $x$ means this quadratic polynomial has a root mod. $p$, and this is the case if and only if its discriminant $-3$ is a square mod. $p$. Computing with the Legendre's symbol, we have $$\biggl(\frac{-3}p\biggr)=\biggl(\frac{-1}p\biggr)\biggl(\frac{3}p\biggr)=(-1)^{\tfrac{p-1}2}\cdot\biggl(\frac{p}3\biggr)(-1)^{\tfrac{p-1}2}=\biggl(\frac{p}3\biggr).$$ Thus the discriminant is a square mod. $p$ if and only if $p$ is a square mod. $3$. Now $p$ is a square mod. $3$ if it is either $3$ or if $p\equiv 1\mod 3$. Therefore the list of these primes is

$$ \bigl\{\,3,\,13,\,19,\,31,\, 37,\,43,\, 47,\,53,\,59,\,71,\,83,\,89\,\bigr\}. $$

Answer 2

If $p \vert(x^2 + x + 1)$, then $\exists k \in \mathbb{Z}$ such that \begin{align} x^2 + x + 1 &= kp\\ \Rightarrow x^2 + x + (1 - kp) &= 0\\ \Rightarrow x &= \frac{-1 \pm \sqrt{1 - 4(1 - kp)}}{2}\\ &= \frac{-1 \pm \sqrt{-3 + 4kp}}{2} \end{align} Hence, $(-3 + 4kp)$ must be a perfect square in order for $x$ to be an integer. Similar to what others have said, that means that we must have that $-3$ is a quadratic residue modulo $p$.

You then need to go through the primes one by one and verify this. For example, for $p = 5$ we have $$ \left(\frac{-3}{5} \right) = \left(\frac{2}{5} \right) = -1$$ (using the law of quadratic reciprocity)

So $p = 5$ will not divide $x^2 + x + 1$ for any positive $x \in \mathbb{Z}$.

For $p = 7$, however, $$ \left(\frac{-3}{7} \right) = \left(\frac{4}{7} \right) = \left(\frac{2}{7} \right)^2 = 1$$ Hence, $\exists x \in \mathbb{Z}$ such that $7$ divides $x^2 + x + 1$. Indeed, $x = 2, 4,$ and $9$ all do the trick.

I'd recommend writing a program or using an online Legendre Symbol Calculator to compute each Legendre symbol one by one.