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 Theoremand Euler's generalization. Our goal is to answer the following question:Given an integer

n, can we produce another positive integermsuch thata1 (mod^{m}n) forallintegersathat have an order?Note that this would imply that such an

mis a period (although not necessarily minimal) for the powers ofamodnforallathat 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

nwhich are relatively prime ton. Since this set will appear in the course later, we will give its usual notation here:

DefinitionThemultiplicative groupmodulon, denotedZ_{n}^{*}, is the set of elements ofZ_{n}which are relatively prime ton. The number of integers inZ_{n}^{*}is denoted by_{}(n).In our example of

n= 15,Z_{15}^{*}is1, 2, 4, 7, 8, 11, 13, 14.

An interesting thing happens if we multiply every element of

Z_{n}^{*}bya. Here's what we get withn= 15 anda= 2:2, 4, 8, 14, 16, 22, 26, 28.

Since we are working modulo

n, let's reduce the entire list modulon= 15:2, 4, 8, 14, 1, 7, 11, 13.

Looking closely, we recognize that these are the elements of

Z_{15}^{*}, 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

Z_{n}^{*}in a new way, namely by multiplying bya. We can exploit this observation by taking the product over both sets. Starting with the product of the elements ofZ_{15}^{*}each multiplied bya(= 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:

2

^{8}· (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

Z_{n}^{*}(after reordering them). Hence it follows that2

^{8}· (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

2

^{8}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 ofathat have an order.Here is a function which automates the computations we did above. You supply the values of

aandn. It will list the elements ofZ_{n}^{*}, take that list and multiply each term bya, then give the list again after reducing modulon, and finally sort the list.

As you try different values of

aand keepn= 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 forn.

## Research Question 5

For

n= 15 and any value ofarelatively prime ton, find a value formthat 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 6

Now generalize your solution to Research Question 5 to any positive integer

nand any value ofathat has an order.

## Research Question 7

Specialize your solution to Research Question 6 to

n=p, wherepis prime, and any value ofathat has an order modulop. 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 ofn.

## 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 anda,b, andcare integers such thata+^{n}b=^{n}c, then at least one of^{n}a,b, orcis 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

andproved. So, the name Fermat's Little Theorem stuck as a way to distinguish it from Fermat's Last Theorem.

Section 8.1 | Section 8.2 | Section 8.3 | Section 8.4

Copyright © 2001 by W. H. Freeman and Company