Eulers phi function

Euler's phi function, denoted by φ(n) and 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 n and coprime to n. This is also equal to the order of the group of units of the ring Z/nZ (see modulo arithmetic). For example, φ(8) = 4 since the four numbers 1, 3, 5 and 7 are coprime to 8. Also phi(21)=4.

φ 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 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.)