Calculating Φ for Large Positive Integers

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 p-1 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^{p-1} \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, Φ(pn) = pn - 1(p - 1) for any positive integer n.

• Proof: The number of positive integers less than or equal to any prime pn that are not relatively prime to pn are multiples of p, that is $p, 2p, 3p, ..., p^{n-1}p$. There are hence pn-1 of these integers. In total there are pn positive integers less than or equal to pn. Hence $\phi (p^n) = p^n - p^{n - 1} = p^{n-1}(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^{2-1}(23-1) = 506$.
• B) 29791 is a cube, specifically $29791 = 31^3$. Once again, applying lemma 3 we calculate that $\phi (29791) = \phi (31^3) = 31^{3-1}(31-1) = 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^{4-1}(2-1) \cdot 39^{1-1}(39-1) = 2^3 (1) \cdot (1)(38) = 8 \cdot 38 = 304\$.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License