Euler's Totient Function

Euler's totient function, $ϕ (n)$ , counts the integers up to $n$ that are coprime to $n$ . It is the size of the multiplicative group $(Z / n Z)^{\times}$ .

Definition

Definition (Totient Function)

ϕ (n)

is the number of integers

k

{1, 2, \dots, n}

such that

g cd (k, n) = 1

Formulas

For prime $p$ : $ϕ (p) = p - 1$ .
For prime power: $ϕ (p^{k}) = p^{k} - p^{k - 1} = p^{k} (1 - 1/ p)$ .
Multiplicative: If $g cd (m, n) = 1$ , then $ϕ (mn) = ϕ (m) ϕ (n)$ .
General Formula: If $n = p_{1}^{e_{1}} \dots p_{k}^{e_{k}}$ :

ϕ (n) = n (1 - \frac{1}{p _{1}}) (1 - \frac{1}{p _{2}}) \dots (1 - \frac{1}{p _{k}})

Sum Property

d ∣ n \sum ϕ (d) = n

"The sum of the totients of the divisors equals the number itself."

Practice Problems

Exercise (Problem 1)

Calculate

ϕ (100)

and

ϕ (360)

Exercise (Problem 2)

Find all integers

n

such that

ϕ (n) = 12

Exercise (Problem 3)

Prove that

ϕ (n)

is even for all

n > 2