Difference between revisions of "Euler's phi function"
(→See also) |
|||
| Line 4: | Line 4: | ||
Given the [[prime factorization]] of <math>{n} = {p}_1^{e_1}{p}_2^{e_2} \cdots {p}_n^{e_n}</math>, then one formula for <math>\phi(n)</math> is <math> \phi(n) = n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right) \cdots \left(1-\frac{1}{p_n}\right) </math>. | Given the [[prime factorization]] of <math>{n} = {p}_1^{e_1}{p}_2^{e_2} \cdots {p}_n^{e_n}</math>, then one formula for <math>\phi(n)</math> is <math> \phi(n) = n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right) \cdots \left(1-\frac{1}{p_n}\right) </math>. | ||
| − | |||
| − | |||
=== Identities === | === Identities === | ||
| Line 13: | 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>. | ||
| − | === | + | === See also === |
| − | * | + | * [[Number theory]] |
| − | * Euler's Totient | + | * [[Prime]] |
| + | * [[Euler's Totient Theorem]] | ||
Revision as of 15:34, 18 June 2006
Euler's phi 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 
, 
.
