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