# rsa / Euler’s Totient Function — Number Theory

Part of my series explaining the RSA Algorithm

Euler, one of the busiest people in Mathematical history, first demonstrated this function in 1763. He tried to use pi (π) to denote the function but it turns out pi was occupied. In 1801 Gauss suggested that we use phi (𝛗) instead. It was named the ‘Totient Function’ in 1879, by James Joseph Sylvester.

With name and notation settled, let’s look at what it does. A coprime pair is where the greatest common divisor two numbers share is 1. They have no larger common factors; they are relatively prime.

The Totient Function tells us how many coprimes a number has smallest than itself. 9’s smaller coprimes are 1, 2, 4, 5, 7 & 8. 𝛗(9) = 6. But how does it do that?

Finding the Totient

For Primes

For prime numbers the Totient value is 1 less than itself. Every number less than a prime number is relatively prime to it. This the definition of a prime number. So for any prime p, 𝛗(p) = p -1. That was simple enough.

For Prime Powers

For a prime p raised to a power k, the only numbers less than pᵏ which are NOT its coprimes are other multiples of p. This is because p is the only factor in pᵏ.

All pᵏ’s factor can be represented: p, 2p, 3p, …, pᵏ⁻¹p.

pᵏ⁻¹ is necessarily the largest multiple of p greater than or equal to pᵏ because pᵏ⁻¹p = p.

Therefore we know that pᵏ has pᵏ⁻¹ numbers less than it which are not coprime. There are pᵏ integers less than pᵏ. If pᵏ⁻¹ are not coprime, then pᵏ - pᵏ⁻¹ integers are coprime to pᵏ.

For prime powers the formula for counting coprimes less than it is: 𝛗(pᵏ) = pᵏ - pᵏ⁻¹.

For everything else

For those numbers which are neither prime nor prime powers, we use Euler’s Product Formula. It works as follows.

Solving for n, which has j prime factors, the product formula takes the form:

n x (1 — 1/p₁) x (1 — 1/p₂) x ... x (1 — 1/pⱼ).

For example:

n = 42

> which has 3 prime factors
j = 3

ϕ(42) = ϕ(7 x 2 x 3) = 42 x (1 — 1/7) x (1 — 1/2) x (1 — 1/3) = 12.

ϕ(42) = 12

42’s coprimes are: 1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41. There are 12 of them, so the product formula method worked. But why?

One of 42’s prime factors is 3. We know that 1 in 3 numbers are a multiple of 3, and the other 2 in 3 are not. So we multiple 42 by 2/3 to give us the count of numbers less than 42 which does not share the factor 3.

Repeating this process for all 42’s primes looks like: 6/7 x 1/2 x 2/3 = 6/21. This gives us the proportion of all numbers less than 42 which share none of its prime factors. To get the count, we can do proportion multiplied by total: 6/21 x 42 = 12.

We can use this as a corroborative proof for prime powers too. We found that for any prime power pᵏ, the totient value is 𝛗(pᵏ) = pᵏ - pᵏ⁻¹.

pᵏ — pᵏ⁻¹
pᵏ — (pᵏ x p⁻¹)
pᵏ — (pᵏ x 1/p)
pᵏ(1 — 1/p)

By rearranging the prime power rule we can see it derives from the same idea of removing those numbers that share none of its prime factors; in the case of prime powers, just the one factor.

Using the Totient Function

You’re equipped to find its value in any case, but why would you want to at all? Euler’s Totient is leaned on heavily when working with Carmichael’s Function, as we saw in our explanation of it in an earlier post. Consequently, it is very important to digital cryptography.

The Totient also has implications for two unsolved conjectures: Lehmer’s Conjecture and Carmichael’s conjecture.

Happy maths-ing.