Exercise 3.2.7 (Find all $p$ such that $x^2 \equiv 13 \pmod p$)

Proof. This is true for $p=13$, because $0$ is a solution of the congruence $x^2\equiv 13(\mathit{mod}13)$.

Suppose now that $p\ne 13$. We search the primes $p\ne 13$ such that $\left(\frac{13}{p}\right)=1$. Since $13\equiv 1(\mathit{mod}4)$, the law of quadratic reciprocity shows that this is equivalent to

The quadratic residues modulo $13$ are $1,3,4,9,10,12$, thus $\left(\frac{p}{13}\right)=1$ is equivalent to $p\equiv 1,3,4,9,10,12(\mathit{mod}13)$. To conclude, $x^2\equiv 13(\mathit{mod}p)$ has a solution if and only if $p=13$, or $p\equiv 1,3,4,9,10,12(\mathit{mod}13)$.

(The first possible values of $p$, except $13$, are $p=3,17,23,29,43,53,61,79,101,103,107,113,\dots$) □