Eulers phi function

HomePage | Recent changes | View source | Discuss this page | Page history | Log in |

Printable version | Disclaimers | Privacy policy

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 = p1k1 ... prkr where the pj are distinct primes, then φ(n) = (p1-1) p1k1-1 ... (pr-1) prkr-1. (Sketch of proof: the case r = 1 is easy, and the general result follows by multiplicativity.)