= Euler totient function
{c}
{title2=$\varphi(n)$}
{wiki}
= Euler's totient function
{c}
{synonym}
= Euler totient
{c}
{synonym}
= Euler's totient
{c}
{synonym}
= Euler’s totient
{c}
{synonym}
= Totient
{synonym}
<Euler's totient function> is the <arithmetic function>
$$
\varphi(n)=\#\{j\in\{1,\ldots,n\}:\gcd(j,n)=1\},\qquad n>0.
$$
It counts the <congruence classes> modulo $n$ represented by <integers> <coprime> to $n$. In particular, $\varphi(1)=1$, since $\gcd(1,1)=1$. For $12$, the <coprime integers> among $1,\ldots,12$ are $1,5,7,11$, so $\varphi(12)=4$; they form a <reduced residue system>. https://darijgrinberg.gitlab.io/floor.pdf[Darij Grinberg, MIT 18.781 lecture notes, Definition 2.1.2]{ref}
Counting these <congruence classes> is useful because they are exactly the classes with <modular multiplicative inverses>. Their number supplies the exponent in <Euler theorem>. <Möbius inversion> gives the product formula
$$
\varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right),
$$
where $p$ runs over distinct <prime factors> of $n$. Thus $\varphi(p^a)=p^{a-1}(p-1)$ for <prime powers> with $a\geq1$, and $\varphi(12)=12(1-1/2)(1-1/3)=4$. The product for $n=1$ is an <empty product>, so it gives the same convention $\varphi(1)=1$.
Back to article page
