Table of Contents

Recall the definition for Euler's totient function:
Definition: Euler's Totient Function or Euler's ΦFunction, $\phi (m)$ for a positive integer m is equal to the number of positive integers less than or equal to m that are relatively prime to m. 
We will now obtain methods for calculating Φ(n) for large positive n.
Calculating Φ for Large Positive Integers
Lemma 1: If p is a prime, then Φ(p) = p  1.
 Proof: Suppose that p is any prime. The only divisors of p are 1 and p. There are p1 positive integers less than or equal to p, so $\phi (p) = p  1$. Notice that of all the positive divisors between 1 and p, the only one that is not relatively prime to p is p itself since $(p, p) = p$ trivially.
Recall that Fermat's Theorem states that for a prime p and when $(a, p) = 1$, then $a^{p1} \equiv 1 \mod p$. Since $\phi (p) = p 1$, we can see that Fermat's theorem is just a special case of Euler's theorem ($a^{\phi (m)} \equiv 1 \pmod m$.
Lemma 2: For any prime p, Φ(p^{n}) = p^{n  1}(p  1) for any positive integer n.
 Proof: The number of positive integers less than or equal to any prime p^{n} that are not relatively prime to p^{n} are multiples of p, that is $p, 2p, 3p, ..., p^{n1}p$. There are hence p^{n1} of these integers. In total there are p^{n} positive integers less than or equal to p^{n}. Hence $\phi (p^n) = p^n  p^{n  1} = p^{n1}(p  1)$.
Example 1
Calculate A) $\phi (529)$, B) $\phi (29791)$.
 A) Notice that 529 is a square, specifically $529 = 23^2$. Since 23 is a prime, we can utilize lemma 3 to calculate $\phi (529)$, namely $\phi(529) = \phi (23^2) = 23^{21}(231) = 506$.
 B) 29791 is a cube, specifically $29791 = 31^3$. Once again, applying lemma 3 we calculate that $\phi (29791) = \phi (31^3) = 31^{31}(311) = 31^2(30) = 28830$.
Lemma 3: Euler's totient function is multiplicative
We are not going to prove this lemma, however, note that a function defined on positive integers is multiplicative if $f(mn) = f(m) f(n)$ and $(m, n) = 1$. Euler's totient function is the same way, that is \phi (mn) = \phi (m), \phi (n) $]] if $(m, n) = 1$.
Example 2
Calculate A) $\phi (34)$, B) $\phi (52)$ and C) $\phi (33)$.
To evaluate all of these values, we're going to try to find their prime power decompositions since we can easily calculate $\phi (p)$.
 A) We can calculate the prime power decomposition of 32 to be $32 = 2 \cdot 17$. Both 2 and 17 are prime. We know that for any prime p, $\phi (p) = p  1$. Hence $\phi (32) = (1)(16) = 16$.
 B) The prime power decomposition of 52 is $52 = 2^2 \cdot 13$. So then $\phi (52) = \phi (2^2) \phi (13)$. $\phi (4) = 2$, so thus we obtain that $\phi (52) = (2)(12) = 24$.
 C) The prime power decomposition of 33 is $33 = 3 \cdot 11$. So then $\phi (33) = \phi (3) \phi (11) = (2)(10) = 20$.
Using the Prime Power Decomposition of n to Calculate Φ(n)
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)$ 
 Proof: Since Euler's totient function is multiplicative, it thus follows that if the prime power decomposition of an integer n is $n = p_1^{e_1}p_2^{e_2}...p_k^{e_k}$, then $\phi (n) = \phi (p_1^{e_1}) \phi (p_2^{e_2}) ... \phi (p_k^{e_k})$ since $(p_i, p_k) = 1$ when $i ≠ j$ (every prime is relatively prime to every other prime). But $\phi (p_i^{e_i}) = p_i^{e_i  1}(p_i  1)$, so then $\phi (n) = \phi (p_1^{e_1}) \phi (p_2^{e_2})... \phi (p_k^{e_k}) = p_1^{e_1  1}(p_1  1)p_2^{e_2  1}(p_2  1) ... p_k^{e_k  1}(p_k  1)$, which completes the proof.
Example 3
Calculate $\phi (624)$.
The prime power decomposition of 624 is $624 = 2^4 \cdot 39$. It thus follows that $\phi (624) = \phi (2^4) \phi (39) = 2^{41}(21) \cdot 39^{11}(391) = 2^3 (1) \cdot (1)(38) = 8 \cdot 38 = 304$.