If GCD(a,n) = 1 then aφ(n) = 1 (mod n).

Proof: take a to be any positive integer coprime to n.

Let A be the set of numbers coprime to n: A = {a1, a2, a3, …, aφ(n)}

Let aA be the product of the number, a, with each of the elements of A: aA = {aa1, aa2, aa3, …, aaφ(n)}

No two elements of aA are congruent mod n (see lemma 1, below*), so their residues mod n must be {a1, a2, a3, …, aφ(n)} in some order.

By equating the product of the numbers in set aA with the product of those in set A, mod n,

aφ(n)a1a2a3…aφ(n) = a1a2a3…aφ(n) (mod n)

Since a1a2a3…aφ(n) is coprime to n, we can divide both sides by a1a2a3…aφ(n), mod n, proving Euler’s Totient Theorem.

* Lemma 1: Why are no two elements of aA = {aa1, aa2, aa3, …, aaφ(n)} congruent, mod n?

Suppose a is a number coprime to n, and b and c are two different numbers, also coprime to n, in the range [1,n-1] and ab=ac, mod n.

Then ab-ac=nk, where k is an integer.

a(b-c)=nk, and since b-c is smaller than n in absolute value, a must be larger than k in absolute value.

a and n have no factors in common, so a|k, but a can’t divide k, since a is larger than k, a contradiction.

Other Totient Theorems

Let’s write m = 2n-1 for convenience.

Now 2n = m+1, so 2n = 1 (mod m), but no smaller (but still positive) power of 2 is equivalent to 1 (mod m).

So (2n)k = 1 (mod m), which means 2kn = 1 (mod m) for any integer, k.

2φ(m) = 1 (mod m), by Euler’s Totient Theorem.

We can divide φ(m) by n giving quotient q and remainder r such that φ(m) = qn+r, and so

2φ(m) = 2qn+r = 2qn 2r = 1 (mod m), and we know 2qn = 1 (mod m), so 2r = 1 (mod m), and 0 ≤ r < n, so r=0