## Euler's theorem

Now we can state Euler's generalization.

Let be an integer. Recall that is then number of positive integers relatively prime to .

Theorem 1.8.4 (Euler's Theorem)   If is an integer and then .

proof: The proof of Fermat's Little Theorem above can be modified somewhat to work in this more general case as well. Exercise: Try to do this.

We know that if a number is prime then . An integer for which is called a Fermat pseudoprime to base . Roughly speaking, if is a Fermat pseudoprime to many different bases then is probably'' a prime 1.7.

Example 1.8.5   We have (see Example 1.4.10 above), so by Euler's theorem, . We can check this by hand without a computer: by the binomial expansion .

david joyner 2008-04-20