Redirected from Euler's phi 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 moduloandcoprimeto 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_{1}^{k1} ... p_{r}^{kr} where the p_{j} are distinct primes, then φ(n) = (p_{1}1) p_{1}^{k11} ... (p_{r}1) p_{r}^{kr1}. (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 dn), we get
Search Encyclopedia

Featured Article
