Now we give a theorem that is very important to the cryptography in this class.
Euler's Theorem: For any modulus m, for any number b that is relatively prime to m,
We can use this theorem to simplify exponential expressions. For
example, let the modulus m be 4001, a prime. Then 
.
Let b be a positive number less than 4001. Then
where we have used the basic rules of exponentiation 
and 
.
Since 
, we can simplify mod 4001
expressions by replacing 
with 1.
Similarly we can show
and so on. The exact exponent doesn't matter; what matters is the mod
standard name of the exponent.