# Find all primes $p$ such that $\left( \frac{-19}{p} \right) = 1$

Find all primes $p$ such that -19 is a quadratic residue $\bmod p$.

solution:

We have that $(\frac{-19}{p})=(\frac{p}{19})$, so that if $-19$ is a quadratic residue modulo $p$, then $p$ is a quadratic residue modulo $19$, i.e. when $p$ is congruent to any of $1,4,5,6,7,9,11,16,17 \mod 19$.

Can anyone give me an explanation why $p$ is a quadratic residue modulo $19$ implies that it must be congruent to any of these numbers modulo $19$?

By trial and error, the non-zero squares modulo $19$ are $$1^2=1,\ 2^2=4,\ 3^2=9,\ 4^2=16,\ 5^2=6,\ 6^2=17,\ 7^2=11,\ 8^2=7,\ 9^2=5,$$ and the rest are the same since $10^2=(-9)^2=9^2$ and so on. That is, any integer (whether prime or not) is a square modulo $19$ if and only if it is congruent to one of $$1,\,4,\,5,\,6,\,7,\,9,\,11,\,16,\,17.$$
• New to this. What does congruence mean? Like you said, how is 19 congruent to 1, 4, 5, etc.? Also, how is $9^2=5$? – Hamman Samuel Feb 25 '16 at 13:58
• @HammanSamuel Google "modular arithmetic". Also please read more carefully, I did not say $19$ is congruent to $1,4,5$ etc. – David Feb 25 '16 at 22:44
• @HammanSamuel The notation $a\equiv b \mod n$ (read out as "$a$ is congruent to $b\mod n$") means $n|(a-b)$. Equivalently, $a=qn+b$ for some $q\in\mathbb{Z}$. – P.D. Feb 25 '16 at 22:46