5
$\begingroup$

I'm trying to show that there are infinitely many values of $p$ such that $x^2 + 2x + 2$ has no roots over $\mathbb{F}_p$. Is this easily solvable? (I kind of came up with it myself so I don't know.)

Thanks!

3 Answers 3

16

It is straightforward if you know some theory. I assume that by $\mathbb{F}_p$ you mean the integers modulo $p$.

Your equation has a solution in $\mathbb{F}_p$ iff $(x+1)^2\equiv -1\pmod{p}$ has a solution.

For odd primes $p$, the congruence $y^2 \equiv -1\pmod{p}$ has a solution iff $p\equiv 1\pmod{4}$.

So for primes of the form $4k+3$, there is no solution.

An argument much like the usual "Euclid" proof shows there are infinitely many primes of the form $4k+3$. Indeed in a precise sense, half the primes are of this type. So there are infinitely many primes for which your equation has no solution.

Proof of the characterization of the primes for which $y^2\equiv -1 \pmod{p}$ can be found in any beginning book on Number Theory.

  • 0
    Though, asymptotically, there are the same number of primes of the form 4n+1 as 4n+3, there are usually more of the form 4n+3. Look up "prime number races".2011-12-27
11

HINT $\ $ Quadratic Formula $\rm\:\Rightarrow\ x = -1 \pm\sqrt{-1}\ $ but $\rm\:\sqrt{-1}\not\in\mathbb F_p\:$ for primes $\rm\:p = 4\:k+3 \:$ else

$\qquad\qquad\ \rm a^2 = -1\ \Rightarrow\ a^{p-1}\ =\ (a^2)^{2\:k+1}\ \equiv\ {-}1\pmod{p}\ \ $ contra Fermat's Little Theorem.

NOTE $\ $ For more on the underlying group theory see here.

  • 0
    Thank you, that was a very clear solution!2011-08-10
3

I would give a slightly different group theoretic perspective. If $F$ is the field of $p$ elements and $p$ is an odd prime, then the multiplicative group of non-zero elements of $F$ has order $p-1.$ If there is an element $a \in F$ such that $a^2 = -1,$ then $a^4 =1$ and the cyclic group $\langle a \rangle$ has order $4.$ By Lagrange's theorem, $4$ divides $p-1,$ so $p$ has the form $4k+1$ for some integer $k.$