Now we can state Euler's generalization.
Let be an integer. Recall that is then number of positive integers relatively prime to .
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.