> [!NOTE] **Definition** (Euler Totient Function) > The *Euler Totient Function* is defined on the positive [[Natural Numbers|natural numbers]] as follows $\begin{align} \varphi: \mathbb{N}^{+} & \to \mathbb{N}^{+} \\ n &\mapsto |(\mathbb{Z}/n\mathbb{Z})^{\times}| \end{align}$ > (i.e. the order of [[Unit Group of Integers Modulo n|unit group]] of $\mathbb{Z}/n\mathbb{Z}$ or equivalently, the number of positive integers less than $n$ that are [[Coprime Integers|coprime]] to $n$). > [!Example] Example > By [[Integers modulo prime is a field and integers modulo composite is not]], if $p$ is prime then $(\mathbb{Z} \text{/} p \mathbb{Z})^{\times} = \{[1]_{p}, [2]_{p},\dots,[p-1]_{p}\}$ and so $\varphi(p) = p-1$. # Properties **Multiplicative**: Note that [[Euler's totient function is multiplicative]]: for all $m,n \in \mathbb{N}^{+},$ $\varphi(mn)=\varphi(m)\varphi(n).$ As a result, [[Euler's totient function from prime factorisation]] asserts that $\varphi(p_{1}^{r_{1}}\dots p_{k}^{r_{k}})=\varphi(p_{1}^{r_{1}})\dots \varphi(p_{k}^{r_{k}})=(p_{1}^{r_{1}}-p_{1}^{r_{1}-1})\dots(p_{k}^{r_{k}}-p_{k}^{r_{k}-1}).$ # Applications By [[Euler's theorem (Number Theory)|Euler's theorem]], the order of a unit of $\mathbb{Z}/n\mathbb{Z}$ divides $\varphi(n).$