# 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.
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 **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 . This fact, together with Lagrange's theorem, provides a proof for Euler's theorem.

## Contents

## 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 number *p*. 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

This last formula is a Euler product and is often written as

with the product ranging only over the distinct primes *p*_{r}.

### Computing example

## Some values of the function

+0 | +1 | +2 | +3 | +4 | +5 | +6 | +7 | +8 | +9 | +10 | +11 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|

0+ | 1 | 1 | 2 | 2 | 4 | 2 | 6 | 4 | 6 | 4 | 10 | |

12+ | 4 | 12 | 6 | 8 | 8 | 16 | 6 | 18 | 8 | 12 | 10 | 22 |

24+ | 8 | 20 | 12 | 18 | 12 | 28 | 8 | 30 | 16 | 20 | 16 | 24 |

36+ | 12 | 36 | 18 | 24 | 16 | 40 | 12 | 42 | 20 | 24 | 22 | 46 |

48+ | 16 | 42 | 20 | 32 | 24 | 52 | 18 | 40 | 24 | 36 | 28 | 58 |

60+ | 16 | 60 | 30 | 36 | 32 | 48 | 20 | 66 | 32 | 44 | 24 | 70 |

72+ | 24 | 72 | 36 | 40 | 36 | 60 | 24 | 78 | 32 | 54 | 40 | 82 |

## Properties

The number (*n*) is also equal to the number of possible 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.

According to Euler's theorem, if *a* is coprime to *n*, that is, gcd(*a*,*n*) = 1, then

This follows from Lagrange's theorem and the fact that *a* belongs to the multiplicative group of if and only if *a* is coprime to *n*.

## Generating functions

A Dirichlet series involving (*n*) is

A Lambert series generating function is

which converges 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*log log*n*/log*n*.

is also generally close to *n* in an average sense:

where the big O is the Landau symbol. This also says that the probability of two positive integers chosen at random from [1,*n*] x [1,*n*] being relatively prime is . A proof of this formula may be found here.

## Other formulas involving Euler's function

- for

- for

Proofs of some of these identities may be found here.

## Inequalities

Some inequalities involving the function are:

- for n > 2, where γ is Euler's constant,

- for
*n*> 0,

and

- for
*n*> 6.

For prime *n*, clearly (*n*) = *n*-1. For composite *n* we have

- (for composite
*n*).

For all :

For randomly large n, these bounds still cannot be improved, or to be more precise :

lim inf and lim sup

A pair of inequalities combining the function and the σ divisor function are:

- for
*n*> 1.

## See also

- Nontotient
- Noncototient
- Highly totient number
- Sparsely totient number
- Highly cototient number
- Divisor function

## 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.

- Eric Bach and Jeffrey Shallit,
*Algorithmic Number Theory*, volume 1, 1996, MIT Press. ISBN 0-262-02405-5, see page 234 in section 8.8.

- Kirby Urner,
*Computing totient function in Python and scheme*, (2003)