Euler's totient function

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

<math>\sum_{d\mid n}\varphi(d)=n</math>