As

krimson has mentioned, calling a result Euler's theorem
somewhat under-specifies it. However, here is a theorem
that usually goes by that name.
It's worth noting that although this result is simple it
is used in an important way in the

RSA cryptosystem.
We need a definition.

**Definition**
If *a,b,n* are integers with *n>0*
we say that *a* is *congruent* to *b*
*modulo* *n* if *n* divides *a-b*.

So for example
4 is congruent to 1 modulo 3.
We write phi for the Euler Phi function.

**Euler's Theorem**
If *a* and *n* are coprime positive integers
then

*a*^{phi(n)} is congruent to 1 modulo *n*.

Before we prove this result, note that Fermat's Little Theorem
is the special case of this result when *n* is prime.

**Proof:**
We'll use a little bit of technology to prove the theorem.
Consider **Z**_{n} the ring of integers modulo n.
Have a look at that writeup because we'll use some results and notation
from it. It is shown there that for an integer
*a* we have __a__ is a unit in **Z**_{n}
if and only if *(a,n)=1*. So we see from the
definition of the Euler Phi function
that the multiplicative group
of units in the ring **Z**_{n} has order phi(*n*).
By Lagrange's theorem if we raise an element in a finite group
to the power the group order we get the identity element.
Thus, if *a* is as in the statement
it satisfies

__a__^{phi(n)} = __1__

The result follows since for two integers

*x* and

*y*
we have

__x__=__y__ if and only if

*x* is congruent
to

*y* modulo

*n*.