-2

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.

Electiwirez
  • 11
  • Where did you declare the variable n? – Jesse Meng Mar 07 '18 at 00:05
  • sorry I just fixed it I meant x – Electiwirez Mar 07 '18 at 00:06
  • 1
    @Electiwirez: Does this look like a homework solving website to you? At least provide some context like what have you tried, where did you get stuck, etc. How can you expect others to help you when you don't show any effort to solve your own problem? – Prasun Biswas Mar 07 '18 at 00:08
  • @PrasunBiswas I don't understand how to approach the problem. I just need some sort of starter and then I can probably solve the rest. – Electiwirez Mar 07 '18 at 00:10
  • You might start thinking about what $x^2+x+1$ is, when $x$ is a positive integer. In particular, is it an odd or an even number? – Gibbs Mar 07 '18 at 00:12
  • consider the group $\mathbb Z_p^\times$ This group has some element $x$ such that $1,x, x^2$ form a subgroup. What does this say about the order of the group? – Doug M Mar 07 '18 at 00:13
  • @Gibbs I don't see the way to use your hint for a solution. Yeah, by your hint we can eliminate $p=2$, but how do you use it to find other primes? – Levent Mar 07 '18 at 00:16
  • Any other prime is an odd number... – Gibbs Mar 07 '18 at 00:16
  • @Gibbs Wait but if a number is odd or even it gives me an odd number... like 3, 6, 5, 4 – Electiwirez Mar 07 '18 at 00:19
  • @Gibbs What were you trying to get to? – Electiwirez Mar 07 '18 at 00:29
  • @Gibbs I still don't see. Yeah any other prime is odd, so they may or may not divide $x^2+x+1$? – Levent Mar 07 '18 at 00:30
  • I was actually trying to make you think about the numbers $x^2+x+1$, which are odd. So prime numbers of the form $x^2+x+1 < 100$ fit, and you get at least some first results. About the others, I would do a more abstract reasoning like the one in the answer of AlkaKadri. – Gibbs Mar 07 '18 at 00:39

2 Answers2

1

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.

AlkaKadri
  • 2,130
0

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

Bernard
  • 175,478