# 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:

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

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:

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:

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.