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

In number theory, the totient 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 since 1 is coprime to itself (1 being the only natural number with this property). For example, since the six numbers 1, 2, 4, 5, 7 and 8 are coprime to 9. 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. 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 (). The cototient of n is defined as , 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, is the order of the group of units of the ring . This fact, together with Lagrange's theorem on the possible sizes of subgroups of a group, provides a proof for Euler's theorem that for all a coprime to n. The totient function also plays a key role in the definition of the RSA encryption system.
Contents
Full article ▸


related documents 
Symmetric group 
Convex set 
Kruskal's algorithm 
Local ring 
Golomb coding 
Carmichael number 
Group representation 
Goodstein's theorem 
Controllability 
Search algorithm 
Division algebra 
Constant of integration 
Analytic geometry 
Wellorder 
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 
