Euler's Totient Function

number-theory

Definition

Euler's Totient Function

Euler’s totient function $\varphi (m)$ maps a modulus $m$ to the number of invertible residue classes w.r.t. to $m$:

$$\phi (m)=|\{a\in \mathbb{Z}\mid 1\le a\le m\wedge \gcd (a,m)=1\}|$$

It maps each integer $n$ to the number of integers up to $n$ that are coprime to $n$ (i.e. gcd is 1).

Product Formula

Product Formula

Let $m=p_1^{e_1}\cdot \dots \cdot p_r^{e_r}$ the prime factorisation of of $m$ (with $p_j\in \mathbb{P}$ are different in pairs and $e_j>0$), then:

$$\phi (m)=m\cdot \prod _{i=1}^r(p_i-1)$$