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 |