Difference between revisions of "Phi function"

Latest revision as of 11:56, 13 July 2006

Redirect to:

@@ Line 1: / Line 1: @@
 #REDIRECT [[Euler's totient function]]
-We want to determine an explicit formula <math>\phi(n)</math> for how many numbers less than a given number n is [[relatively prime]] to n.
-Begin by evaluating <math>\phi(p)</math> for some prime p. By definition, there are <math>p-1</math> such numbers.  Now let's try <math>\phi(p^a)</math>.  Since p is prime, the only numbers not relatively prime to it must have p as a factor.  These numbers are <math>p, p^2, ..., p^{a-1}</math>.  Hence, <math>\phi(p^a)=p^a-p^{a-1}=p^a(1-\frac{1}{p})</math>.
-For two primes p and q, <math>\phi(pq)= pq-p-q+1=(p-1)(q-1)= pq(1-\frac{1}{p})(1-\frac{1}{q})</math>.  These two specific examples indicate that phi function is [[multiplicative]].  Indeed, for any composite number <math>m=p_1p_2...p_n</math>, where each p_i is prime, we find that <math>\phi(m)=m(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_n})</math>.