Difference between revisions of "Euler's totient function"
m (it's the integers that are relatively prime, not the number) |
|||
| Line 11: | Line 11: | ||
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>. | ||
| − | In fact, we also have <math>{a}, {b}</math> | + | In fact, we also have for any <math>{a}, {b}</math> that <math>\phi{(a)}\phi{(b)}\gcd(a,b)=\phi{(ab)}\phi({\gcd(a,b)})</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>. | 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>. | ||
Revision as of 03:39, 20 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 
, 
.
In fact, we also have for any that 
.
For any 
, we have 
where the sum is taken over all divisors d of .
