Euler's totient function (original) (raw)

Euler's totient function φ(n), named after Leonhard Euler, is an important function in number theory.

If n is a positive integer, then φ(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.

φ is a (conditionally) 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_k_1 ... p r k _r_where the p j are distinct primes, then φ(n) = (_p_1-1) _p_1_k_1-1 ... (_p_r-1) _p_r_k_r-1. (Sketch of proof: the case r = 1 is easy, and the general result follows by multiplicativity.)

The value of φ(n) is equal to the order of the group of units of the ring Z/nZ (see modular arithmetic). This, together with Lagrange's theorem, provides a proof for Euler's theorem.

φ(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):

A Dirichlet series involving φ(n) is