Additional Examples Of Calculating Φ for Large Integers

Recall that:

Theorem: Suppose that $n = p_1^{e_1}p_2^{e_2}...p_k^{e_k}$ is the prime power decomposition of n. Then $\phi (n) = p_1^{e_1 - 1}(p_1 - 1)p_2^{e_2 - 1}(p_2 - 1) ... p_k^{e_k - 1}(p_k - 1)$

We will continue to do some more examples for Calculating Φ for Large Integers.

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}