Multiplicative Functions

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:

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:

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:

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,*

David Joyner 2007-09-03