Euler totient function

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

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

where ${{\mathbb{\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 $\varphi$ maps $G$ on itself and follows the homomorphism property.

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

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

Totient of Prime Numbers

If $p$ is a prime number, then

$\varphi (p)=p-1$

Proof. Since

$\gcd (p,m)=1$

for all

$m\in {{\mathbb{\mathbb{Z}}}_p}^{*}$

, we have

$\left|{{\mathbb{\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{array}{rl}\varphi \left(p^k\right)& =p^r-p^{r-1}\\ & =p^{r-1}(p-1)\end{array}$

Proof. Since

$p$

is prime,

$\gcd (p^r,m)\in \{1,p,p^2,\dots ,p^r\}$

for any integer

$m$

. Now

$\gcd (p^r,m)\ne 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 (syntax error): {\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 $\{p_1^{r_1},p_2^{r_2},\dots ,p_k^{r_k}\}$ represents the prime factorization of an integer $n$, then using the formulae and properties above, we have

$\varphi (n)=\prod _{i=1}^k{p_i}^{r_i-1}(p_i-1)$

See Also

• Fermat's little theorem
• Euler's theorem