Arithmetic Functions (Additive and Multiplicative)

Definition: An Arithmetic Function is a function $f$ whose domain is $\mathbb{N}$ and whose codomain is $\mathbb{C}$.

Definition: An arithmetic function $f$ is said to be Completely Additive if $f(mn) = f(m) + f(n)$ for all $m, n \in \mathbb{N}$. $f$ is said to be Additive if $f(mn) = f(m) + f(n)$ whenever $(m, n) = 1$.

Below is a table of some additive and completely additive arithmetic functions.

Function	Description	Additive	Completely Additive
$\omega (n)$	The number of distinct prime divisors of $n$.	Yes	No
$\Omega (n)$	The number of prime divisors of $n$ counting multiplicity.	Yes	Yes

Definition: An arithmetic function $f$ is said to be Completely Multiplicative if $f(mn) = f(m)f(n)$ for all $m, n \in \mathbb{N}$. $f$ is said to be Multiplicative if $f(mn) = f(m)f(n)$ whenever $(m, n) = 1$.

Observe that if $f$ is multiplicative and if $n$ has prime power decomposition $n = p_1^{e_1}p_2^{e_2}…p_k^{e_k}$ then:

(1)

\begin{align} \quad f(n) &= f(p_1^{e_1}p_2^{e_2}…p_k^{e_k}) \\ &= f(p_1^{e_1})f(p_2^{e_2})…f(p_k^{e_k}) \\ &= \prod_{p^k \| n}f(p^k) \end{align}

Also observe that if $f$ is completely multiplicative then:

(2)

\begin{align} \quad f(n) &= f(p_1^{e_1}p_2^{e_2}…p_k^{e_k}) \\ &= f(p_1^{e_1})f(p_2^{e_2})…f(p_k^{e_k}) \\ &= f(p_1)^{e_1} f(p_2)^{e_2}…f(p_k)^{e_k} \\ &= \prod_{p^k \| n} (f(p))^k \end{align}

If $f$ is multiplicative then all we need to know is how to compute $f$ on prime powers $p^k$, and if $f$ is completely multiplicative then all we need to know is how to compute $f$ on primes.

Below is a table of some multiplicative and completely multiplicative arithmetic functions.

Function	Description	Multiplicative	Completely Multiplicative
$d(n)$ ($\tau(n)$)	The number of positive divisors of $n$	Yes	No
$\sigma(n)$	The sum of the positive divisors of $n$	Yes	No
$\sigma_k(n)$, $k \in \mathbb{N}$	The sum of the $k^{\mathrm{th}}$ powers of the positive divisors of $n$.	Yes	No
$\phi(n)$	The number of positive integers less than $n$ that are relatively prime to $n$.	Yes	No
$N(n)$	The number of solutions to the quadratic congruence $x^2 \equiv -1 \pmod n$.	Yes	No
$\mathrm{id}(n) = n$.	The identity function.	Yes	Yes
$1(n) = 1$	The constant function $1$.	Yes	Yes
$\iota(n)$	The function that is equal to $1$ when $n = 1$ and $0$ everywhere else.	Yes	Yes