euler's totient function

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

\mathbb{Z}/n\mathbb{Z}

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

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

\varphi(n)=n\prod_{p|n}\left(1-\frac{1}{p}\right)

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

\sum_{d\mid n}\varphi(d)=n

where the sum extends over all positive divisors d of n. We can now use the Mbius inversion formula to "invert" this sum and get another formula for φ(n):

\varphi(n)=\sum_{d\mid n} d \mu(n/d)

where

\mu

is the usual Mbius function defined on the positive integers. If a is coprime to n, that is, (a,n)=1 then

a^{\varphi(n)}=1\mod n

Generating functions

A Dirichlet series involving φ(n) is

\sum_{n=1}^{\infty} \frac{\varphi(n)}{n^s}=\frac{\zeta(s-1)}{\zeta(s)}.

A Lambert series generating function is

\sum_{n=1}^{\infty} \frac{\varphi(n) q^n}{1-q^n}= \frac{q}{(1-q)^2}

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⁻¹

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:

\frac{1}{n^2} \sum_{k=1}^n \varphi(k)= \frac{3}{\pi^2} + \mathcal{O}\left(\frac{\ln n }{n}\right)

where the big O is the Landau symbol.

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
$\phi(n)$	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
$\phi(n)$	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
$\phi(n)$	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	70	71	72	73	74	75	76	77	78	79	80
$\phi(n)$	60	30	36	32	48	20	66	32	44	24	70	24	72	36	40	36	60	24	78	32

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.

<< Previous

Word Browser

Next >>

john burgee
frank gehry
cass gilbert
michael graves
walter burley griffin
jean eugne robert houdin
stage name
cream (band)
wallace harrison
raymond hood
easter island

philip johnson
pritzker prize
hector berlioz
pseudonymity
kenzo tange
nickname
venus de milo
bayonet
olympic
rock creek park
urban planner

palo alto, california
san jose, california
asia pacific network information centre
hegemony
fermat's little theorem
minkowski's theorem
goddess worship
quinoa
count noun
hazrat inayat khan
statcoulomb

esu
vilayat inayat khan
cinnabar
louis gathmann
sufi order international
cinnamon
illusion
tenrikyo
dave berg (cartoonist)
vulcan, alberta
2060 chiron