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
aphi(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 Zn 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 Zn
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 Zn 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
aphi(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.