0
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Hamman Samuel Feb 25 '16 at 13:58
  • $\begingroup$ @HammanSamuel Google "modular arithmetic". Also please read more carefully, I did not say $19$ is congruent to $1,4,5$ etc. $\endgroup$ – David Feb 25 '16 at 22:44
  • $\begingroup$ @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}$. $\endgroup$ – P.D. Feb 25 '16 at 22:46
  • $\begingroup$ 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. $\endgroup$ – Hamman Samuel Feb 26 '16 at 4:33
  • $\begingroup$ @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. $\endgroup$ – David Feb 26 '16 at 5:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.