Euler's Totient Function

Definition

Euler's totient (phi) function, denoted with the greek letter phi and written $\varphi(n)$ , is a function that counts the number of integers up to $n$ that are relatively prime or coprime to $n$ . Relatively prime and coprime mean the same thing, and two numbers are said to be coprime when their greatest common divisor $(gcd)$ equals $1$ .

Basic Examples

Let's look at a few simple examples to understand how the function works.

For $n = 1$ :
$\varphi(1) = 1$ because the only integer up to 1 that is relatively prime to 1 is 1 itself.

For $n = 2$ :
$\varphi(2) = 1$ because the only integer up to 2 that is relatively prime to 2 is 1.

For $n = 3$ :
$\varphi(3) = 2$ because the integers up to 3 that are relatively prime to 3 are 1 and 2.

Properties

Euler's totient function has several important properties. For instance, if $p$ is a prime number, then:

\varphi(p) = p - 1

This is because a prime number $p$ is only divisible by 1 and itself, meaning all numbers less than $p$ are relatively prime to $p$ .

Additionally, for two relatively prime numbers $m$ and $n$ :

\varphi(mn) = \varphi(m) \cdot \varphi(n)

This multiplicative property helps in calculating Euler's totient function for larger numbers by breaking them down into their prime factors.

Calculating Euler's Totient Function

Euler's totient function can be calculated using the formula:

\varphi(n) = n \left(1 - \frac{1}{p_1}\right) \left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_k}\right)

where $p_1, p_2, \ldots, p_k$ are the distinct prime factors of $n$ .

For example, to calculate $\varphi(12)$ :
1. $12 = 2^2 \cdot 3$
2. The prime factors of 12 are 2 and 3
3. Apply the formula:
$\varphi(12) = 12 \left(1 - \frac{1}{2}\right) \left(1 - \frac{1}{3}\right) = 12 \cdot \frac{1}{2} \cdot \frac{2}{3} = 4$
Therefore, $\varphi(12) = 4$ .

Applications

Euler's totient function is used in various fields of number theory and cryptography. One of its most famous applications is in Euler's Theorem, which states that for any integer $a$ and $n$ that are relatively prime:

a^{\varphi(n)} \equiv 1 \pmod{n}

This theorem is a generalization of Fermat's Little Theorem and is crucial in the RSA encryption algorithm, which is widely used in securing digital communications.