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.

Theorem16.5.1Euler's Criterion

If \(p\) is an odd prime, then for all integers \(a\) not a multiple of \(p\) the sign of the following determines whether \(a\) is a QR; \[a^{(p-1)/2}\equiv\pm 1\text{ mod }(p)\, ,\] with \(+1\) if \(a\) is a QR, otherwise \(-1\).

Proof

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.

Proposition16.5.3

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\).

Proof

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.