Difference between revisions of "Euler's totient function"
m |
m (proofreading) |
||
Line 1: | Line 1: | ||
− | '''Euler's totient function''', <math>\phi(n)</math>, determines the number of integers less than a given positive integer that | + | '''Euler's totient function''', <math>\phi(n)</math>, determines the number of integers less than a given positive integer that is [[relatively prime]] to that integer. |
=== Formulas === | === Formulas === |
Revision as of 17:40, 19 June 2006
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 .