Find all primes $p$ such that $x^2 \equiv 13 \pmod p$

Question

I've took quadratic residues and found a problem solving this question. I searched for an answer and got a one, but it didn't convince me, maybe because the solver didn't put steps and analyze how to use theorems in such a question. Please help me!

Answer 1

This can be tackled by the law of quadratic reciprocity, which says: If $p, q$ are distinct odd primes then the two statements $$p {\rm\ is\ a\ quadratic\ residue\ of\ } q,\quad q {\rm\ is\ a\ quadratic\ residue\ of\ } p$$ are both true or both false, unless $p$ and $q$ are both congruent to 3 mod 4, in which case one statement is true and the other is false. In our case $q = 13$, which is not congruent to 3 mod 4, so 13 is a q.r. of an odd prime $p$ iff $p$ is a q.r. of 13, that is, iff $p$ is congruent to $\pm1, \pm 3$ or $\pm 4$ mod 13. Finally 13 is clearly a q.r. of $p = 2$.