# 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 ifEuler's totient function (denoted

) counts the positive integers up to a given integer that are relatively prime toLet's observe

when is a prime number. It holds:That's because all integers smaller than

are relatively prime to the (prime) numberLet's now observe

, where and are two distinct primes.How many positive integers smaller than

are relatively prime toThe 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
```