Euler's Totient Function Examples 1

Recall from the Euler's Totient Function page that if $n \in \mathbb{N}$ then $\phi (n)$ denotes the number of positive integers less than or equal to $n$ that are relatively prime to $n$.

We made note of some important properties of this function including:

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

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

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

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

We will now look at some examples of computing $\phi(n)$ for various $n$.

Example 1

Calculate $\phi (529)$.

We first note that $529 = 23^2$. Since $23$ is a prime number we have that:

(1)

\begin{align} \quad \phi (529) = \phi (23^2) = 23^2 - 23 = 506 \end{align}

Example 2

Calculate $\phi (29791)$.

We first note that $29791 = 31^3$. Since $31$ is a prime number we have that:

(2)

\begin{align} \quad \phi (29791) = \phi (31^3) = 31^3 - 31^2 = 29791 - 961 = 28830 \end{align}

Example 3

Calculate $\phi (400)$.

The prime power decomposition of $400$ is $400 = 2^4 \cdot 5^2$. So:

(3)

\begin{align} \quad \phi (400) = \phi (2^4 \cdot 5^2) = \phi(2^4) \phi (5^2) = (2^4 - 2^3)(5^2 - 5^1) = (8)(20) = 160 \end{align}