From Wikipedia, the free encyclopedia

For other functions named after Euler, see List of topics named after Leonhard Euler.

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. 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 ; 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, provides a proof for Euler's theorem.

Contents 1 Computing Euler's function 1.1 Computing example 2 Some values of the function 3 Properties 4 Generating functions 5 Growth of the function 6 Other formulas involving Euler's function 7 Inequalities 8 See also 9 References 10 External links

It follows from the definition that , and . Moreover, is a multiplicative function; if m and n are coprime then . (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 × B and C, via the Chinese remainder theorem.) The value of can thus be computed using the fundamental theorem of arithmetic: if

where the p_j are distinct primes, then

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

with the product ranging only over the distinct primes p dividing n.

In words, this says that the distinct prime factors of 36 are 2 and 3; half of the thirty-six integers from 1 to 36 are divisible by 2, leaving eighteen; a third of those are divisible by 3, leaving twelve coprime to 36. And indeed there are twelve: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, and 35.

	+0	+1	+2	+3	+4	+5	+6	+7	+8	+9
0+		1	1	2	2	4	2	6	4	6
10+	4	10	4	12	6	8	8	16	6	18
20+	8	12	10	22	8	20	12	18	12	28
30+	8	30	16	20	16	24	12	36	18	24
40+	16	40	12	42	20	24	22	46	16	42
50+	20	32	24	52	18	40	24	36	28	58
60+	16	60	30	36	32	48	20	66	32	44
70+	24	70	24	72	36	40	36	60	24	78
80+	32	54	40	82	24	64	42	56	40	88
90+	24	72	44	60	46	72	32	96	42	60

The number 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 ). 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 :

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 iff a is coprime to n.

The two generating functions presented here are both consequences of the fact that

A Dirichlet series involving (n) is

where ζ(s) is the Riemann Zeta function. This is derived as follows:

A Lambert series generating function is

which converges for |q|<1.

This follows from

which is

The growth of as a function of n is an interesting question, since the first impression from small n that might be noticeably smaller than n is somewhat misleading. Asymptotically we have

for any given ε > 0 and n > N(ε). In fact if we consider

we can write that, from the formula above, as the product of factors

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

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, 2, ..., n} being relatively prime approaches 6 / π² when n tends to infinity. A related result is the average order of , which is described by

A proof of these two formulas may be found here.

where m > 1 is a positive integer and ω(m) designates the number of distinct prime factors of m. (This formula counts the number of naturals less than or equal to n and relatively prime to m, additional material is listed among the external links.)

Proofs of some of these identities may be found here.

Some inequalities involving the function are:

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

for n > 0,

and

For prime n, clearly . For composite n we have

(for composite n).

For all n > 1:

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

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

The last two are proved on the page on proofs of totient identities.

• Nontotient
• Noncototient
• Highly totient number
• Sparsely totient number
• Highly cototient number
• Divisor function
• Carmichael function
• Proofs involving the totient function

• Milton Abramowitz and Irene A. Stegun, Handbook of Mathematical Functions, (1964) Dover Publications, New York. ISBN 0-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)

• Miyata, Daisuke & Yamashita, Michinori, Derived logarithmic function of Euler's function
• Bordellès, Olivier, Numbers prime to q in [1,n]
• Calculate ø(n) for a number up to 2³¹ [1]