Euler's totient function φ(n), 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 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 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 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.)
The value of φ(n) is equal to the order of the group of units of the
ring Z/nZ.
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
Cn (and therefore also to the degree of the cyclotomic
polynomial Φn). Since every element of
Cn generates a cyclic subgroup and
the subgroups of Cn are of the form
Cd where d divides n (written as
d|n), we get
-
where the sum extends over all positive divisors d of
n.
This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Euler's totient function".
|