Phi function

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})$ .

Page

Toolbox

Search

Phi function