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_{1}^{e}1 p_{2}^{e}2
... p_{n}^{e}n

φ(x) = x (1-1/p_{1}) ( 1-1/p_{2})...( 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^{n}) = p^{n-1}(p-1), so

(3) φ(x) = p_{1}^{e}1^{-1}
(p_{1}-1) p_{2}^{e}2^{-1} ( p_{2}-1)...p_{n}^{e}n^{-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 this Math Help site is
Graeme McRae.