Euler's Totient Function Examples 2

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 more examples of computing $\phi(n)$ for various $n$.

Example 1

Calculate $\phi (23291)$.

The prime power decomposition of $23292$ is $23292 = 2^2 \cdot 3^2 \cdot 647$. Hence it follows that:

(1)

\begin{align} \phi (23292) & = \phi (2^2) \phi (3^2) \phi (647) \\ \phi (23292) & = 2^{2-1}(2-1) 3^{2-1}(3-1) 647^{1-1}(647 -1) \\ \phi (23292) & = (2)(1)(3)(2)(1)(646) \\ \phi (23292) & = (2)(1)(3)(2)(1)(646) \\ \phi (23292) & = 7752 \\ \end{align}

Example 2

Calculate $\phi (62292)$.

The prime power decomposition of $62292$ is $62292 = 2^2 \cdot 3 \cdot 29 \cdot 179$. Hence it follows that:

(2)

\begin{align} \phi (62292) & = \phi (2^2) \phi (3) \phi (29) \phi (179) \\ \phi (62292) & = 2^{2-1}(2-1) 3^{1-1}(3-1) 29^{1-1}(29-1) 179^{1-1}(179-1) \\ \phi (62292) & = (2)(1)(1)(2)(1)(28)(1)(178) \\ \phi (62292) & = 19936 \end{align}

Example 3

Calculate $\phi (432432)$.

The prime power decomposition of $432432$ is $432432 = 2^4 \cdot 3^3 \cdot 7 \cdot 11 \cdot 13$. Hence it follows that:

(3)

\begin{align} \phi (432432) & = \phi(2^4) \phi(3^3) \phi (7) \phi (11) \phi (13) \\ \phi (432432) & = 2^{4-1}(2-1) 3^{3-1}(3-1) 7^{1-1}(7-1) 11^{1-1}(11-1) 13^{1-1}(13-1) \\ \phi (432432) & = (8)(1)(9)(2)(1)(6)(1)(10)(1)(12) \\ \phi (432432) & = 103680 \end{align}

Example 4

Calculate $\phi (6824000)$.

The prime power decomposition of $6824000$ is $6824000 = 2^6 \cdot 5^3 \cdot 853$. Hence it follows that:

(4)

\begin{align} \phi (6824000) & = \phi (2^6) \phi (5^3) \phi (853) \\ \phi (6824000) & = 2^{6-1}(2-1) 5^{3-1}(5-1) 853^{1-1}(853-1) \\ \phi (6824000) & = (32)(1)(25)(4)(1)(852) \\ \phi (6824000) & = 2726400 \end{align}

Example 5

Calculate $\phi (9999990)$.

The prime power decomposition of $9999990$ is $9999990 = 2 \cdot 3^3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 37$. Hence it follows that:

(5)

\begin{align} \phi (9999990) & = \phi (2) \phi (3^3) \phi (5) \phi (7) \phi (11) \phi (13) \phi (37) \\ \quad \phi (9999990) & = 2^{1-1}(2-1) 3^{3-1}(3-1) 5^{1-1}(5-1) 7^{1-1}(7-1) 11^{1-1}(11-1) 13^{1-1}(13-1) 37^{1-1}(37-1) \\ \phi (9999990) & = (1)(1)(9)(2)(1)(4)(1)(6)(1)(10)(1)(12)(1)(36) \\ \phi (9999990) & = 1866240 \end{align}