Difference between revisions of "Euler's totient function"
| Line 10: | Line 10: | ||
For relatively prime <math>{a}, {b}</math>, <math> \phi{(a)}\phi{(b)} = \phi{(ab)} </math>. | For relatively prime <math>{a}, {b}</math>, <math> \phi{(a)}\phi{(b)} = \phi{(ab)} </math>. | ||
| + | |||
| + | For any <math>n</math>, we have <math>\sum_{d|n}\phi(d)=n</math> where the sum is taken over all divisors d of <math> n </math>. | ||
=== See also === | === See also === | ||
Revision as of 19:59, 18 June 2006
Euler's totient function, 
, determines the number of integers less than a given positive integer that are 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 
, 
.
For any 
, we have 
where the sum is taken over all divisors d of .
