I'm analyzing this little problem:

Find all primes $p$ : $x^2 \equiv 13 \pmod p$ has solutions

Here my effort since now:

If the congruence $x^2 \equiv 13 \pmod p$ has solutions, must be the Legendre symbol $(13/p) = 1$. Therefore using quadratic reciprocity $(13/p) = (p/13)(-1)^{(13-1)(p-1)/4}$. I assume that must be $(p/13) = 1$ therefore the second part must be $+1$. Let's see.

Here $(-1)^{(13-1)(p-1)/4}=1$ iif $(13-1)(p-1)/4 = 2k, k \in \mathbb{Z}^+ $.

$(13-1)(p-1)/4 = 2k \rightarrow 3p-3=2k \rightarrow p \equiv 1 \pmod 2$.

But this seems strange to me. What am I doing wrong?

I wish also to be able to understand this result using group theory, I'm starting it now and it'll be useful to start using it.


  • 1
    $\begingroup$ > I assume that must be $(p/13)=1$ therefore the second part must be $+1$. OK, general rule here: if you feel the need to use the word "assume" and you aren't writing either a proof by contradiction or are planning on proving that assumption later, something's wrong, and you should either justify your assumption, or change something fundamental. In this case, you've proven that if $(p/13) = 1$, then $p \equiv 1 \pmod 2$. Why must we have $(p/13) = 1$? $\endgroup$ Dec 6, 2018 at 8:48
  • $\begingroup$ Maybe because for Legendre symbol be defined, $p \not = 13$ and $(p,13)=1$? $\endgroup$
    – Alessar
    Dec 6, 2018 at 8:55
  • $\begingroup$ It's because the exponent is always even, for every prime, so the two Legendre symbols are equivalents $\endgroup$
    – Alessar
    Dec 6, 2018 at 9:34

1 Answer 1


There is nothing wrong. You have shown that $(13-1)(p-1)/4$ is even for every odd prime $p$, so $(13/p)=(p/13)$.

Therefore, it suffices to find the squares mod $13$. Don't forget the trivial cases $p=2$ and $p=13$.

  • $\begingroup$ I think I've solved, so $p=2,11,13$? If it's correct, I'll update also my question with the right explanation. $\endgroup$
    – Alessar
    Dec 6, 2018 at 9:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .