Latest Tweets

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

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$.