Difference between revisions of "Phi function"
Quantum leap (talk | contribs) |
|||
| 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 19:50, 18 June 2006
Redirect to:
We want to determine an explicit formula 
for how many numbers less than a given number n is relatively prime to n.
Begin by evaluating 
for some prime p. By definition, there are 
such numbers. Now let's try 
. Since p is prime, the only numbers not relatively prime to it must have p as a factor. These numbers are 
. Hence, 
.
For two primes p and q, 
. These two specific examples indicate that phi function is multiplicative. Indeed, for any composite number 
, where each p_i is prime, we find that 
.
