Euler’s Totient Theorem

Standard
Now I will present a wonderful fact about the coprimes to n — they form a group under multiplication mod n, which leads to:

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s