Recall integers and are relatively prime if .
In this section, we will introduce three important multiplicative functions. Note these functions are determined by their values on the prime powers.
You may have guessed the strategy for finding a formula for multiplicative functions. Since , for any prime numbers and , in order to find a formula for , where is a positive integer and is a multiplicative function, we factor as a product of prime powers and our work is reduced to finding a formula for , where is the highest power of the prime dividing .
proof: By Theorem 1.5.11 (1) all divisors of are of the form: , where . Therefore, there are choices for , choices for , etc, which gives us the above formula.
proof: Let and be relatively prime positive integers. We write the prime factorizations as follows:
where all the and are distinct primes.
We have , which, by Theorem 1.6.5, is equal to: .
proof: Let and be relatively prime positive integers with positive divisors and , respectively. Then:
Since , each term is distinct, i.e. , if and (why?). Therefore, the numbers in the above sum represent all of the divisors of and we have proved that .
Let be a positive integer. Recall the Euler phi function, , is the number of positive integers less than or equal to which are relatively prime to .
proof: The positive integers less than or equal to , which are not relatively prime to are all multiples of : . Thus, we can see that there are such integers. Since there are integers less than or equal to , it follows that:
Our next goal is to show that is multiplicative. This result, the Fundamental Theorem of Artithmetic, and Lemma 1.6.8 will give us a formula for , for any positive integer .
We start with a lemma. Recall that for integers and a fixed integer , we define if and only if .
proof: Write , for some integer . The rest of the proof is left as an exercise.
proof: Let and be positive integers with . Write the numbers to as an array:
If then no element in the row which has as the first element is relatively prime to . That is, all numbers which are relatively prime to must lie in a row whose first element is relatively prime to . Since there are such rows, our proof will be complete if we can show that there are elements in each such row which are relatively prime to .
Consider the row: , where . Suppose , with . Then divides . But, since , it follows from Proposition 1.2.16(2) that divides , i.e. . This, together with the above inequalities involving and show that . Therefore, no two elements in the row are congruent . By Lemma 1.6.9, every element in the row is relatively prime to . Since no two elements are congruent, their least residues are , in some order. By definition, exactly elements of are relatively prime to . It then follows that there are exactly elements in the row which are relatively prime to which completes the proof.
proof: Since for all , the result follows from Lemma 1.6.8 and Theorem 1.6.10.
Solution: We know that and if and only if is prime. In general, , where and , for . Therefore,
If is prime, then , , and , so: