Difference between revisions of "Euler's phi function"

(Fixed LaTeX on old version; restores old info)
 
(3 intermediate revisions by the same user 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]] p, <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
 

Latest revision as of 15:36, 18 June 2006