Euler's Totient Function

Recall from The Sum of Positive Divisors of an Integer page that if $n \in \mathbb{Z}$ then $\sigma(n)$ denotes the sum of all positive divisors of $n$ and is explicitly given by:

(1)

\begin{align} \quad \sigma(n) = \sum_{d \mid n}_{d > 0} d \end{align}

We will now look at yet another very important function known as Euler's totient function which we define below.

Definition: Euler's Totient Function denoted $\phi : \mathbb{N} \to \mathbb{N}$ is defined for each $n \in \mathbb{N}$ by $\phi (n)$ representing the number of positive integers that less than or equal to $n$ and relatively prime to $n$.

An alternative name for Euler's totient function is "Euler's phi function".

For example, if $n = 16$, consider all of the positive integers less than $16$. They are:

(2)

\begin{align} \quad \{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 \} \end{align}

The only subset of these positive integers which are relatively prime to $16$ are $\{ 1, 3, 5, 7, 9, 11, 13, 15 \}$. There are $8$ such numbers, so $\phi (16) = 8$.

Proposition 1: If $p$ is a prime number then $\phi (p) = p - 1$.

• Proof: Let $p$ be prime. Then $1, 2, ..., p-1$ are all relatively prime to $p$. There are $p - 1$ such numbers, so $\phi (p) = p - 1$. $\blacksquare$

Proposition 2: If $p$ is a prime number then $\phi (p^2) = p^2 - p$.

• Proof: Let $p$ be a prime number and let $n \in \{ 1, ..., p^2 - 1 \}$. Then $n$ can be expressed for some $a_0, a_1 \in \{ 0, 1, ..., p-1 \}$ as:

(3)

\begin{align} \quad n = a_0 + a_1p \end{align}

• Note that $(p^2, n) \neq 1$ if and only if $p \mid a_0$ i.e., $a_0 = 0$. So there are $p - 1$ values for which $a_0$ can be, and $p$ values for which $a_1$ can be so there are $p(p-1) = p^2 - p$ values for which $(p^2, n ) \neq 1$. Thus:

(4)

\begin{align} \quad \phi (p^2) = p(p - 1) = p^2 - p \quad \blacksquare \end{align}

Proposition 3: If $p$ is a prime number and $k \in \mathbb{N}$ then $\phi (p^k) = (p - 1)p^{k-1} = p^k - p^{k-1}$.

• Proof: Let $p$ be a prime number and let $n \in \{ 1, ..., p^k - 1\}$. Then $n$ can be expressed for some $a_0, a_1, ..., a_{k-1} \in \{ 0, 1, ..., p - 1\}$ as:

(5)

\begin{align} \quad n = a_0 + a_1p + a_2p^2 + ... + a_{k-1}p^{k-1} \end{align}

• Then $(p^k, n) = 1$ if and only if $p \mid a_0$, i.e., $a_0 = 0$. So there are $p - 1$ values for which $a_0$ can be, and there are $p$ values for which $a_1$, $a_2$, …, $a_{k-1}$ can be. Thus:

(6)

\begin{align} \quad \phi (p^k) = p^{k-1}(p - 1) = p^k - p^{k-1} \quad \blacksquare \end{align}

Proposition 4: If $p$ and $q$ are distinct prime numbers then $\phi (pq) = \phi (p) \phi (q)$.