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 
.
