I’ve previously written about Fermat’s Little Theorem, which tells us that if is a prime and is not divisible by , then . That’s not terribly exciting when , so let’s concentrate on odd primes in this post. Then is a whole number, so it makes sense (in the modular arithmetic world) to let . Then Fermat‘s Little Theorem tells us that .
How many possibilities for are there (modulo , of course), if we know that ?
Well, that congruence tells us that . But, in the jargon, “there are no zero-divisors modulo a prime”. That is, if , then or . (Note that we really do need to be prime here — try some examples!)
So if is such that , then . Which is pretty nice. (Again, we really needed to be prime here. Try working modulo 8 instead, and see what happens there!)
Back to where we started. We said that if is not divisible by the odd prime , then , so we know know that .
That narrows down the possibilities a lot. It’s no good trying to tell me that — I simply shan’t believe you (even without doing any calculations). But tell me that , or that , and I have a problem — how do I know which is correct?
This is where Euler‘s criterion comes in. I think that I’ll just state it now, and then say a little about how one might prove it afterwards.
Theorem (Euler’s Criterion) Let be an odd prime, and let be coprime to . Then .
Here the symbol on the right-hand side of the congruence is the Legendre symbol.
So not only is certainly congruent to 1 or -1 modulo , but we can tell which — it just depends whether or not is a quadratic residue modulo .
Looking at this another way, it gives us a way to compute the Legendre symbol (which appears slightly mysterious) — it’s just a suitable power. That can be very useful indeed.
How might we try to prove this? I’ll outline two approaches here, each using a bit of background theory.
One approach would be to make the most of the last Theorem of the Week, which tells us that there is a primitive root modulo . That is, there is some such that each non-zero number modulo is a power of .
How does that help? Well, our number is coprime to , so we must have for some . Now . So we have if and only if divides (using the fact that has order ). And we can check that this happens if and only if is even. But that’s exactly the criterion for to be a quadratic residue, and so we’re done.
Alternatively, we could think about the polynomial modulo . A theorem of Lagrange (an analogue of the fundamental theorem of algebra) tells us that this has at most roots modulo . The same applies to the polynomial modulo . But we have values that satisfy one or other of these polynomials, so in fact they must each have roots. But if is a quadratic residue modulo , then for some and so , so the quadratic residues modulo must be the roots of the polynomial modulo .
Why is Euler’s criterion a good thing? Partly, of course, because it’s intrinsically interesting in its own right. But also it can be applied to a bunch of number theory problems. One quick consequence, for example, is the fact that if is an odd prime then is a quadratic residue modulo if and only if .
It also has relevance in the field of primality testing. We say that is an Euler pseudoprime to the base if it `behaves like a prime’ as far as Euler’s criterion is concerned: if . It turns out that if is an odd composite number then is an Euler pseudoprime to at most half of all possible bases, and this gives rise to the Solovay-Strassen primality test. This is very different from the situation for Fermat pseudoprimes, where there are Carmichael numbers (numbers that cannot be distinguished from primes just using this notion of a pseudoprime).
This is another result that occurs in introductory number theory books such as The Higher Arithmetic by Davenport, and A concise introduction to the theory of numbers by Baker (to name but two examples).