Latest Tweets

Free math worksheets

Euler’s phi function

For some natural number m, we observe the following sequence:

    \[1, 2, 3, \ldots, m.\]

The number of members of this sequence, which are relatively prime to the number m, we denote as \varphi(m). In this way we obtain a function \varphi: \mathbb{N} \to \mathbb{N} defined with m \to \varphi(m). We call this function the Euler’s phi function and it is very important in the number theory.

For instance, 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, and there are 4, so \varphi(12) = 4.

From the definition follows that for every prime number p,

    \[\varphi(p) = p - 1\]

is valid.

The question now is how would we determine \varphi(m) for ”large” m. That help us the multiplicative property of the Euler’s phi function, given in the following theorem.

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 65 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