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