Question: How can you generalize Fermat's theorem to the case where the modulus is composite?
Idea: 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
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.
(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. 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
(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.
Example. is a reduced residue system mod 12. So if .
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
is a reduced residue system mod n.
Example. 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 : the little Fermat 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
Example. , and . Hence, --- surely not an obvious fact!
You can also use Euler's theorem to compute modular powers. Suppose I want to find . Mathematica tells me that is
I probably don't want to do this by hand!
Euler's theorem says that . So
Example. Solve .
Note that and . Therefore, . Multiply the equation by :
So the solution is .
Bruce Ikenaga's Home Page
Copyright 2008 by Bruce Ikenaga