However, Fact 16.4.4 is a terrible way to actually find quadratic residues for a given \(p\), since it involves finding a primitive root and listing lots of powers! We need both theory and practice.
Here is a much easier way. Recall our observation in Theorem 12.3.1: \begin{equation*}a^{(p-1)/2}\equiv\pm 1\text{ for all }a\text{ not divisible by }p\; .\end{equation*} We visualized it as the middle column in this graphic.
But as so often in mathematics, solving one question leads to another; after all, we didn't say when we got plus or minus 1, just that these are the only possibilities. Let's extend this as follows.
If \(p\) is an odd prime, then for all integers \(a\) not a multiple of \(p\), the sign of the following expression determines whether \(a\) is a QR. \begin{equation*}a^{(p-1)/2}\equiv\pm 1\text{ (mod }p)\end{equation*} We obtain \(+1\) if \(a\) is a QR, otherwise \(-1\).
This immediately gives the result in Fact 16.1.2 that \(-1\) has a square root modulo an odd prime \(p\) precisely when \(p\equiv 1\) (mod \(4\)), because \((-1)^{(p-1)/2}=+1\) precisely when \((p-1)/2\) is even, or \(p\equiv 1\) (mod \(4\)). That is much easier than our previous ad-hoc way of doing it!
Using this same idea, we can prove a very nice result about when a composite number is a QR.
If \(n=ab\) is a factorization (not necessarily nontrivial) of \(n\), then \(n\) is a QR of \(p\) precisely when either both \(a\) and \(b\) are QRs of \(p\) or both \(a\) and \(b\) are not QRs of \(p\).
Hence if one of \(a,b\) is and the other isn't, neither is \(n=ab\).
Now I can immediately decide that \(-2\equiv 21\) is not a QR (mod \(23\)). Why? First, \(-2\equiv 21\); then recall that \(-1\) is not a QR but 2 is, which we knew before. Likewise, I can immediately decide that \(-2\equiv 9\) is a QR (mod \(11\)) by the fact that neither \(-1\) nor \(2\) is a QR.
