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
• Thanks for the answer, that helps a lot! @David, given that this is a question answering forum, I expect to get clearer answers here than going on search engines. Furthermore, I do have an understanding of modular arithmetic. Congruence is a specific term, I've searched for it's meaning and examples. Honestly, wour feedback is not constructive. – Hamman Samuel Feb 26 '16 at 4:33
• @HammanSamuel since this is a voluntary question answering forum, I think you should just pass by anything that is not up to your high standards. If you want specific tuition you should be prepared to find a teacher and pay for their help. – David Feb 26 '16 at 5:32