Euler's totient function

In number theory, Euler's totient function counts the positive integers up to a given integer

that are relatively prime to

. It is written using the Greek letter phi as

, and may also be called Euler's phi function. It can be defined more formally as the number of integers

in the range

for which the greatest common divisor

is equal to

. The integers

of this form are sometimes referred to as totatives of

. For example, the totatives of

are the six numbers

and

. They are all relatively prime to

, but the other three numbers in this range,

, and

are not, because

and

. Therefore,

As another example,

since for

the only integer in the range from

itself, and

Euler's totient function is a multiplicative function, meaning that if two numbers

and

are relatively prime, then

.This function gives the order of the multyplicative group of integeres modulo

(the group of units of the ring

). It also plays a key role in the definition of the RSA encryptoin system.

New Resources