Euler's totient function
The totient function of a positive integer is the number of integers less than which have no factors in common with (i.e. such that the greatest common divisor of and 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 using the formula
Some properties of the totient function
- For a prime number , all numbers less than are coprime to it, so .
- For every , . This is because there are only numbers less than .
- The totient may also be bounded below: for it satisfies . \
- A sharper bound is
- How fast does the totient function grow? For large , "on average". One way to make this precise is by stating , while in contrast