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)$.