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

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