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
    Cool, I didn't know that! Wait...why is that true?2011-08-10
  • 0
    Oh okay, if it's not easy I'll go look it up myself. Thanks for the help!2011-08-10
  • 2
    @badatmath: An element $a\in\mathbb F_p$ is called a quadratic residue modulo $p$ if there exists $x\in F_p$ such that $x^2\equiv a$ (mod $p$). Many number theory texts will tell you that $-1$ is a quadratic residue modulo $p$ ($p$ odd) if and only if $p\equiv 1$ (mod $4$). E.g., see Theorem 9-1 on [page 116](http://books.google.com/books?id=eVwvvwZeBf4C&lpg=PA116&pg=PA116#v=onepage&q&f=false) of Andrews's *Number theory*.2011-08-10
  • 0
    Oh okay, thanks :) I haven't taken that class yet. I'll go look at Jonas' reference.2011-08-10
  • 0
    @André There's no need to refer to a textbook since the proof is quite easy - see my answer.2011-08-10
  • 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.

  • 4
    Unfortunately, I have not learned to be compact. Have been admiring your posts.2011-08-10
  • 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.$