Latest Tweets

Free math worksheets

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

    \[\begin{aligned} \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. \\ \end{aligned}\]

Therefore, \varphi(375) = 200.

 

Shares