Section16.5Euler's Criterion

However, this 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 about the square root of Fermat's Little Theorem: \[a^{(p-1)/2}\equiv\pm 1\text{ for all }a\text{ not divisible by }p\; .\] We visualized it as the middle column here.

We can extend this in a different direction; after all, we didn't say when we got plus or minus 1. Let's extend this as follows.

Example16.5.2

Notice that this immediately gives our old result 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.

Hence if one of \(a,b\) is and the other isn't, neither is \(n=ab\).

Example16.5.4

Now I can immediately decide that \(-2\equiv 21\) is not a QR mod (23) by the fact 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.