3.3: Multiplicative Order and Applications - Mathematics

In this section we prove two very useful results called Euler’s Theorem and Fermat’s Little Theorem (a special case of Euler’s). We do not follow the proof strategy of Euler and Fermat, however, instead using an approach inspired by abstract algebra and Lagrange’s Theorem in that subject.

First we need the

[def:multorder] Suppose (ninNN) and (ainZ) satisfy (nge2) and (gcd(a,n)=1). Then we define the multiplicative order of (a) in mod (n) (called just the order when the multiplicative and (n) can be understood from context) to be the smallest (kinNN) such that (a^kequiv1pmod{n}). The order of (a) in mod (n) is written (ord_n(a)).

Let us verify something which should probably always be checked for a new definition:

[prop:orderwelldefined] Given relatively prime numbers (ninNN) and (ainZ) with (nge2), (ord_n(a)) is well-defined.

The problem in the definition of (ord_n(a)) might be that there might not be any value of (kinNN) at all for which (a^kequiv1pmod{n}).

But notice that this is a congruence, so we are really only concerned with the elements (a^k) up to their congruence class.

So look at ({[a^p]_nmid pinNN}) and imagine putting the natural numbers (pinNN) into different boxes based on what is the corresponding congruence class ([a^p]inZ/nZ). Since there are infinitely many elements in (NN) and only (n) elements in (Z/nZ) – (n) boxes – by the Pigeonhole Principle (Theorem [thm:pigeonhole]) there must be two (actually, infinitely many pairs of) distinct values (p,qinNN) such that (p) and (q) end up in the same box, meaning ([a^p]=[a^q]). Assume without loss of generality that (p>q), so (p-qinNN).

We are given that (gcd(a,n)=1), so by Corollary [cor:modinv], (a^{-1}) exists in mod (n). Thus [a^{p-q}equiv a^p,(a^{-1})^qequiv a^q,(a^{-1})^qequiv a^0equiv1pmod{n}] (replacing (a^p) with (a^q) in the middle of this congruence since we know that ([a^p]=[a^q]), which means (a^pequiv a^qpmod{n})) and therefore the set of (kinNN) for which (a^kequiv1pmod{n}) is non-empty. The order is the smallest such value, which exists by the Well-Ordering Principle.

Here now is a theorem from abstract algebra (Lagrange’s Theorem) translated into the current context:

[thm:orddividesphi] Given relatively prime numbers (ninNN) and (ainZ), (ord_n(a)midphi(n)).

Start by looking at the congruence classes ([a],[a^2],[a^3]dots). They go up to ([a^{ord_n(a)}]=[1]) and then start to repeat, so the set [left={[a^j]mid jinNN, jleord_n(a)}] is a set of (ord_n(a)) elements of (Z/nZ) (in group theory, this set (left) is called the cyclic subgroup of ((Z/nZ)^*) generated by (a)). Notice that because (a^{ord_n(a)}equiv1pmod{n}), ([1]inleft). Also, since if (a^{-1}) is the inverse of (a) mod (n), ((a^{-1})^k) is the inverse of (a^k) for (kinNN), we see that (leftsubseteq(Z/nZ)^*).

That was a lot of work, but now we get the famous theorems of Fermat’s Little and of Euler very easily.

[thm:eulers]Euler’s Theorem Say (ainZ) and (ninNN) satisfy (gcd(a,n)=1). Then (a^{phi(n)}equiv1pmod{n}).

The previous theorem, [thm:orddividesphi], told us that (ord_n(a)midphi(n)), so (exists minZ) such that (mcdotord_n(a)=phi(n)). By the definition of order, this means [a^{phi(n)}equiv a^{mord_n(a)}equivleft(a^{ord_n(a)} ight)^mequiv1^mequiv1pmod{n} .]

[cor:FLT]Fermat’s Little Theorem If (p) is a prime and (ainZ) satisfies (gcd(p,a)=1) then (a^{p-1}equiv1pmod{p}).

We have seen that for primes (p), (phi(p)=p-1), so there is very little to do here.

Sometimes one sees Fermat’s Little Theorem in the following, different form:

[thm:altFLT] If (p) is a prime then (forall ainZ), (a^pequiv apmod{p}).

If (gcd(a,p)=1), then by Fermat’s Little, (a^{p-1}equiv1pmod{p}). Multiplying both sides of this congruence by (a) yields the desired result.

If instead (gcd(a,p) eq1), it must be that (gcd(a,p)=p) since that gcd is a divisor of (p), which is prime. The gcd is also a divisor of (a), so in fact (pmid a). But then (a) and all its powers are congruent mod (p) to (0), so (a^pequiv0equiv apmod{p}).

Exercises for §3

What are the remainder when (15!) is divided by (17) and the remainder when (2cdot(26!)) is divided by (29)?

We know (17) is prime (it’s just a wonderful number, isn’t it?). But just to be sure, use Wilson’s Theorem to prove it.

Can we build a test for primality out of Fermat’s Little Theorem? If so, would it be better (more efficient) than one based on Wilson’s Theorem? How would it work? Write a clear, formal statement of your proposed primality test.

If you know a programming language, write some code to try out your primality test. If not (or, in any case, after the programming), do a little research to see if this question has already been investigated and, if so, what was the conclusion. Give either a formal statement of the test and formal result describing its efficacy or a counter-example to your test that you found in the literature.

Suppose (p) is an odd prime. Prove that if the quadratic congruence (x^2+1equiv0pmod{p}) has a solution, then (pequiv1pmod{4}). [Hint: Apply Fermat’s Little Theorem to a solution (a) of the congruence, then multiply and divide by (2) in the power.]