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$.