Encyclopedia > Euler's phi function

  Article Content

Euler's totient function

Redirected from Euler's phi function

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 (see modular arithmetic). 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

<math>\sum_{d\mid n}\varphi(d)=n</math>
where the sum extends over all positive divisors d of n.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Monty Woolley

... Nominations 1945 - Nominated - Best Actor in a Supporting Role - Since You Went Away 1943 - Nominated - Best Actor in a Leading Role - The Pied Piper Woolley has a ...

 
 
 
This page was created in 39.3 ms