Euler's Totient Function

Also called the Phi function after the Greek letter φ

How many integers from 1 to n don't share any prime factors with n?

The idea "don't share any prime factors" is often shortened to "coprime" or "relatively prime".

And so we get Euler's Totient Function (symbol φ)

Let's try another!

Your turn!

These are all examples of Euler's Totient Function, which has the symbol φ (the Greek letter Phi)

• φ(6) = 2
• φ(12) = 4
• φ(15) = 8

It is that simple, just crossing numbers off a list. 

But it can take a long time of course, so any timesavers would be handy. Let's discover some!

Prime Numbers

What happens with prime numbers?

This is generally true of all prime numbers:

φ(p) = p − 1
(where p is a prime number)

We have our first timesaver.

Same Prime More Than Once

What if we multiply by the same prime again?

And we get:

We have our next timesaver:

φ(p^a) = p^a-1(p − 1)
(where p is a prime number)

Two Different Primes

What about two different primes multiplied together?

This is generally true! We can work out how many of each prime factor we eliminated, adjust for over counting, and then work out how many are left.

And we can make a formula for it:

The result is remarkably simple:

φ(pq) = (p − 1)(q − 1)
(where p and q are distinct primes)

So far we have discovered:

• φ(p) = (p − 1)
• φ(pq) = (p − 1)(q − 1)

In fact it works generally:

• φ(pqr) = (p − 1)(q − 1)(r − 1)
• etc...

But all primes must be distinct (different)!

What about a mix of primes, some different, some the same?

So the algorithm is:

• Break the number into its prime factors
• Set aside any duplicate factors
• Use φ(pqr...) = (p − 1)(q − 1)(r − 1)... on the remaining factors
• Finish up by multiplying by the factors that were set aside

A better version!

But there is a neat formula that does all that and makes good sense:

φ(n) = n (p₁ − 1p₁)(p₂ − 1p₂) ... (p_z − 1p_z)

It starts with n, then multiplies it in a special way to reduce it like we did with the eliminations.

If you are doing the calculation manually, try replacing n with all its factors, it makes cancelling easier:

Note the formula is often written in this (exactly equivalent) form:

φ(n) = n (1 − 1p₁)(1 − 1p₂) ... (1 − 1p_z)

Any of those formulas let us find φ(n) for any integer above 1, because integers above 1 are either prime or the product of primes. See Fundamental Theorem of Arithmetic.

Another formula

There is another clever general formula:

φ(n) = p₁^k₁−1(p₁ − 1)p₂^k₂−1(p₂ − 1) ... p_z^k_z−1(p_z − 1)

Where p₁, p₂, etc are distinct (different) primes, and the exponents k₁, k₂, etc are their exponents.

Using distinct primes and their exponents neatly handles single or multiple primes. Let us do our previous example again to see:

Multiplicative Property

This is also true:

φ(pq) = φ(p)φ(q)
(where p and q are coprime, so don't share any factors)

To show why this works, let us see an example:

Uses

Euler's Totient Function is very useful in Number Theory and plays a central role in RSA Cryptography

Summary

• Euler's Totient Function φ is how many integers from 1 to n are coprime to n
• Coprime means "do not share any factors"
• For a prime number: φ(p) = p − 1
• For powers of a prime number: φ(p^a) = p^a-1(p − 1)
• General formulas (p_r are prime numbers):

φ(n) = n (p₁ − 1p₁)(p₂ − 1p₂) ... (p_z − 1p_z)

φ(n) = n (1 − 1p₁)(1 − 1p₂) ... (1 − 1p_z)

φ(n) = p₁^k₁−1(p₁ − 1)p₂^k₂−1(p₂ − 1) ... p_z^k_z−1(p_z − 1)

• Multiplicative property (p and q are coprime):

φ(pq) = φ(p)φ(q)