Navigation 
 Home 
 Search 
 Site map 

 Contact Graeme 
 Home 
 Email 
 Twitter

 Skip Navigation LinksMath Help > Number Theory > Factors, Coprimes, and Totient Function > Euler's Totient Theorem

Euler's Totient Theorem

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

A Generalization of Fermat's Little Theorem

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

If n is a positive integer, then n divides φ(2n-1)

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

Internet references

 

Related Pages in this website

Squares.

Euler's criterion for determining whether a number is a quadratic residue (mod p), or in other words, if a number is the square of some other number (mod p).

Fermat's Theorems -- Fermat's Little Theorem, in particular.

For any integer n, the sum of the totient values of each of its divisors equals n.

Number theory theorems, page 4: Totient.

Group - definition of a "group", which has properties closure, associativity, identity, and inverse.

The proof that primes of the form 4k+3 can be expressed as the sum of four squares uses Fermat's Little Theorem.

A bunch of Ring Theory theorems and definitions.

Proof that there is no solution to the Diophantine equation A4+B4=C2, which means Fermat's last theorem is true 

   


The webmaster and author of this Math Help site is Graeme McRae.