|
|
| (5 intermediate revisions by 2 users not shown) |
| Line 1: |
Line 1: |
| − | '''Euler's phi function''' determines the number of integers less than a given positive integer that are [[relatively prime]] to that integer.
| + | #REDIRECT [[Euler's totient function]] |
| − | | |
| − | === Formulas ===
| |
| − | | |
| − | Given the [[prime factorization]] of <math>n = p_1^{a_1}p_2^{a_2} \cdots p_n^{a_n}</math>, then one formula for <math>\phi(n)</math> is:
| |
| − | <math> \phi(n) = n(1-\frac{1}{p_1})(1-\frac{1}{p_2}) \cdots (1-\frac{1}{p_n}) </math>
| |
| − | | |
| − | === Identities ===
| |
| − | | |
| − | For [[prime]] <math> p </math>, <math>\phi(p)=p-1</math>, because all numbers less than <math> p </math> are relatively prime to it.
| |
| − | | |
| − | For relatively prime <math>a, b</math>, <math> \phi(a)\phi(b) = \phi(ab) </math>.
| |
| − | | |
| − | === Other Names ===
| |
| − | | |
| − | * Totient Function
| |
| − | * Euler's Totient Function
| |
