# Euler's totient function

### From Conservapedia

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