Difference between revisions of "Phi function"

 
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.   
 
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>.
 
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>.
 
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>.

Revision as of 18:50, 18 June 2006

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