# 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).$