Euler's Totient Function

Definition

$Z_{m}^{*} = d e f {a \in Z_{m} ∣ g c d (a, m) = 1}$ $ϕ (m) = ∣ Z_{m}^{*} ∣$

ϕ (m) = m p ∣ m \prod (1 - \frac{1}{p})

m = p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}}

is the prime factorization of $m$ , then

ϕ (m) = p_{1}^{k_{1} - 1} (p_{1} - 1) \cdot p_{2}^{k_{2} - 1} (p_{2} - 1) \dots p_{r}^{k_{r} - 1} (p_{r} - 1)

So the rule is:

Factor $m$ into primes
For each prime $p_{i}^{k_{i}}$ :
- keep $p_{i}^{k_{i} - 1}$
- replace one $p_{i}$ by $(p_{i} - 1)$
Multiply everything together

m = 18 = 2 \cdot 3^{2}

ϕ (18) = 2^{1 - 1} (2 - 1) \cdot 3^{2 - 1} (3 - 1) = 1 \cdot 1 \cdot 3 \cdot 2 = 6