Euler's totient function
The totient function 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 . The totient function can be computer from a prime factorization of n using the formula
Some properties of the totient function
- For a prime number p, all numbers less than p are coprime to it, so .
- For every n, . This is because there are only n − 1 numbers less than n.
- The totient may also be bounded below: for n > 6 it satisfies . \
- A sharper bound is
- How fast does the totient function grow? For large n, "on average". One way to make this precise is by stating , while in contrast