Euler's totient function
Euler's totient function, , determines the number of integers less than a given positive integer that is relatively prime to that integer.
Formulas
Given the prime factorization of , then one formula for is .
Identities
For prime p, , because all numbers less than are relatively prime to it.
For relatively prime , .
In fact, we also have , we have .
For any , we have where the sum is taken over all divisors d of .