Multiplicative Functions

Recall integers and are relatively prime if .

Definition 1.6.1   Let be a function. The function is called multiplicative if , whenever and are relatively prime. If , for all then we call completely multilpicative.

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 .

Definition 1.6.2   Let be a positive integer. The number of positive divisors of is denoted and is called the number of divisors function. The sum of the positve divisors of is denoted and is called the sum of divisors function. In other words,

and

Example 1.6.3 (a)   and , where is any prime number.

(b) ,

(c)

Example 1.6.4   We have , since the positive divisors of are . We have

Theorem 1.6.5   Let be any positive integer with prime factorization: . Then

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.

Corollary 1.6.6   The number of divisors function is multiplicative.

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: .

Theorem 1.6.7   The function is multiplicative.

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 .

Lemma 1.6.8   for all positive integers .

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 .

Lemma 1.6.9   If and then

proof: Write , for some integer . The rest of the proof is left as an exercise.

Theorem 1.6.10   is multiplicative.

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.

Theorem 1.6.11   Let be a positive integer with prime factorization: . Then .

proof: Since for all , the result follows from Lemma 1.6.8 and Theorem 1.6.10.

Example 1.6.12   Show that: if and only if is prime.

Solution: We know that and if and only if is prime. In general, , where and , for . Therefore,

If is prime, then , , and , so:

Subsections

david joyner 2008-04-20