Arithmetic Functions (Additive and Multiplicative)

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
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License