Euler's totient function

The totient function $\varphi$ of a positive integer $n$ is the number of integers $k$ less than $n$ which have no factors in common with $n$ (i.e. such that the greatest common divisor of $k$ and $n$ is 1). For example, the numbers 1, 5, 7, and 11 have no factors in common with 12, so $\varphi (12)=4$. The totient function can be computer from a prime factorization of $n$ using the formula

$\varphi \left(p_{1}^{k_{1}}\cdots p_{n}^{k_{n}}\right)=(p_{1}-1)p_{1}^{k_{1}-1}\cdot \cdots \cdot (p_{n}-1)p_{n}^{k_{n}-1}$.

Some properties of the totient function

• For a prime number $p$, all numbers less than $p$ are coprime to it, so $\varphi (p)=p-1$.
• For every $n$, $\varphi (n)\leq n-1$. This is because there are only $n-1$ numbers less than $n$.
• The totient may also be bounded below: for $n>6$ it satisfies $\varphi (n)>{\sqrt {n}}$. \
• A sharper bound is

$\varphi (n)>{\frac {n}{e^{\gamma }\log \log n+{\frac {3}{\log \log n}}}}$

• How fast does the totient function grow? For large $n$, $\phi (n)\approx n$ "on average". One way to make this precise is by stating ${\frac {1}{n^{2}}}\sum _{k=1}^{n}\varphi (k)={\frac {3}{\pi ^{2}}}+O\left({\frac {\log n}{n}}\right)$, while in contrast ${\frac {1}{n^{2}}}\sum _{k=1}^{n}k={\frac {1}{2}}+O\left({\frac {1}{n}}\right).$