Euler's totient function

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

<math>\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}</math>.

Some properties of the totient function

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

<math>\varphi(n) > \frac{n}{e^\gamma \log \log n + \frac{3}{\log \log n}}</math>

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