Euler's theorem

Now we can state Euler's generalization.

Let $n>1$ be an integer. Recall that $\phi(n)$ is then number of positive integers relatively prime to $n$ .

Theorem 1.8.4 (Euler's Theorem)   If $n>1$ is an integer and $gcd(a,n)=1$ then $a^{\phi(n)}\equiv 1 ({\rm mod} n)$ .

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. $\Box$

We know that if a number $p$ is prime then $a^p\equiv a ({\bf mod} p)$ . An integer $n$ for which $a^n\equiv a ({\bf mod} n)$ is called a Fermat pseudoprime to base $a$ . Roughly speaking, if $n$ is a Fermat pseudoprime to many different bases then $n$ is ``probably'' a prime ^1.7.

Example 1.8.5   We have $\phi(10)=4$ (see Example 1.4.10 above), so by Euler's theorem, $1001^4 \equiv 1 ({\rm mod} 10)$ . We can check this by hand without a computer: by the binomial expansion $1001^4=(1000+1)^4=1000^4+4\cdot 1000^3 +6\cdot 1000^2 +4\cdot 1000 + 1 =1004006004001\equiv 1 ({\rm mod} 10)$ .