# Euler’s totient function (or Euler’s phi function)

Euler’s phi function

For arbitrarily chosen natural number , we observe the following sequence:

The totient  of a positive integer  greater than 1 is defined to be the number of positive integers less than  that are relatively prime to . In this way we obtain a function defined with .  is defined to be 1.

We call this function the Euler’s totient function or Euler’s phi function and it is very important number theoretic function having a deep relationship to prime numbers and the so-called order of integers.

For instance, let’s find . We observe the sequence:

Numbers that are relatively prime to are   and . There are of these numbers so .

From the definition follows that for every prime number ,

is valid.

The question is how can we determine for ”large” . The multiplicative property of the Euler’s phi function, given in the following theorem, helps us to answer that question.

Theorem 1. If and are relatively prime numbers, then

Example 1. Determine .

Solution.

We write the number as the product of two relatively prime factors: . By the formula above

is valid. Since and , it follows

More effective formula to determine the number is given in the following theorem.

Theorem 2. If is a prime factor decomposition of the natural number , then

is valid.

Example 2.  Determine .

Solution.

Prime factor decomposition of the number is

By the formula from the Theorem 2. we have

Therefore, .

Shares