Euler's totient function

:For other meanings, see Euler function (disambiguation).

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

In number theory, the totient φ(n) of a positive integer n is defined to be the number of positive integers less than or equal to n and coprime to n. For example, φ(8) = 4 since the four numbers 1, 3, 5 and 7 are coprime to 8.

Related Topics:
Number theory - Positive integer - Coprime

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The function φ so defined is the totient function.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The totient is usually called the Euler totient or Euler's totient, after the Swiss mathematician Leonhard Euler, who studied it.

Related Topics:
Swiss - Leonhard Euler

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The totient function is also called Euler's phi function or simply the phi function, since the letter Phi (φ) is so commonly used for it. The cototient of n is defined as n - φ(n).

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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

Related Topics:
Group - Modulo - Unit - Ring - Lagrange's theorem - Euler's theorem

~ ~ ~ ~ ~ ~ ~ ~ ~ ~