Euler totient function

The Euler totient function $\phi$ of a positive integer $n$ counts the number of integers $0<k<n$ that are relatively prime to $n$; that is,

$\phi (n)=\left|\left\{k\in {\mathbb {Z} _{n}}^{*}~\mid ~\gcd {\left(k,n\right)}=1\right\}\right|$

where ${\mathbb {Z} _{n}}^{*}$ is the set of nonzero integers modulo $n$.

Properties

Endomorphic

The Euler totient function is an endomorphism on multiplicative groups of integers. If $G$ represents such a group, then $\phi$ maps $G$ on itself and follows the homomorphism property.

Stated simply, for any positive integers $m$ and $n$, where $\gcd {\left(m,n\right)}=1$, then

$\phi (m\cdot n)=\phi (m)\cdot \phi (n)$

Totient of Prime Numbers

If $p$ is a prime number, then

$\phi (p)=p-1$

Proof. Since $\gcd {\left(p,m\right)}=1$ for all $m\in {\mathbb {Z} _{p}}^{*}$, we have $\left|{\mathbb {Z} _{p}}^{*}\right|=p-1$.

quod erat demonstrandum

Totient of Prime Powers

If $p$ is a prime number and $r$ is an integer greater than $1$, then

${\begin{aligned}\phi \left(p^{k}\right)&=p^{r}-p^{r-1}\\&=p^{r-1}\,\left(p-1\right)\end{aligned}}$

Proof. Since $p$ is prime, $\gcd {\left(p^{r},m\right)}\in \left\{1,p,p^{2},\ldots ,p^{r}\right\}$ for any integer $m$. Now $\gcd {\left(p^{r},m\right)}\neq 1$ holds only when $m$ is a multiple of $p$. The multiples of $p$ that are less than or equal to $p^{r}$ are Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S = \left\{ p, 2p, 3p, \ldots, p^{r − 1} \, p = p^r \right\}} , of which there are Failed to parse (syntax error): {\displaystyle \left| S \right| = p^{r − 1}} . Therefore the other Failed to parse (syntax error): {\displaystyle p^r − p^{r − 1}} numbers are all relatively prime to $p^{r}$.

quod erat demonstrandum

Totient of Integers in General

If $\left\{p_{1}^{r_{1}},p_{2}^{r_{2}},\ldots ,p_{k}^{r_{k}}\right\}$ represents the prime factorization of an integer $n$, then using the formulae and properties above, we have

$\phi (n)=\prod _{i=1}^{k}{p_{i}}^{r_{i}-1}\,\left(p_{i}-1\right)$

See Also

• Fermat's little theorem
• Euler's theorem