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 ,
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 .
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
Example 2. Determine .
Prime factor decomposition of the number is
By the formula from the Theorem 2. we have