Euler's Totient Theorem

Theorem

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

1 a⁽ⁿ⁾ (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}.

Proof

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.

Step 1: Construct the set, S, of all distinct nonzero integers less than n that are relatively prime to n.

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

Step 2: Assign the number of elements in S to the parameter m.

Step 3: Choose an arbitrary integer a that is relatively prime to n.

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.

Step 4: Construct the set, R, by multiplying every member of S by a and reducing the result modulo-n.

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

Step 5: Determine the key properties of S and R.

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_ia mod n

This means that there exists some integer K_i such that

j_i = k_ia + K_in (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_ia + K_in

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

d = (k_ia/c) + (K_in/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₁ and k₂) and generate the corresponding elements of R (j₁ and j₂).

j₁ k₁*a mod n

and

j₂ k₂*a mod n

j₁ j₂ mod n

then

k₁*a k₂*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₁ k₂ 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₁ and k₂ were chosen to be distinct elements of S, therefore j₁ and j₂ 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.

Step 6: Prove that S and R are equivalent sets.

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

Step 7: Form the products of all elements of each set.

P_S = (k₁*k₂*...k_m) (i.e., product of all m-elements in S)

P_R = (j₁*j₂*...j_m) (i.e., product of all m-elements in R)

Step 8: Prove the equality of the two products and simplify.

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₁*k₂*...k_m) (j₁*j₂*...j_m) (mod n)

(k₁*k₂*...k_m) ((k₁*a)(k₂*a)...(k_m*a)) (mod n)

(k₁*k₂*...k_m) (k₁*k₂*...k_m)*a^m (mod n)

Note that the factor a^m results from the fact that there are m factors on the right hand side each of which includes a.

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⁽ⁿ⁾ (mod n)

provided a and n are relatively prime.

Don't Forget the Fine Print!

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⁴ mod 10 is equal to 1 when, obviously, it is 6.