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 = p₁^e1 p₂^e2 ... p_n^en 

φ(x) = x (1-1/p₁) ( 1-1/p₂)...( 1-1/p_n)

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 φ(pⁿ) = p^n-1(p-1), so
(3) φ(x) = p₁^e1^-1 (p₁-1) p₂^e2^-1 ( p₂-1)...p_n^en^-1 ( p_n-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 the Math Help site is Graeme McRae.
     [home]  [email]  [search]  [Links to Math Sites]  [Whiteboard]