Typically, we start with conjectures and try to prove them. In this case, we take a different approach. We will provide the basis for a proof, and you will need to see what sort of statement it leads to for the theorem. The theorems which result are known as Fermat's Little Theorem and Euler's generalization. Our goal is to answer the following question:
Given an integer n, can we produce another positive integer m such that am
1 (mod n) for all integers a that have an order?
Note that this would imply that such an m is a period (although not necessarily minimal) for the powers of a mod n for all a that have an order.
Let's look at an example. We will work with powers of 2 modulo 15. In this computation, we will deal with the set of integers between 1 and n which are relatively prime to n. Since this set will appear in the course later, we will give its usual notation here:
Definition The multiplicative group modulo n, denoted Zn*, is the set of elements of Zn which are relatively prime to n. The number of integers in Zn* is denoted by
(n).
In our example of n = 15, Z15* is
1, 2, 4, 7, 8, 11, 13, 14.
An interesting thing happens if we multiply every element of Zn* by a. Here's what we get with n = 15 and a = 2:
2, 4, 8, 14, 16, 22, 26, 28.
Since we are working modulo n, let's reduce the entire list modulo n = 15:
2, 4, 8, 14, 1, 7, 11, 13.
Looking closely, we recognize that these are the elements of Z15*, but listed in a different order. It's easier to see this if we sort them:
1, 2, 4, 7, 8, 11, 13, 14.
As you can see, we can produce the elements of Zn* in a new way, namely by multiplying by a. We can exploit this observation by taking the product over both sets. Starting with the product of the elements of Z15* each multiplied by a (= 2 in this case), we have:
(1) (2 · 1) · (2 · 2) · (2 · 4) · (2 · 7) · (2 · 8) · (2 · 11) · (2 · 13) · (2 · 14).
Rather than multiply everything out, we instead factor out a 2 from each term:
28 · (1 · 2 · 4 · 7 · 8 · 11 · 13 · 14).
On the other hand, we observed above that the terms of the product in equation (1) are congruent to the elements of Zn* (after reordering them). Hence it follows that
28 · (1 · 2 · 4 · 7 · 8
· 11 · 13 · 14) 1 · 2 · 4 · 7 · 8
· 11 · 13 · 14 (mod 15).
We can cancel the equal terms from each side (why?), to find that
28 1
(mod 15).
Let's check this last congruence:
Now, it is your turn. Try to follow the reasoning above with a different value of a. Remember that we are only interested in values of a that have an order.
Here is a function which automates the computations we did above. You supply the values of a and n. It will list the elements of Zn*, take that list and multiply each term by a, then give the list again after reducing modulo n, and finally sort the list.
As you try different values of a and keep n = 15, do you get the same exponent or does it vary? How can we predict what the exponent will be?
After you have a handle on n = 15, try different values for n.
Research Question 5For n = 15 and any value of a relatively prime to n, find a value for m that satisfies the requirements given in the question at the beginning of this section. You should be able to model your proof after the example given above. |
Research Question 6Now generalize your solution to Research Question 5 to any positive integer n and any value of a that has an order. |
Research Question 7Specialize your solution to Research Question 6 to n = p, where p is prime, and any value of a that has an order modulo p. You should be able to be more specific about the value of "m" in this special case. |
Once your proof of your conjecture for Research Question 7 is complete, you should be in a better position to prove your conjecture for Research Question 4.
The result of Research Question 7 is known as Fermat's Little Theorem. Research Question 6 is Euler's generalization of Fermat's Little Theorem to include composite values of n.
8.4.1 Why Is Fermat's Theorem Little?
The name Fermat's Little Theorem arose as a contrast to what is known as Fermat's Last Theorem:
If n > 3 and a, b, and c are integers such that an + bn = cn, then at least one of a, b, or c is zero.
Ironically, most mathematicians do not believe that Fermat proved this statement. It became famous years ago and is probably the most-studied mathematical problem in history. It was not considered a theorem until 1994 when Andrew Wiles completed its proof roughly 350 years after Fermat had conjectured it! Unfortunately, it has overshadowed the theorems which Fermat discovered and proved. So, the name Fermat's Little Theorem stuck as a way to distinguish it from Fermat's Last Theorem.