Euler's totient function

related topics
{math, number, function}
{work, book, publish}
{rate, high, increase}

In number theory, the totient \varphi(n) of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n (i.e. having no common positive factors other than 1). In particular \varphi(1)=1 since 1 is coprime to itself (1 being the only natural number with this property). For example, \varphi(9)=6 since the six numbers 1, 2, 4, 5, 7 and 8 are coprime to 9. The function \varphi 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. The totient function is also called Euler's phi function or simply the phi function, since it is commonly denoted by the Greek letter phi (\varphi). The cototient of n is defined as n - \varphi(n), in other words the number of positive integers less than or equal to n that are not coprime to n.

The totient function is important mainly because it gives the size of the multiplicative group of integers modulo n. More precisely, \varphi(n) is the order of the group of units of the ring \mathbb{Z}/n\mathbb{Z}. This fact, together with Lagrange's theorem on the possible sizes of subgroups of a group, provides a proof for Euler's theorem that a^{\varphi(n)}\equiv 1 \pmod{n} for all a coprime to n. The totient function also plays a key role in the definition of the RSA encryption system.


Full article ▸

related documents
Symmetric group
Convex set
Kruskal's algorithm
Local ring
Golomb coding
Carmichael number
Group representation
Goodstein's theorem
Search algorithm
Division algebra
Constant of integration
Analytic geometry
Exact sequence
Diophantine set
Mersenne twister
Mersenne prime
Lebesgue measure
Separable space
Kolmogorov space
Probability space
Laurent series
Automated theorem proving
Cartesian product
Linear equation
Banach fixed point theorem
Inverse limit
Axiom of regularity
Conjunctive normal form