Theorem 39: Euler’s criterion

I’ve previously written about Fermat’s Little Theorem, which tells us that if p is a prime and a is not divisible by p, then a^{p-1} \equiv 1 \pmod{p}.  That’s not terribly exciting when p = 2, so let’s concentrate on odd primes p in this post.  Then \frac{p-1}{2} is a whole number, so it makes sense (in the modular arithmetic world) to let x = a^{\frac{p-1}{2}}.  Then Fermat‘s Little Theorem tells us that x^2 \equiv 1 \pmod{p}.

How many possibilities for x are there (modulo p, of course), if we know that x^2 \equiv 1 \pmod{p}?

Well, that congruence tells us that (x - 1)(x + 1) \equiv 0 \pmod{p}.  But, in the jargon, “there are no zero-divisors modulo a prime”.  That is, if mn \equiv 0 \pmod{p}, then m \equiv 0 \pmod{p} or n \equiv 0 \pmod{p}.  (Note that we really do need p to be prime here — try some examples!)

So if x is such that x^2 \equiv 1 \pmod{p}, then x \equiv \pm 1 \pmod{p}.  Which is pretty nice.  (Again, we really needed p to be prime here.  Try working modulo 8 instead, and see what happens there!)

Back to where we started.  We said that if a is not divisible by the odd prime p, then (a^{\frac{p-1}{2}})^2 \equiv 1 \pmod{p}, so we know know that a^{\frac{p-1}{2}} \equiv \pm 1 \pmod{p}.

That narrows down the possibilities a lot.  It’s no good trying to tell me that 19^{50} \equiv 7 \pmod{101} — I simply shan’t believe you (even without doing any calculations).  But tell me that 19^{50} \equiv 1 \pmod{101}, or that 19^{50} \equiv -1 \pmod{101}, 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 p be an odd prime, and let a be coprime to p.  Then a^{\frac{p-1}{2}} \equiv \genfrac{(}{)}{}{}{a}{p} \pmod{p}.

Here the symbol on the right-hand side of the congruence is the Legendre symbol.

So not only is a^{\frac{p-1}{2}} certainly congruent to 1 or -1 modulo p, but we can tell which — it just depends whether or not a is a quadratic residue modulo p.

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 p.  That is, there is some g such that each non-zero number modulo p is a power of g.

How does that help?  Well, our number a is coprime to p, so we must have a \equiv g^r \pmod{p} for some r.  Now a^{\frac{p-1}{2}} \equiv g^{r(\frac{p-1}{2})} \pmod{p}.  So we have a^{\frac{p-1}{2}} \equiv 1 \pmod{p} if and only if p-1 divides r(\frac{p-1}{2}) (using the fact that g has order p-1).  And we can check that this happens if and only if r is even.  But that’s exactly the criterion for g^r to be a quadratic residue, and so we’re done.

Alternatively, we could think about the polynomial X^{\frac{p-1}{2}} - 1 modulo p.  A theorem of Lagrange (an analogue of the fundamental theorem of algebra) tells us that this has at most \frac{p-1}{2} roots modulo p.  The same applies to the polynomial X^{\frac{p-1}{2}} + 1 modulo p.  But we have p-1 values that satisfy one or other of these polynomials, so in fact they must each have \frac{p-1}{2} roots.  But if a is a quadratic residue modulo p, then a \equiv b^2 \pmod{p} for some b and so a^{\frac{p-1}{2}} \equiv b^{p-1} \equiv 1 \pmod{p}, so the \frac{p-1}{2} quadratic residues modulo p must be the \frac{p-1}{2} roots of the polynomial X^{\frac{p-1}{2}} - 1 modulo p.

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 p is an odd prime then -1 is a quadratic residue modulo p if and only if p \equiv 1 \pmod{4}.

It also has relevance in the field of primality testing.  We say that n is an Euler pseudoprime to the base b if it `behaves like a prime’ as far as Euler’s criterion is concerned: if b^{\frac{n-1}{2}} \equiv \genfrac{(}{)}{}{}{b}{n} \pmod{n}.  It turns out that if n is an odd composite number then n 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).

Further reading

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

6 Responses to “Theorem 39: Euler’s criterion”

  1. Number Theory: Lecture 6 « Theorem of the week Says:

    […] 20 (Euler‘s criterion): Let be an odd prime, and let be an integer.  Then .  This is interesting only when is […]

  2. Gareth Says:

    I always liked the following proof of Euler’s Criterion, as it is very much like the standard proof of Wilson’s Theorem, so it’s easy to remember and recreate. Say that x and y are “associates” if xy = a. Clearly each x has a unique associate, and there are two self-associate elements if a is a quadratic residue (assuming p>2), and none otherwise.

    We multiply out (p-1)!, which is congruent to -1 by Wilson’s Theorem. If a is not a quadratic residue then in the product we get all p-1 numbers pairing up with their associates, that is (p-1)/2 copies of a, and so a^{(p-1)/2} \equiv -1.

    On the other hand, if a is a quadratic residue, say with x^2 \equiv a, then in the product we get p-3 numbers pairing up with their associates, along with \pm x not pairing up. So the product is a^{(p-3)/2}(-x)(x) \equiv a^{(p-3)/2}(-a) \equiv -a^{(p-1)/2}, and so a^{(p-1)/2} \equiv 1.

  3. Luis Guzman Says:

    Reblogged this on Guzman's Mathematics Weblog and commented:

  4. Theorem 41: Gauss’s lemma « Theorem of the week Says:

    […] going to write this post on the assumption that you know about Fermat’s little theorem and Euler’s criterion.  Fortunately, those links take you to places on this blog where you can read everything you need […]

  5. Number Theory: Lecture 6 | Theorem of the week Says:

    […] Theorem 20 (Euler’s criterion): Let be an odd prime, and let be an integer.  Then .  We proved this by first showing that and then using Lagrange’s theorem to show that the even powers of a primitive root ‘use up’ all the possible solutions to . […]

  6. Number Theory: Lecture 7 | Theorem of the week Says:

    […] Proposition 23 (Gauss‘s Lemma): Let be an odd prime, and let be coprime to .  Then , where .  We proved this by showing that , , …, correspond to , , …, in some order, where each of these has a definite sign, and then multiplying them all together to show that .  Then we finished off using Euler’s criterion. […]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: