Navigation   Home   Search   Site map

document.write (document.title)

 Contact Graeme   Home   Email   Twitter
 Math Help > Number Theory > Theorems > Totient

The definition and key theorems involving Euler's Totient function.  For more info, see the "related pages" listed below.

Definition

φ(n) is the number of positive integers not larger than n that are coprime to n.  (Coprime is defined this way: two numbers are coprime when they share no factor other than 1.)  Note that φ(1)=1, because 1 is coprime to itself.

Calculating the totient of n

Let x = p1e1 p2e2 ... pnen

φ(x) = x (1-1/p1) ( 1-1/p2)...( 1-1/pn)

Proof:
(1) Totient is a multiplicative function -- that means when a and b are coprime (i.e. GCD(a,b)=1), then φ(ab) = φ(a) φ(b).
(2) If p is prime then φ(pn) = pn-1(p-1), so
(3) φ(x) = p1e1-1 (p1-1) p2e2-1 ( p2-1)...pnen-1 ( pn-1), which simplifies to the expression given here, as explained by the Totient Function page.

The Sum of Totients of Divisors of n is n

Consider the sum,

Σ φ(d) = n
d|n

Proof:  I will show that this sum counts all the cases, as k ranges from 1 to n, in which GCD(k,n)=d, where d is a divisor of n.  There are n such cases, because GCD(k,n) is always some divisor of n.

As k ranges from 1 to n, GCD(k,n)=d exactly when k/d and n/d are coprime integers.  Therefore, the sum

Σ φ(n/d) = n
d|n

And, since n/d ranges over all the factors of n, this sums the totients of all the factors of n, proving the result.

A more elaborate proof with examples:  Totient Function

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

Proof: Euler's Totient Theorem

Related pages in this website

Proof that the sum of totients of divisors of n is n:  Totient Function, and some other interesting things about totients.

Proof that any number coprime to n raised to the power φ(n) is 1 (mod n): Euler's Totient Theorem, and some other interesting things about totients.

Method of proof: multiplicative induction

μ(n), the M�bius function

τ(n), the number of divisors of n: Divisors, Tau function

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