Euler's totient function
Revision as of 23:11, 24 June 2006 by ComplexZeta (talk | contribs) (→Formulas: Removed abuse of notation)
Euler's totient function, , is defined as the number of positive integers less than or equal to a given positive integer that are relatively prime to that integer.
Formulas
The formal definition is .
Given the general prime factorization of , one can compute using the formula .
Identities
For prime p, , because all numbers less than are relatively prime to it.
For relatively prime , .
In fact, we also have for any that .
For any , we have where the sum is taken over all divisors d of .