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

Question

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.

Thanks

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