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