TAOCP 1.2.4 Exercise 29

Section 1.2.4: Integer Functions and Elementary Number Theory

Exercise 29. [M22] A function $f(n)$ of positive integers $n$ is called multiplicative if $f(rs)=f(r)f(s)$ whenever $r \perp s$. Show that each of the following functions is multiplicative:

(a) $f(n)=n^c$, where $c$ is any constant;

(b) $f(n)=[n \text{ is not divisible by } k^2 \text{ for any integer } k>1]$;

(c) $f(n)=c^k$, where $k$ is the number of distinct primes that divide $n$;

(d) the product of any two multiplicative functions.

Verified: yes
Solve time: 48s

---

Solution

Let $f(n)$ be a function of positive integers. Recall that $f$ is multiplicative if

$f(rs) = f(r) f(s) \quad \text{whenever } r \perp s.$

We prove each part separately.

(a) $f(n) = n^c$ for constant $c$.

Let $r \perp s$. Then by the usual laws of exponents,

$f(rs) = (rs)^c = r^c s^c = f(r) f(s).$

Hence $f$ is multiplicative.

(b) $f(n) = [n \text{ is not divisible by } k^2 \text{ for any integer } k>1]$.

Let $r \perp s$. Then $r$ and $s$ share no common prime factors. A square $k^2$ divides $rs$ if and only if it divides $r$ or $s$, because if $k^2$ were divisible by primes from both $r$ and $s$, then $r$ and $s$ would not be relatively prime. Therefore,

$f(rs) = [rs \text{ is squarefree}] = [r \text{ is squarefree}] [s \text{ is squarefree}] = f(r) f(s).$

Hence $f$ is multiplicative.

(c) $f(n) = c^k$, where $k$ is the number of distinct primes dividing $n$.

Let $r \perp s$, and let $k_r$ and $k_s$ be the number of distinct primes dividing $r$ and $s$, respectively. Since $r$ and $s$ have no common prime factors, the number of distinct primes dividing $rs$ is $k_r + k_s$. Therefore,

$f(rs) = c^{k_r + k_s} = c^{k_r} c^{k_s} = f(r) f(s).$

Hence $f$ is multiplicative.

(d) Product of multiplicative functions.

Let $f$ and $g$ be multiplicative functions, and let $r \perp s$. Then

$(fg)(rs) = f(rs) g(rs) = f(r) f(s) g(r) g(s) = f(r) g(r) f(s) g(s) = (fg)(r) (fg)(s).$

Hence the product $fg$ is multiplicative.

This completes the proof. ∎