Difference between revisions of "Euler's phi function"

Revision as of 12: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 $n = p_1^{a_1}p_2^{a_2} \cdots p_n^{a_n}$ , then one formula for $\phi(n)$ is: $\phi(n) = n(1-\frac{1}{p_1})(1-\frac{1}{p_2}) \cdots (1-\frac{1}{p_n})$

Identities

For prime p, $\phi(p)=p-1$ , because all numbers less than p are relatively prime to it.

Other Names

Totient Function
Euler's Totient Function

@@ Line 8: / Line 8: @@
 === 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 [[prime]] p, <math>\phi(p)=p-1</math>, because all numbers less than p are relatively prime to it.
-For relatively prime <math>a, b</math>, <math> \phi(a)\phi(b) = \phi(ab) </math>.
 === Other Names ===

Page

Toolbox

Search

Difference between revisions of "Euler's phi function"

Revision as of 12:34, 18 June 2006

Formulas

Identities

Other Names