Euler's totient function

From Wikipedia, the free encyclopedia
Jump to: navigation, search
The first thousand values of \phi(n)

In number theory, the totient \phi(n) of a positive integer is the number of integers less than the number which are coprime to n (they share no factors).

For example, \phi(8) = 4, because the four numbers 1, 3, 5 and 7 are coprime to 8. The function \phi used here is the totient function, usually called the Euler totient or Euler's totient, after the Swiss mathematician Leonhard Euler, who studied it. The totient function is also called Euler's phi function or simply the phi function, since the Greek letter Phi (\phi) is so commonly used for it. The cototient of n is defined as n - \phi(n).

The totient function is important mainly because it gives the size of the multiplicative group of integers modulo n. More precisely, \phi(n) is the order of the group of units of the ring \mathbb{Z}/n\mathbb{Z}. This fact, together with Lagrange's theorem, provides a proof for Euler's theorem.