Multiplicative Functions

Recall integers $a$ and $b$ are relatively prime if $gcd(a,b)=1$ .

Definition 1.6.1   Let $f:\mathbb{N}\rightarrow \mathbb{C}$ be a function. The function $f$ is called multiplicative if $f(ab)=f(a)f(b)$ , whenever $a$ and $b$ are relatively prime. If $f(ab)=f(a)f(b)$ , for all $a,b\in \mathbb{N}$ then we call $f$ 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 $gcd(p,q)=1$ , for any prime numbers $p$ and $q$ , in order to find a formula for $f(n)$ , where $n$ is a positive integer and $f$ is a multiplicative function, we factor $n$ as a product of prime powers and our work is reduced to finding a formula for $f(p^e)$ , where $p^e$ is the highest power of the prime $p$ dividing $n$ .

Definition 1.6.2   Let $n$ be a positive integer. The number of positive divisors of $n$ is denoted $d(n)$ and is called the number of divisors function. The sum of the positve divisors of $n$ is denoted $\sigma (n)$ and is called the sum of divisors function. In other words,

$$d(n)=\sum_{d \mid n} 1,$$

and

$$\sigma (n) = \sum_{d \mid n} d.$$

Example 1.6.3 (a)   $d(p)=2$ and $\sigma (p)=1+p$ , where $p$ is any prime number.

(b) $d(24)=8$ ,

(c) $\sigma (24)=60.$

Example 1.6.4   We have $d(p^k)=k+1$ , since the positive divisors of $p^k$ are $1,p,p^2,p^3,\dots,p^k$ . We have

$$\sigma (p^k)= 1+p+p^2+p^3+\cdots +p^k=\frac{1-p^{k+1}}{1-p}.$$

Theorem 1.6.5   Let $n$ be any positive integer with prime factorization: $n=p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ . Then

$$d(n)=d(p_1^{e_1}) d(p_2^{e_2}) \cdots d(p_k^{e_k}) =(e_1+1)(e_2+1) \cdots (e_k+1).$$

proof: By Theorem 1.5.11 (1) all divisors of $n$ are of the form: $a=p_1^{f_1} p_2^{f_2} \cdots p_k^{f_k}$ , where $0 \leq f_i \leq e_i$ . Therefore, there are $e_1+1$ choices for $f_1$ , $e_2+1$ choices for $f_2$ , etc, which gives us the above formula. $\Box$

Corollary 1.6.6   The number of divisors function $d$ is multiplicative.

proof: Let $m$ and $n$ be relatively prime positive integers. We write the prime factorizations as follows:

$$m=p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} \quad {\rm and} \quad n=q_1^{f_1} q_2^{f_2} \cdots q_l^{f_l},$$

where all the $p_i$ and $q_j$ are distinct primes.

We have $d(mn)=d(p_1^{e_1} \cdots p_k^{e_k} q_1^{f_1} \cdots q_l^{f_l})$ , which, by Theorem 1.6.5, is equal to: $(e_1+1) \cdots (e_k+1) (f_1+1) \cdots (f_l+1)=d(m) d(n)$ . $\Box$

Theorem 1.6.7   The function $\sigma (n)$ is multiplicative.

proof: Let $m$ and $n$ be relatively prime positive integers with positive divisors $a_1, a_2, \dots, a_k$ and $b_1, b_2, \dots,b_l$ , respectively. Then:

$$\sigma(m) \sigma (n)=(a_1+a_2+\cdots +a_k) (b_1+b_2+\cdots+b_l) =a_1(b_1+\cdots+b_l)+\cdots+a_k(b_1+\cdots+b_l).$$

Since $gcd(m,n)=1$ , each term is distinct, i.e. $a_i b_j \neq a_s b_t$ , if $i \neq s$ and $j \neq t$ (why?). Therefore, the numbers in the above sum represent all of the divisors of $mn$ and we have proved that $\sigma (mn)=\sigma (m) \sigma (n)$ . $\Box$

Let $n$ be a positive integer. Recall the Euler phi function, $\phi(n)$ , is the number of positive integers less than or equal to $n$ which are relatively prime to $n$ .

Lemma 1.6.8   $\phi (p^n)=p^{n-1}(p-1)$ for all positive integers $n$ .

proof: The positive integers less than or equal to $p^n$ , which are not relatively prime to $p^n$ are all multiples of $p$ : $1 \cdot p, 2 \cdot p, 3 \cdot p, \dots,p^{n-1} \cdot p$ . Thus, we can see that there are $p^{n-1}$ such integers. Since there are $p^n$ integers less than or equal to $p^n$ , it follows that:

$$\phi (p^n)=p^n-p^{n-1}=p^{n-1}(p-1).$$

$\Box$

Our next goal is to show that $\phi$ is multiplicative. This result, the Fundamental Theorem of Artithmetic, and Lemma 1.6.8 will give us a formula for $\phi(n)$ , for any positive integer $n$ .

We start with a lemma. Recall that for integers $a,b$ and a fixed integer $m>1$ , we define $a \equiv b ({\rm mod} m)$ if and only if $m \mid (a-b)$ .

Lemma 1.6.9   If $gcd(a,m)=1$ and $a \equiv b ({\rm mod} m)$ then $gcd(b,m)=1$

proof: Write $b=a+c m$ , for some integer $c$ . The rest of the proof is left as an exercise. $\Box$

Theorem 1.6.10   $\phi$ is multiplicative.

proof: Let $m$ and $n$ be positive integers with $gcd(m,n)=1$ . Write the numbers $1$ to $mn$ as an array:

$$\begin{array}{ccccc} 1 & m+1 & 2m+1 & \dots & (n-1)m+1 \\ 2... ... & & . \\ .&.& .& & . \\ m& 2m & 3m & \dots & nm \end{array}$$

If $gcd(k,m)=d >1$ then no element in the row which has $k$ as the first element is relatively prime to $mn$ . That is, all numbers which are relatively prime to $mn$ must lie in a row whose first element is relatively prime to $m$ . Since there are $\phi (m)$ such rows, our proof will be complete if we can show that there are $\phi(n)$ elements in each such row which are relatively prime to $mn$ .

Consider the $k^{th}$ row: $k \quad m+k \quad 2m+k \quad \dots \quad (n-1)m+k$ , where $gcd(k,m)=1$ . Suppose $im+k \equiv jm+k \quad ({\rm mod} n)$ , with $0 \leq i,j <n$ . Then $n$ divides $im+k-(jm+k)=(i-j)m$ . But, since $gcd(m,n)=1$ , it follows from Proposition 1.2.16(2) that $n$ divides $i-j$ , i.e. $i \equiv j ({\rm mod} n)$ . This, together with the above inequalities involving $i$ and $j$ show that $i=j$ . Therefore, no two elements in the $k^{th}$ row are congruent $({\rm mod} n)$ . By Lemma 1.6.9, every element in the $k^{th}$ row is relatively prime to $m$ . Since no two elements are congruent, their least residues are $0,1,2,\dots,n-1$ , in some order. By definition, exactly $\phi(n)$ elements of $\{0,1,...,n-1\}$ are relatively prime to $n$ . It then follows that there are exactly $\phi(n)$ elements in the $k^{th}$ row which are relatively prime to $mn$ which completes the proof. $\Box$

Theorem 1.6.11   Let $n$ be a positive integer with prime factorization: $n=p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ . Then $\phi (n) =p^{e_1-1} (p_1-1) p_2^{e_2-1} (p_2-1) \cdots p_k^{e_k-1} (p_k-1)$ .

proof: Since $gcd(p_i^{e_i},p_j^{e_j})=1$ for all $i \neq j$ , the result follows from Lemma 1.6.8 and Theorem 1.6.10. $\Box$

Example 1.6.12   Show that: $\phi (n) +\sigma (n)=n d(n)$ if and only if $n$ is prime.

Solution: We know that $\phi (n) \leq n-1$ and $\phi(n)=n-1$ if and only if $n$ is prime. In general, $\sigma (n) =1 + r_1+r_2+ \cdots +r_k$ , where $r_k=n$ and $r_i \mid n, \quad 1 < r_i < n$ , for $1 \leq i \leq k-1, k=d(n)-1$ . Therefore,

$$\sigma (n) \leq 1 + kn ,$$

$$\phi (n) + \sigma (n) \leq (n-1) +1+kn ,$$

$$\phi (n)+\sigma(n) \leq n+(d(n)-1)n=nd(n) .$$

If $n$ is prime, then $\phi(n)=n-1$ , $d(n)=2$ , and $\sigma (n)=n+1$ , so:

$$\phi (n)+\sigma (n)=(n-1) + (n+1)=2 n=d(n) n .$$