Euler-Totient Function

Euler-

φ

Function

For $n \in Z^{+}$ , let $φ (n)$ be the number of positive integers $a \leq n$ with $a$ relatively prime to $n$ . Namely, $(a, n) = 1$ (so you are counting the "primes" up to $n$ ).

For example $φ (12) = 4$ since $1, 5, 7, 11$ are the only positive integers less than or equal to 12 with no factor in common with 12. Similarly $φ (1) = 1, φ (2) = 1, φ (3) = 2, φ (4) = 2, . . .$ . For primes $p$ we have $φ (p) = p - 1$ and more generally for all $a \geq 1$ we have:

φ (p^{a}) = p^{a} - p^{a - 1} = p^{a - 1} (p - 1)

The function $φ$ is multiplicative in the sense that:

φ (a b) = φ (a) φ (b) ⟺ gcd (a, b) = 1

So for any general $n \in N$ then $n = p_{1}^{α_{1}} p_{2}^{α_{2}} \dots p_{s}^{α_{s}}$ so then:

\begin{aligned} φ (n) & = \prod_{i = 1}^{s} φ (p_{i}^{α_{i}}) \\ = \prod p_{i}^{α_{i} - 1} (p_{i} - 1) \end{aligned}

For instance $φ (12) = φ (2^{2}) φ (3) = 2^{1} (2 - 1) \cdot 3^{0} (3 - 1) = 4$ .