What Are Arithmetic and Multiplicative Functions?

Mutiplicative Function Theorem (MFT)

The theorem discussed here is a nice and powerful one involving multiplicative functions.

We define $f:\mathbb{N}\to\mathbb{N}$ to be a multiplicative function if $f(mn)=f(m)f(n)$ for any $m\perp n$. In fact, we call this weakly multiplicative in this case and strongly multiplicative if $f(mn)=f(m)f(n)$ for every $m,n\in\mathbb{N}$. Let $f$ be a multiplicative function and the unique prime factorization of $n$ be, $$n=p_1^{e_1}\cdots p_k^{e_k}$$ Let's call this the Multiplicative Function Theorem or MFT in short.

We asssume that $m\perp n$ denotes the greatest common divisor of $m$ and $n$ is $1$ i.e. $\gcd(m,n)=1$, $\tau(n)$ is the number of divisors of $n$. It is well known that the functions number of divisors, sum of divisors, Mobius function and totient function are multiplicative. So we don't prove them here again

For a multiplicative function $f$, the summatory function of $f$ is $F(n)=\sum\limits_{d|n}f(d)$. If $p$ is a prime, then we have, $$F(p^a)=\sum_{d|p^a}f(d)=\sum_{i=0}^af\left(p^i\right)$$

Theorem

Let $f$ be a multiplicative function. Then the following theorem holds true:

We have $F(n)=\sum_{d|n}f(d)$. Then,

\begin{eqnarray*} F(n) & = & \left(1+f(p_1)+\ldots+f\left(p_1^{e_1}\right)\right)\cdots\left(1+f(p_k)+\ldots+f\left(p_k^{e_k}\right)\right)\newline & = & \prod_{i=1}^k\sum_{j=0}^{e_i}f\left(p_i^j\right)\newline & = & \prod_{i=1}^kF\left(p_i^{e_i}\right) \end{eqnarray*}

In fact, there is not much to prove, since the theorem follows from unique prime factorization(though not straightly) of positive integers. But we can outline one like this:

Let's assume $T$ is the expansion of the right side of equation $(1.1)$, and $$S=\sum\limits_{d|n}f(d)$$

If $d|n,$ is a divisor of $n$, then $d=p_1^{w_i}\cdots p_k^{w_k}$ where $0\leq w_i\leq e_i$ for $1\leq i\leq k$. Then we have, \begin{eqnarray*} f(d) & = & f\left(p_1^{w_1}\right)\cdots f\left(p_k^{w_k}\right)\newline & = & f\left(p_1^{w_1}\right)\cdots f\left(p_k^{w_k}\right) \end{eqnarray*} which is a term that is present in $T$. Thus, we conclude that each term of $S$ is a member of $T$. Now we easily find that the converse is also true. Because, after multiplying, we see that every term in $T$ is of the form $$f\left(p_1^{w_1}\right)\cdots f\left(p_k^{w_k}\right)$$ which can be written as $$f\left(p_1^{w_1}\right)\cdots f\left(p_k^{w_k}\right)$$ or $f(d)$. Therefore, every term in $T$ is also in $S$ as well. Combining these two, $S=T$.

Since $m\perp1$ for all $m\in\mathbb{N}$, setting $m=1$, $f(m\cdot1)=f(m)f(1)$ implies $f(1)=1$. Therefore, each term starts with $1$, instead of $f(1)$ or $f(p_i^0)$.

From this, we can infer: If $f$ multiplicative, then so is $F$.

We see some applications of this theorem by solving some problems. The crucial fact deduced from this theorem is: if we can find the value of $F(p^a)$ for a positive integer $a$, we are done. And more satisfying, to do that we need to find the value of $f(p^a)$ only. Here are some examples. First we see another proof of number of divisors formula.

$1$. Find the number of divisors of $n$.

Solution Note that, if we set $f(n)=1$ for all $n\in\mathbb N$ then $f$ is multiplicative. Then it is obvious that, $$\sum_{d|n}1=\tau(n)$$

Also, since $f$ is multiplicative, we can invoke MFT. Using this,

\begin{eqnarray*} F(p_i^{e_i}) & = & \sum_{d|p_i^{e_i}}f(d)\newline & = & f(1)+f(p_i)+\ldots+f\left(p_i^{e_i}\right)\newline & = & 1+\ldots+1\newline & = & e_i+1 \end{eqnarray*} Therefore, $\tau(n)=(e_1+1)\cdots(e_k+1)$.

You can find the formula of $\varphi(n)$ in a similar manner, to see that $$\varphi(n)=\prod_{p^e||n}p^{e-1}(p-1).$$

$2$. Let $\sigma(n)$ is the sum of divisors of $n$. And let's say $\sigma_r(n)$ is the sum of $r^{th}$ power of the divisors of $n$, that is, if $d_1,d_2,\ldots,d_{\tau(n)}$ are divisors of $n$, $$\sigma_r(n)=d_1^r+\ldots+d_{\tau(n)}^r$$ Then $\sigma(n)=\sigma_1(n)$, the usual sum of divisors of $n$.

$$\sigma_r(n)=\dfrac{p_1^{(e_1+1)r}-1}{p_1-1}\cdots\dfrac{p_k^{(e_k+1)r}-1}{p_k-1}$$

Solution Set $f(n)=n^r$. This is multiplicative(in fact a strong one) since $f(mn)=(mn)^r=m^rn^r=f(m)f(n)$. Then, $$\sigma_r(n)=\sum_{d|n}d^r=f(d)$$ \begin{eqnarray*} F(p_i) & = & 1+f(p_i)+\ldots+f(p_i^{e_i}) \newline & = & 1+p_i^r+\ldots+p_i^{e_ir}\newline & = & \dfrac{p_i^{(e_i+1)r}-1}{p_i-1} \end{eqnarray*} Therefore, $$\sigma_r(n)=\dfrac{p_1^{(e_1+1)r}-1}{p_1-1}\cdots\dfrac{p_k^{(e_k+1)r}-1}{p_k-1}$$ The formula of usual sum of divisor follows if we set $r=1$.

$3$. Prove that, $$\sum_{d|n}\varphi(d)=n$$ where $\varphi(n)$ is the Euler function.

Solution Using MFT, we get, \begin{eqnarray*} F(p) & = & \sum_{i=0}^e\varphi(p^i)\newline & = & 1+(p-1)+p(p-1)+\ldots+p^{e-1}(p-1)\newline & = & 1+(p-1)\left(1+p+\ldots+p^{e-1}\right)\newline & = & 1+(p-1)\left(\dfrac{p^e-1}{p-1}\right)\newline & = & p^e \end{eqnarray*} Hence, $\sum\limits_{d|n}\varphi(d)=\prod\limits_{p|n} p^e=n$.

$4$. Mobius Function $\mu(n)$ is defined by

Prove that, $\sum\limits_{d|n}\mu(d)=0$ for $n>1$.

Solution First, note that, for a prime $p$, $\mu(p^a)=0$ for $a>1$ since it isn't square-free. Therefore,

\begin{eqnarray*} F(p^e) & = & \mu(1)+\mu(p)+0+\ldots+0\ & = & 1-1\ & = & 0 \end{eqnarray*} since $\mu(p)=(-1)^1=-1$. Therefore, $$\sum\limits_{d|n}\mu(d)=\prod\limits_{p|n}\sum\limits_{i=0}^{e_i}\mu(p^i)=0.$$

An arithmetic function is a function $f$ from the positive integers to the complex numbers.

A multiplicative arithmetic function is one which also satisfies $f(ab)=f(a)f(b)$ whenever $a$ and $b$ are coprime. (Also, it is required for it to attain a nonzero value.)

Or course, we may choose $b=1$ and $a$ any positive integer, to find $f(a)=f(a)f(1)$. We know there is an $a$ with $f(a)\neq 0$, choose that and divide by $f(a)$ to obtain $f(1)=1$.

If the last condition for multiplicativity, i.e. that $a$ and $b$ are to be relatively prime isn't needed, $f$ is called totally multiplicative. But why do we need this condition? Give this a bit of thought before continuing.

We know that every integer $n>1$ can be prime factorized as

$$n=p_1^{k_1}p_2^{k_2}...p_r^{k_r}.$$

Every multiplicative function $f$ will then satisfy $f(1)=1$ and for $n>1$,

$$f(n)=f(p_1^{k_1})f(p_2^{k_2})...f(p_r^{k_r}).$$

This is intuitively obvious (just keep splitting the prime factors of $n$ into two groups and using the condition), and can be proven by induction on $r$. It is a fundamental theorem, however, in the theory of multiplicative functions.

Also, when studying these functions, it is quite handy to use product notation:

$$f(n)=\prod_{i=1}^r f(p_i^{k_i}).$$

Now with multiplicative functions, the values of $f$ at prime powers determine $f$, but we cannot say anything else about $f$ for sure. (Actually, we may choose arbitrary values at the prime powers and thereby generate a multiplicative function.)

If we additionally assume total multiplicativity, it is the value of $f$ at the primes which determines $f$, turning out to be too strict a condition to impose.

Multiplicative arithmetic functions include the totient function, the number of factors function and the sum of divisors function.