Euler's Totient Function

number-theory

Definition

Euler's Totient Function

Euler’s totient function $\varphi (m)$ function 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\}|$$

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

Fermat’s Little Theorem

Fermat's Little Theorem

Let $a,m\in \mathbb{Z}$ $\gcd (a,m)=1$, then:

$$a^{\phi (m)}\equiv 1(\mathrm{mod}m)$$

todo