Euler's Totient Function and Prime Factorization

Welcome back. In our previous lesson, we introduced Euler's totient function, $ϕ (n)$ , as the cornerstone of Euler's theorem. This allowed us to simplify large modular exponentiations, a technique vital for modern cryptography. However, we were only able to compute $ϕ (n)$ for simple cases, such as primes where $ϕ (p) = p - 1$ .

This lesson delivers on the promise to generalize this computation. Our goal is to derive and apply a formula for calculating $ϕ (n)$ for any arbitrary integer $n$ , using its prime factorization. This computational skill is not merely a number-theoretic curiosity; it is a fundamental component in the construction of cryptosystems like RSA, where computing $ϕ (n)$ is a key step in generating the public and private keys.

The First Building Block: Powers of a Prime

We know how to compute $ϕ (p)$ for a prime $p$ . The next logical step is to consider a power of a prime, $n = p^{k}$ , where $k$ is a positive integer.

To compute $ϕ (p^{k})$ , we need to count the integers from 1 to $p^{k}$ that are relatively prime to $p^{k}$ . An integer shares a common factor with $p^{k}$ if and only if it is a multiple of $p$ . So, our task simplifies to counting how many numbers up to $p^{k}$ are not multiples of $p$ .

The following video provides a clear derivation of this count.

Introduction to Euler's Totient Function!

This video explains how to derive the formula for the totient of a prime power by counting the total numbers in the interval and subtracting those that are not coprime.

Please watch the section from this timestamp. Focus on the argument: the numbers that are not coprime to p^k are precisely the multiples of p. The video counts these multiples and subtracts them from the total.

As the video explains, the multiples of $p$ in the range $[1, p^{k}]$ are $1 \cdot p, 2 \cdot p, \dots, p^{k - 1} \cdot p$ . There are exactly $p^{k - 1}$ such multiples.

The total number of integers in the interval is $p^{k}$ . Therefore, the number of integers that are coprime to $p^{k}$ is:

ϕ (p^{k}) = (total numbers) - (multiples of p) = p^{k} - p^{k - 1}

This formula can also be written in two other useful forms:

ϕ (p^{k}) = p^{k - 1} (p - 1)

ϕ (p^{k}) = p^{k} (1 - \frac{1}{p})

This formula is our first major tool for computing $ϕ (n)$ .

The Second Building Block: The Multiplicative Property

Now that we can handle integers that are powers of a single prime, we need a way to handle integers with multiple distinct prime factors, like $n = 360 = 2^{3} \cdot 3^{2} \cdot 5$ . The key to this is a beautiful property of the totient function.

Theorem: Multiplicativity of $ϕ$
If $m$ and $n$ are two positive integers such that $g cd (m, n) = 1$ , then:

ϕ (mn) = ϕ (m) ϕ (n)

An integer is coprime to the product $mn$ if and only if it is coprime to $m$ and coprime to $n$ . This fact is the foundation of the proof for this theorem. The following resource provides an elegant and rigorous proof that leverages this idea by arranging the integers from 1 to $mn$ into a grid. Given your background, the structure of this proof should be quite satisfying.

4 Euler's Totient Function

This document provides a formal proof for the multiplicative property of Euler's totient function. The argument is both intuitive and rigorous.

First, read the subsection titled "Proving the multiplicative property" on page 3. Pay attention to the example where the numbers modulo 36 are laid out in a rectangle. This visual argument is the core idea. Then, read the formal proof that follows on page 4, which abstracts this very example.

The General Formula for $ϕ (n)$

We now have all the necessary components to build the general formula. Any integer $n > 1$ has a unique prime factorization:

n = p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}}

where $p_{1}, \dots, p_{r}$ are distinct prime numbers and $k_{1}, \dots, k_{r}$ are positive integers.

Since the terms $p_{i}^{k_{i}}$ are all pairwise coprime (e.g., $g cd (p_{1}^{k_{1}}, p_{2}^{k_{2}}) = 1$ ), we can repeatedly apply the multiplicative property:

ϕ (n) = ϕ (p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}}) = ϕ (p_{1}^{k_{1}}) \cdot ϕ (p_{2}^{k_{2}}) \dots ϕ (p_{r}^{k_{r}})

Now, we can substitute our formula for prime powers, $ϕ (p^{k}) = p^{k} - p^{k - 1}$ , for each term in the product. The following video walks through this final synthesis to arrive at the explicit formula.

Explicit Formula for Euler's Totient Function!

This video masterfully combines the two properties we've just discussed—the formula for prime powers and multiplicativity—to derive the general formula for \phi(n).

Watch the derivation from this section. The presenter starts with the prime factorization of n, applies the multiplicative property, substitutes the formula for prime powers, and simplifies the result into its final, elegant form.

The final result from this derivation is the explicit formula for Euler's totient function:

ϕ (n) = n p ∣ n \prod (1 - \frac{1}{p})

where the product is over the set of distinct prime factors $p$ of $n$ .

Putting the Formula into Practice

Let's apply this formula to a few examples.

Example 1: Computing $ϕ (360)$

The prime factorization of 360 is $2^{3} \cdot 3^{2} \cdot 5^{1}$ . The distinct prime factors are 2, 3, and 5.
Using the formula:

ϕ (360) = 360 (1 - \frac{1}{2}) (1 - \frac{1}{3}) (1 - \frac{1}{5})

ϕ (360) = 360 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 180 \cdot \frac{2}{3} \cdot \frac{4}{5} = 120 \cdot \frac{4}{5} = 96

So, there are 96 integers between 1 and 360 that are coprime to 360.

Example 2: The RSA Case

A crucial case for cryptography is when $n$ is the product of two distinct, large primes, $n = pq$ . This is the modulus used in the RSA algorithm. Let's compute $ϕ (n)$ in this case.
The distinct prime factors are simply $p$ and $q$ .

ϕ (pq) = pq (1 - \frac{1}{p}) (1 - \frac{1}{q}) = pq (\frac{p - 1}{p}) (\frac{q - 1}{q}) = (p - 1) (q - 1)

This extremely important result, $ϕ (pq) = (p - 1) (q - 1)$ , is used directly in RSA key generation. Notice how easy it is to compute $ϕ (n)$ if you know the prime factors $p$ and $q$ . However, if you only know $n$ , computing $ϕ (n)$ is computationally equivalent to factoring $n$ , which is believed to be a hard problem. This difficulty is the source of RSA's security.

To solidify your understanding, please study the following worked example.

[PDF] Dr. Z.'s Number Theory Lecture 15 Handout: Euler's Totient Function

This document provides another clear example of the computation.

Please review Problem 15.2 on page 2. It demonstrates the step-by-step calculation for \phi(300).

Conclusion

In this lesson, we have constructed the complete toolkit for computing Euler's totient function for any integer. We saw that the general formula is built upon two simpler, yet powerful, ideas: the formula for prime powers, $ϕ (p^{k}) = p^{k} - p^{k - 1}$ , and the multiplicative nature of the function, $ϕ (mn) = ϕ (m) ϕ (n)$ for coprime $m$ and $n$ .

Key Takeaways:

To compute $ϕ (n)$ , you must first find the prime factorization of $n$ .
The formula for a prime power is $ϕ (p^{k}) = p^{k} - p^{k - 1}$ .
The function is multiplicative: $ϕ (mn) = ϕ (m) ϕ (n)$ if $g cd (m, n) = 1$ .
The general formula is $ϕ (n) = n \prod_{p ∣ n} (1 - 1/ p)$ .
For the RSA modulus $n = pq$ , we have the critical identity $ϕ (n) = (p - 1) (q - 1)$ .
The ease of computing $ϕ (n)$ when the factors of $n$ are known, versus the difficulty when they are not, is a central principle in public-key cryptography.

In our next lesson, we will explore the Chinese Remainder Theorem. This theorem is a powerful tool for solving systems of linear congruences. As a point of interest, it also provides an alternative, more algebraic proof for the multiplicative property of $ϕ (n)$ , further highlighting the deep connections between the concepts in this module.

Recommended resources

The First Building Block: Powers of a Prime

The Second Building Block: The Multiplicative Property

The General Formula for ϕ(n)

Putting the Formula into Practice

Conclusion

The General Formula for $ϕ (n)$