The Euler totient function plays an important role in the field of number theory so I’ve decided to give a brief introduction to it in this article with some nice applications.

Coprime Integers

We say that an integer m divides n (or is a divisor of n) if n/m is a whole number and we write m|n. Furthermore, we say that two whole numbers m and n are relatively prime (or coprime) if the greatest common divisor is 1. In this case, we write (n,m) = 1. In the literature, you will sometimes see the notation gcd(n,m)instead of (n,m).

For example, 3|6 and (5,6)=1. Of course, 3 divides 6 and the biggest number dividing both 5 and 6 is 1.

The Totient Function

An important question that turns up in number theory all the time is the following:

“how many numbers below a given number n is coprime to n?”

Define the Euler Totient function (sometimes called the Euler ϕ-function) as

That is, ϕ(n) is the number of natural numbers below n that are coprime to n.

For example, ϕ(6) = 2 because only 1 and 5 are both less than and coprime to 6. In the same fashion, ϕ(10) = 4, ϕ(30) = 8 etc.

It would surely be nice if we had a formula for this function but how would we go about finding one? Let me introduce a nice technique for finding such arithmetic formulas that can be applied to a lot of different functions and scenarios in mathematics in general.

A Probabilistic Approach

This method revolves around a question of probabilistic nature.

Instead of proving a formula the totient function by some classical machinery such as induction or direct proof, I will go about this by raising the following question:

“What is the probability that a random integer between 1 and n is coprime to n”?

On the one hand, by the definition of the totient function ϕ, an answer is of course ϕ(n)/n because after all, there are ϕ(n) integers between 1 and n that are coprime to n and there are of course n integers in total. We have:

On the other hand, let’s think about this in terms of prime divisors of n. That a number m is coprime to n means that for each prime number p dividing n, p does not divide m.

Returning to the question, the probability that a prime number p divides m is 1/p. So the probability that a prime p does not divide m must be 1–1/p as the sum of all probabilities on a probability space must be 1 and the two events are compliments of each other.

Therefore, the probability that none of the primes dividing n also divides m is the product of the probabilities that each prime dividing n does not divide m. That is,

Multiplying by n on both sides yields

Note that by this formula, if p is a prime number, then ϕ(p) = p(1–1/p) = p-1. It makes sense that all the numbers below p are coprime to p because that’s what makes it prime in the first place!

Applications

It turns out that ϕ is a multiplicative function i.e. if (n,m) = 1, then ϕ(nm) = ϕ(n)ϕ(m).

The proof is simple once we know the above formula.

Note that this wouldn’t work if m and n had a prime divisor in common. That is, ϕ is multiplicative but not completely multiplicative.

In general, if (n,m) = d, then ϕ(nm) = ϕ(n)ϕ(m) d/ϕ(d).

A very nice result discovered by Gauss is that

It turns out that such sums over divisors have a relation to the Riemann zeta function. If one assumes convergence in the obvious places, on has:

Theorem:

When we apply this to the above sum of the totient function of divisors we obtain:

Another nice result is that φ(n) is the order of the multiplicative group of integers modulo n. This result becomes important when we study e.g. group characters and Gauss sums which will lead to the theory of Dirichlet L-functions as generalizations of the Riemann zeta function. But that is for another article.

Perhaps the most famous use of the Euler totient function comes from Euler’s theorem that generalizes Fermat’s little theorem (not to be confused with his last theorem).

It states that if (n,m) = 1, then

When n is prime, this is called Fermat’s little theorem.

Many people think that this is very abstract and theoretical, but actually, every time we make online transactions, Euler’s theorem makes the data transfer secure by exploiting the fact that it is hard to compute ϕ(n) without factoring n into its prime factorization and that is generally considered very hard (viewed in a complexity theoretical context) because we don’t know of any fast algorithms for doing this.

We’ll end his article with a quote from one of the masters.

Mathematics is the queen of sciences and number theory is the queen of mathematics

~ Carl Friedrich Gauss