Euler's totient function

January 29, 2021
Definition: Two integers
and
are relatively prime if the only positive integer that divides both of them is

Yeah, it has something to do with the greatest common divisor.

Definition: The greatest common divisor of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers.

Thus, the two integers

and
are relatively prime if

Euler's totient function (denoted

) counts the positive integers up to a given integer
that are relatively prime to

Let's observe

when
is a prime number. It holds:

That's because all integers smaller than

are relatively prime to the (prime) number

Let's now observe

, where
and
are two distinct primes.

How many positive integers smaller than

are relatively prime to

The ones that are not relatively prime to

are:

These are

numbers. Thus:


What if

where
is prime? In this case, the integers that are not relatively prime to
are:

Thus:

And now to the general formula. Let's write

as
where
are distinct primes. Then:

Bob is still working on the proof of this formula though. But he has managed to greatly improve his (already magnificent) computational engine. Not only does it provide a

function, it also provides
function now.

You can try the engine below, just type in something like:

totient 6
Bob's engine

The Alice and Bob newsletter

Get highlights of Alice and Bob's adventures delivered to your email box.

Made by XLAB with ❤️
Follow us
Twitter Twitter