Euler’s phi function
For arbitrarily chosen natural number $m$, we observe the following sequence:
$$1, 2, 3, \ldots, m.$$
The totient $\varphi(m)$ of a positive integer $m$ greater than 1 is defined to be the number of positive integers less than $m$ that are relatively prime to $m$. In this way we obtain a function $\varphi: \mathbb{N} \to \mathbb{N}$ defined with $m \to \varphi(m)$. $\varphi (1)$ 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 $\varphi (12)$. We observe the sequence:
$$1, 2, 3, \ldots, 12.$$
Numbers that are relatively prime to $12$ are $1, 5, 7$ and $11$. There are $4$ of these numbers so $\varphi(12) = 4$.
From the definition follows that for every prime number $p$,
$$\varphi(p) = p – 1$$
is valid.
The question is how can we determine $\varphi(m)$ for ”large” $m$. The multiplicative property of the Euler’s phi function, given in the following theorem, helps us to answer that question.
Theorem 1. If $m$ and $n$ are relatively prime numbers, then
$$\varphi ( m \cdot n) = \varphi(m) \cdot \varphi (n).$$
Example 1. Determine $\varphi(56)$.
Solution.
We write the number $56$ as the product of two relatively prime factors: $56 = 7 \cdot 8$. By the formula above
$$\varphi(56) = \varphi (7) \cdot \varphi (8)$$
is valid. Since $\varphi(7) = 6$ and $\varphi(8) = 4$, it follows
$$\varphi(56) = 6 \cdot 4 = 24.$$
More effective formula to determine the number $\varphi(m)$ is given in the following theorem.
Theorem 2. If $ m = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdots p_r^{\alpha_r}$ is a prime factor decomposition of the natural number $m$, then
$$\varphi(m) = m \left(1 – \frac{1}{p_1} \right) \left( 1 – \frac{1}{p_2}\right) \cdots \left ( 1 – \frac{1}{p_r} \right)$$
is valid.
Example 2. Determine $\varphi(375)$.
Solution.
Prime factor decomposition of the number $375$ is
$$375 = 3 \cdot 5^3.$$
By the formula from the Theorem 2. we have
$$\varphi (375) = 375 \cdot \left( 1- \frac{1}{3} \right) \cdot \left( 1 – \frac{1}{5} \right) $$
$$= 375 \cdot \frac{2}{3} \cdot \frac{4}{5}$$
$$= 200$$
Therefore, $\varphi(375) = 200$.
