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. 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 the letter Phi (φ) is so commonly used for it. The totient function is important chiefly 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 . This fact, together with Lagrange's theorem, provides a proof for Euler's theorem. ## Computing Euler's function
It follows from the definition that φ(1) = 1, and φ(*n*) is (*p*-1)*p*^{k-1} when *n* is the *k*th power of a prime *p*^{k}. Moreover, φ is a multiplicative function; if *m* and *n* are coprime then φ(*mn*) = φ(*m*)φ(*n*). (Sketch of proof: let *A*, *B*, *C* be the sets of residue classes modulo-and-coprime-to *m*, *n*, *mn* respectively; then there is a bijection between *A*x*B* and *C*, via the Chinese remainder theorem.) The value of φ(*n*) can thus be computed using the fundamental theorem of arithmetic: if *n* = *p*_{1}^{k1} ... *p*_{r}^{kr} where the *p*_{j} are distinct primes, then - φ(
*n*) = (*p*_{1}−1) *p*_{1}^{k1−1} ... (*p*_{r}−1) *p*_{r}^{kr−1}. This last formula is an Euler product and is often written as with the product ranging only over the distinct primes *p*_{r}.
## Other properties The number φ(*n*) is also equal to the number of generators of the cyclic group *C*_{n} (and therefore also to the degree of the cyclotomic polynomial Φ_{n}). Since every element of *C*_{n} generates a cyclic subgroup and the subgroups of *C*_{n} are of the form *C*_{d} where *d* divides *n* (written as *d*|*n*), we get where the sum extends over all positive divisors *d* of *n*. We can now use the Möbius inversion formula to "invert" this sum and get another formula for φ(*n*):
where μ is the usual Möbius function defined on the positive integers. If *a* is coprime to *n*, that is, (*a*,*n*)=1 then - .
A Dirichlet series involving φ(*n*) is A Lambert series generating function is which holds for |*q*|<1.
## Growth of the function The growth of φ(*n*) as a function of *n* is an interesting question, since the first impression from small *n* that φ(*n*) might be noticeably smaller than *n* is somewhat misleading. Asymptotically we have *n*^{1−ε} < φ(*n*) < *n* for any given ε > 0 and *n* > *N*(ε). In fact if we consider - φ(
*n*)/*n* we can write that, from the formula above, as the product of factors - 1 −
*p*^{−1} taken over the prime numbers *p* dividing *n*. Therefore the values of *n* corresponding to particularly small values of the ratio are those *n* that are the product of an initial segment of the sequence of all primes. From the prime number theorem it can be shown that a constant ε in the formula above can therefore be replaced by *C* loglog *n*/log *n*. This behavior also holds in an average sense: where the big O is the Landau symbol.
## Some values of the function *n* | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | φ(*n*) | 1 | 1 | 2 | 2 | 4 | 2 | 6 | 4 | 6 | 4 | 10 | 4 | 12 | 6 | 8 | 8 | 16 | 6 | 18 | 8 | *n* | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | φ(*n*) | 12 | 10 | 22 | 8 | 20 | 12 | 18 | 12 | 28 | 8 | 30 | 16 | 20 | 16 | 24 | 12 | 36 | 18 | 24 | 16 | *n* | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | φ(*n*) | 40 | 12 | 42 | 20 | 24 | 22 | 46 | 16 | 42 | 20 | 32 | 24 | 52 | 18 | 40 | 24 | 36 | 28 | 58 | 16 | *n* | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | φ(*n*) | 60 | 30 | 36 | 32 | 48 | 20 | 66 | 32 | 44 | 24 | 70 | 24 | 72 | 36 | 40 | 36 | 60 | 24 | 78 | 32 | ## See also ## References - Milton Abramowitz and Irene A. Stegun,
*Handbook of Mathematical Functions*, (1964) Dover Publications, New York. ISBN 486-61272-4 . See paragraph 24.3.2. |