Euler's totient function

:For other meanings, see Euler function (disambiguation).

Computing Euler's function

It follows from the definition that φ(1) = 1, and φ(n) is (p − 1)pk−1 when n is the kth power of a prime number pk. Moreover, φ 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 thus be computed using the fundamental theorem of arithmetic: if

Related Topics:
Prime number - Multiplicative function - Bijection - Chinese remainder theorem - Fundamental theorem of arithmetic

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:n = p1k1 ... prkr

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

where the pj are distinct primes,

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

then

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:φ(n) = (p1−1) p1k1−1 ... (pr−1) prkr−1.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

This last formula is an Euler product and is often written as

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:arphi(n)=nprod_{p|n}left(1-rac{1}{p} ight)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

with the product ranging only over the distinct primes pr.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~