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$ – user3482749 Dec 6 '18 at 8:48
  • $\begingroup$ Maybe because for Legendre symbol be defined, $p \not = 13$ and $(p,13)=1$? $\endgroup$ – Alessar Dec 6 '18 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 '18 at 9:34

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 '18 at 9:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.