The Euler's totient function reference article from the English Wikipedia on 24-Apr-2004 (provided by Fixed Reference: snapshots of Wikipedia from wikipedia.org)

Euler's totient function

Euler's totient function φ(n) is defined, for any positive integer n, 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.

Named after the Swiss mathematician Leonhard Euler, φ(n) is an important function in number theory, chiefly because it is the cardinality of the multiplicative group of integers modulo n — more precisely, the order of the group of units of the ring Z/nZ (see modular arithmetic). This fact, together with Lagrange's theorem, provides a proof for Euler's theorem.

Table of contents

1 Computing Euler's function 2 Other properties 3 Generating function 4 Growth of the function 5 Some values of the function

Computing Euler's function

It follows from the definition that φ(1) = 1, and φ(n) is (p-1)p^k-1 when n is the kth power of a prime p^k. Moreover, if m and n are coprime then φ(mn) = φ(m). (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 AxB and C, via the Chinese Remainder Theorem.) The value of φ(n) can thus be computed using the fundamental theorem of arithmetic: if

n = p₁^k₁ ... p_r^k_r

where the p_j are distinct primes, then

φ(n) = (p₁-1) p₁^k₁-1 ... (p_r-1) p_r^k_r-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

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
	1	1	2	2	4	2	6	4	6	4	10	4	12	6	8	8	16	6	18	8

	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40
	12	10	22	8	20	12	18	12	28	8	30	16	20	16	24	12	36	18	24	16

	41	42	43	44	45	46	47	48	49	50	51	52	53	54	55	56	57	58	59	60
	40	12	42	20	24	22	46	16	42	20	32	24	52	18	40	24	36	28	58	16

	61	62	63	64	65	66	67	68	69	...
	60	30	36	32	48	20	66	32	44	...