Euler’s Totient Function 𝜑(n)

Euler’s totient function plays a vital role in number theory. It counts all the positive integers up to a given number $n$ that are coprime to $n$.

We’ll make use of it when we want to determine the number of generators in cyclic groups and when we want to describe the order of the multiplicative group of integers modulo $n$.

Definition

The number of positive integers $a < n$ that are relatively prime to $n \in \mathbb{N}$ is called Euler’s totient function 𝜑(n), defined by the rule

$$\varphi (n) = \left | \left \{ a \in \mathbb{N} \mid 0 \le a < n : gcd(a , n) = 1 \right \} \right |.$$