Euler's theorem generalizes Fermat's theorem to the case where the modulus is composite.

The key point of the proof of Fermat's theorem was that if p is prime, are relatively prime to p.

This suggests that in the general case, it might be useful to look at the numbers less than the modulus n which are relatively prime to n. This motivates the following definition.

* Definition.* The * Euler -function* is the function on positive integers
defined by

For example, , because there are eight positive integers less than 24 which are relatively prime to 24:

On the other hand, , because all of the numbers in are relatively prime to 11.

Here is a graph of for :

You can see that the function jumps around a little, but the data points are bounded above by the line . A point will be nearly on this line whenever n is prime, and since there are infinitely many primes, there will always be points near it.

Later, I'll derive a formula for computing in terms of the prime factorization of n.

* Proposition.*

(a) If p is prime, .

(b) If p is prime and , then .

(c) counts the elements in which are invertible mod n.

* Proof.* (a) If p is prime, then all of the
numbers are relatively prime to p. Hence,
.

(b) There are elements in . An
element of this set is * not* relatively prime to
p if and only if it's divisible by p. The elements of this set which
are divisible by p are

(Note that is the last element of the
set.) Thus, there are elements of the set which are
divisible by p, i.e. elements of the set which are * not* relatively prime to p. Hence, there are elements of the set which are relatively prime to p.

(The definition of applies to the set , whereas I just counted the numbers from 1 to . But this isn't a problem, because I counted in the set, but then subtracted it off since it was not relatively prime to p.)

(c) if and only if for some x, so a is relatively prime to n if and only if a is invertible mod n. Now is the number of elements in which are relatively prime to n, so is also the number of elements in which are invertible mod n.

* Definition.* A * reduced
residue system mod n* is a set of numbers

such that:

(a) If , then . That is, the a's are distinct mod n.

(b) For each i, . That is, all the a's are relatively prime to n.

Thus, a reduced residue system contains exactly one representative
for each number relatively prime to n. Compare this to a * complete residue system mod n*, which contains
exactly one representative to every number mod n.

As an example, is a reduced residue system mod 12. So is .

On the other hand, is a complete residue system mod 12.

* Lemma.* Let , and let be a reduced residue system mod n.

(a) For all m, is a reduced residue system mod n.

(b) If , is a reduced residue system mod n.

* Proof.* (a) This is clear, since for all i.

(b) Since , I may find x such that . Since , so I may find such that . Then , which proves that is invertible mod n. Hence, --- the 's are relatively prime to n.

Now if , then , or . Since the a's were distinct mod n, this is only possible of . Hence, the 's are also distinct mod n.

Therefore, is a reduced residue system mod n.

* Corollary.* Let , and let be a reduced residue system mod n. Suppose
, and let t be any integer. Then the following is a
reduced residue system mod n:

Here are some examples of these results. is a reduced residue system mod 6. Adding to each number, I get , another reduced residue system mod 6.

Since , I may multiply the original system by 25 to obtain , another reduced residue system.

Finally, is yet another reduced residue system mod 12.

* Theorem.* (Euler) Let , . Then

* Remark.* If n is prime, then , and Euler's theorem says , which is Fermat's theorem.

* Proof.* Let , and let be a reduced residue system mod n. I may
assume that the 's lie in the range .

Since , is another reduced residue system mod n. Since this is the same set of numbers mod n as the original system, the two systems must have the same product mod n:

Now each is invertible mod n, so multiplying both sides by , I get

As an example, , and . Hence, Euler's theorem says that .

Similarly, .

* Example.* Reduce to a number in the range .

Euler's theorem says that . So

* Example.* Solve .

Note that and . Therefore, . Multiply the equation by :

Now

So the solution is .

Copyright 2019 by Bruce Ikenaga