Euler's theorem states that, for any positive integer *n*, that

1
a^{(n)}
(mod n)

for all integers *a* that are relatively prime to *n*. Note that
this last requirement, though subtle and frequently forgotten, is critically
important.

The function (n) is
Euler's totient function and is defined
as the number of positive integers less than and relatively prime to *n*.
For example, (15) is 8 because there are eight
positive integers less than 15 that share no factors with 15, namely
{1,2,4,7,8,11,13,14}.

For now, let's ignore this notion of the totient function and just assume
that there exists an integer *m* such that

1
a^{m} (mod n)

and see if we can't prove that it exists and what relationship it has to have
to *n*.

The proof that follows may appear to be subtle and somewhat convoluted. Do not be concerned if the underlying reasoning for the approach taken is not readily apparent provided the legitimacy of each step is clear. It might put your mind at ease to note that Euler's Totient Theorem is a generalization of Fermat's Little Theorem, something which Pierre de Fermat himself, one of history's greatest mathematicians, failed to prove when he first proposed the theorem in 1640. Since that time, several proofs have been devised tackling the problem from several fields of study including, among others, combinatorics, modular arithmetic, group theory, and dynamical systems. Since most of our work here involves modular arithmetic, that is the approach that is most natural for us to pursue.

S = {k : 0 < k < n AND gcd(k,n) = 1}

Without loss of generality, we may reduce this value modulo-*n* so that
it is a positive integer less than *n*. Note that, having done this, *a*
will be a member of the set *S*, although this is coincidental.

R = {j: j = ka mod n for any a in S and all k in S}

__Property #1:__ The elements of S are distinct.

Proof: Self-evident

The nature of the construction of S guarantees this since only distinct integers were included.

__Property #2:__ The sets *S* and *R* contain the same number of elements,
namely *m*.

Proof: Self evident.

Each element in *S* was used to generate exactly one element in *R*.

__Property #3:__ Every element of *R* is also an element of *S* (i.e., *R*
is a subset of *S*).

Proof: By contradiction.

Every element of *R* was formed by multiplying two nonzero numbers, *k*
and *a*, that are both relatively prime to
*n.* and then reducing the result modulo-*n*. In other words,

j_{i} = k_{i}a mod n

This means that there exists some integer *K*_{i} such that

j_{i} = k_{i}a + K_{i}n (0 ≤ j_{i}
< n)

If *j*_{i} is not relatively prime to *n*, then it may be
factored into two integers, *c* and *d*, one of which (we'll stipulate
*c*) is a factor of *n*.

c*d = k_{i}a + K_{i}n

Dividing both sides by *c* leaves us with the following expression for
the integer *d*:

d = (k_{i}a/c) + (K_{i}n/c)

Since *c* is a factor of *n*, the second term on the
right hand side is an integer. However, since *k*_{i} and *a*
are both relatively prime to *n*, neither can contain *c* as a factor
and hence the first term is not an integer. The sum of an integer and a
non-integer is not an integer and hence *d*, which must be an integer,
cannot be an integer. This contradiction thus proves that no suitable *c*
exists and hence *j*_{i} and *n* are relatively prime. Notice
that this argument also ensures that *j*_{i} is nonzero.

Therefore *j*_{i} is a positive integer less than
and relatively prime to *n*, which by definition means that it is included
in the set *S*.

__Property #4:__ Elements in *R* are distinct.

Proof: By contradiction.

Pick any two distinct elements of *S* (arbitrarily call them *k*_{1}
and *k*_{2}) and generate the corresponding elements of *R* (*j*_{1}
and *j*_{2}).

j_{1}
k_{1}*a mod
n

and

j_{2}
k_{2}*a mod
n

If

j_{1} j_{2} mod n

then

k_{1}*a
k_{2}*a
mod n

Since *a* is relatively prime to *n*, the
cancellation property of modular arithmetic
allows us to cancel it from both sides leaving

k_{1} k_{2} mod n

Since all elements of *S* are positive integers less than *n*, the
only way they can be congruent modulo-*n* is if they are equal. But this contradicts the constraint that *k*_{1} and *k*_{2}
were chosen to be distinct elements of *S*, therefore *j*_{1}
and *j*_{2} must be distinct elements of *R*.

Since we placed no constraints on which distinct elements of *S* that we
picked, and hence which elements of *R* would be generated, it follows that all elements of *R* are distinct.

If *S* and *R* both consist of distinct elements (properties #1 and
#4) and *R* is a subset of *S* (property #3) having as many elements
as *S* (property #2), then each element of *S* must be included in *
R* making *S* a subset of *R*. If two sets are subsets of each
other, then they are equivalent (i.e, they contain identical elements possibly
varying only in the ordering of the elements).

P_{S} = (k_{1}*k_{2}*...k_{m})
(i.e., product of all m-elements in S)

P_{R} = (j_{1}*j_{2}*...j_{m}) (i.e., product of all m-elements in R)

Since, except for order, *S* and *R* are the same and since multiplication is
commutative, these two products are equal

P_{S} = P_{R}

Since any two equal numbers are congruent when reduced by the same modulus

P_{S}
P_{R} (mod
n)

Expressing *P*_{R} in terms of how it is generated
from the elements of *S*, we have

(k_{1}*k_{2}*...k_{m})
(j_{1}*j_{2}*...j_{m}) (mod
n)

(k_{1}*k_{2}*...k_{m})
((k_{1}*a)(k_{2}*a)...(k_{m}*a))
(mod n)

(k_{1}*k_{2}*...k_{m})
(k_{1}*k_{2}*...k_{m})*a^{m}
(mod n)

Note that the factor *a ^{m}* results from the fact that there
are

Since each element *k*_{i} is relatively prime to *n*, the
cancellation property of modular arithmetic
allows us to cancel each
from both sides of the equation. Therefore

1
a^{m} (mod n)

Recall that, at the very beginning of this proof, we defined *m* to be
the number of nonzero integers less than *n* that are relatively prime to
*n*. The function that returns this number is, by definition,
Euler's totient function,
(n).
Hence

1
a^{(n)}
(mod n)

provided *a* and *n* are relatively prime.

As pointed out at the beginning, the requirement that *a* and *n*
must be relatively prime is a subtle
point that is easily and frequently forgotten, but notice the proof
required it to establish both properties #3 and #4 in Step 5 without which we
would not have been able to assert that the two products formed in the Step 7
were equal.

To show that this is not just a trivial fine point in the proof, consider the
case where *n* is 10 and *a* is 4. It is easy to determine that the
totient of 10 is 4 since the only positive integers less than 10 that are
relatively prime to 10 are {1,3,7,9}. If we ignore the requirement that *a*
and *n* must be relatively prime, we would conclude that 2^{4} mod
10 is equal to 1 when, obviously, it is 6.