|
|
| (One intermediate revision by one other user not shown) |
| Line 1: |
Line 1: |
| − | 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.
| + | #REDIRECT [[Euler's totient function]] |
| − | 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>.
| |
