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, 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}.

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

## Generating function

A Dirichlet series involving φ(*n*) is

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

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

Last updated: 02-03-2005 13:05:11

Last updated: 05-03-2005 17:50:55