Skip to main content
Mathematics LibreTexts

4.1: Multiplicative Functions

  • Page ID
    60314
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Definition 4.1

    Number theoretic functions or arithmetic functions or sequences are functions defined on the positive integers (i.e. \(\mathbb{N}\)) with values in \(\mathbb{C}\).

    Note that in other areas of mathematics, the word sequence is the only term commonly used. We will use these terms interchangeably.

    Definition 4.2

    A multiplicative function is a sequence such that \(\gcd (a, b) = 1\) implies \(f(ab) = f(a)f(b)\). A completely multiplicative function is one where the condition that \(\gcd(a, b) = 1\) is not needed.

    Note that completely multiplicative implies multiplicative (but not vice versa). The reason this definition is interesting, is that it allows us to evaluate the value of a multiplicative function \(f\) on any integer as long as we can compute \(f(p^k)\) for any prime \(p\). Indeed, using the fundamental theorem of arithmetic,

    \[\begin{array} {cccc} {\mbox{if}}&{n = \prod_{i=1}^{r} p_{i}^{l_{i}}}&{\mbox{then}}&{f(n) = \prod_{i=1}^{r} f(p_{i}^{l_{i}})} \end{array} \nonumber\]

    as follows immediately from Definition 4.2.

    Proposition 4.3

    Let \(f\) be a multiplicative function on the integers. Then

    \[F(n) = \sum_{d | n} f(d) \nonumber\]

    is also multiplicative.

    Proof

    Let \(n = \prod^{r}_{i=1} p_{i}^{l_{i}}\). The summation \(\sum_{d | n} f(d)\) can be written out using the previous lemma and the fact that \(f\) is multiplicative:

    \[F(n) = \sum_{a_{1} = 0}^{l_{1}} \cdots \sum_{a_{r} = 0}^{l_{r}} f(p_{1}^{a_{1}}) \cdots f(p_{r}^{a_{r}}) \nonumber\]

    \[= \prod_{i=1}^{r} (\sum_{a_{i} = 0}^{l_{i}} f(p_{i}^{a_{i}})) \nonumber\]

    Now let \(a\) and \(b\) two integers greater than \(1\) and such that \(\gcd (a, b) = 1\) and \(ab = n\). Then by the Unique Factorization Theorem \(a\) and \(b\) can be written as:

    \[\begin{array}{ccc} {a = \prod_{i=1}^{r} p_{i}^{l_{i}}}&{\mbox{and}}&{b = \prod_{i=r+1}^{s} p_{i}^{l_{i}}} \nonumber \end{array}\]

    Applying the previous computation to \(a\) and \(b\) yields that \(f(a) f(b) = f(n)\).

    Perhaps the simplest multiplicative functions are the ones where \(f(n) = n^k\) for some fixed \(k\). Indeed, \(f(n)f(m) = n^{k}m^{k} = f(nm)\). In fact, this is a completely multiplicative function.

    Definition 4.4

    Let \(k \in \mathbb{R}\). The multiplicative function \(\sigma_{k} : \mathbb{N} \rightarrow \mathbb{R}\) gives the sum of the k-th power of the positive divisors of \(n\). Equivalently:

    \[\sigma_{k}(n) = \sum_{d |n} d^{k} \nonumber\]

    Note that the multiplicativity of \(\sigma_k\) follows directly from Proposition 4.3. Special cases are when \(k=1\) and \(k=0\). In the first case, the function is simply the sum of the positive divisors and the subscript '1' is usually dropped. When \(k = 0\), the function is usually called \(\tau\), and the function's value is the number of positive divisors of its argument.

    Theorem 4.5

    Let \(n = \prod^{r}_{i=1} p_{i}^{l_{i}}\) where \(p_{i}\) are primes. Then for \(k \ne 0\)

    \[\sigma_{k} (n) = \prod^{r}_{i=1} (\frac{p_{i}^{k(l_{i}+1)}-1}{p_{i}^{k}-1}) \nonumber\]

    while for \(k = 0\)

    \[\sigma_{0} (n) = \tau (n) = \prod^{r}_{i=1} (l_{i}+1) \nonumber\]

    Proof

    By Proposition 4.3, \(\sigma_{k} (n)\) is multiplicative, so it is sufficient to compute for some prime \(p\)

    \[\sigma_{k} (p^l) = \sum_{i=0}^{l} p_{i}^{ik} = \frac{p^{k(l+1)}-1}{p^{k}-1}) \nonumber\]

    Thus, \(\sigma_{k} (n)\) is indeed a product of these terms.

    However, there are other interesting multiplicative functions beside the powers of the divisors. The Mobius function defined below is one of these, as we will see.

    Definition 4.6

    The Mobius function \(\mu: \mathbb{N} \rightarrow \mathbb{Z}\) is given by:

    \[\mu (n) = \left \{ \begin{array} {ccc} {1}&{\mbox{if}}&{n=1}\\ {0}&{\mbox{if}}&{\exists p > 1 \mbox{ prime with } p^2 | n}\\ {(-1)^r}&{\mbox{if}}&{n = p_{1} \cdots p_{r} \mbox{ and } p_{i} \mbox{ are distinct primes }} \end{array} \right . \nonumber\]

    Definition 4.7

    We say that n is square free if there is no prime \(p\) such that \(p^2 | n\).

    Lemma 4.8

    The Mobius function \(\mu\) is multiplicative.

    Proof

    By unique factorization, we are allowed to assume that

    \[\begin{array} {ccccc} {n=ab}&{\mbox{where}}&{a = \prod_{i=1}^{r} p_{i}^{l_{i}}}&{and}&{b = \prod_{i=r+1}^{s} p_{i}^{l_{i}}} \end{array} \nonumber\]

    If \(a\) equals \(1\), then \(\mu (ab) = \mu (a) \mu (b) = 1 \mu (b)\), and similar if \(b = 1\). If either \(a\) or \(b\) is not square free, then neither is \(n = ab\), and so in that case, we again have \(\mu (ab) = \mu (a) \mu (b) = 0\). If both \(a\) and \(b\) are square free, then \(r\) (in the definition of \(\mu\)) is strictly additive and so \((-1)^r\) is strictly multiplicative, hence multiplicative.

    Definition 4.9

    Euler’s phi function, also called Euler’s totient function is defined as follows: \(\phi (n)\) equals the number of integers in \(\{1, \cdots n\}\) that are relative prime to \(n\).


    This page titled 4.1: Multiplicative Functions is shared under a CC BY-NC license and was authored, remixed, and/or curated by J. J. P. Veerman (PDXOpen: Open Educational Resources) .

    • Was this article helpful?