---
tag: 14FW2X35FP
kind: proof
name: Proof of the multiplicativity of the divisor function
msc: [11A25]
proves: 04WC36XKV6
uses: [0YEW47VJ0J, 0AP80TT660, 0FCWA16FZE, 0GFKP8F8AG, 02WF878BH1, 0DQVHMYAGA]
sources:
  - url: https://proofwiki.org/wiki/Divisor_Sum_Function_is_Multiplicative
---

## Proof

1. Let $k$ be a natural number. For a positive integer $x$, let $D(x)$ be the set of [[positive divisors|0FCWA16FZE]] of $x$. By the definition of the [[divisor function|0YEW47VJ0J]], $\sigma_k(x) = \sum_{d \in D(x)} d^k$.
2. Since $D(1) = \set{1}$, we have $\sigma_k(1) = 1$.
3. Claim: if $a \mid bc$ and $\gcd(a, b) = 1$, then $a \mid c$. By [[Bézout's identity|0DQVHMYAGA]], $1 = ua + vb$ for integers $u, v$. Then $c = uac + vbc$, and $a$ divides both terms.
4. Let $m$ and $n$ be [[coprime|0GFKP8F8AG]] positive integers. Define $\Phi : D(m) \times D(n) \to D(mn)$ by $\Phi(d, e) = de$. This is well defined, since $d \mid m$ and $e \mid n$ give $de \mid mn$.
5. If $d \mid m$ and $e \mid n$, then $\gcd(d, e) = 1$. Indeed, a common divisor of $d$ and $e$ divides both $m$ and $n$, whose [[greatest common divisor|02WF878BH1]] is $1$.
6. $\Phi$ is injective. Suppose $de = d'e'$ with $d, d' \in D(m)$ and $e, e' \in D(n)$. Then $d \mid d'e'$ and $\gcd(d, e') = 1$, so $d \mid d'$ by step 3.
7. In the same way $d' \mid d$. Both are positive, so $d = d'$, and then $e = e'$.
8. $\Phi$ is surjective. Let $c \in D(mn)$, let $d = \gcd(c, m)$, and write $c = d c'$ and $m = d m'$. Then $\gcd(c', m') = 1$, since a common divisor $g \ge 1$ makes $gd$ a common divisor of $c$ and $m$. Then $gd \le d$, so $g = 1$.
9. From $c \mid mn$ we get $d c' \mid d m' n$, so $c' \mid m' n$. By step 3, $c' \mid n$. So $c = \Phi(d, c')$ with $d \in D(m)$ and $c' \in D(n)$.
10. So $\Phi$ is a bijection. Hence $\sigma_k(mn) = \sum_{d \in D(m)} \sum_{e \in D(n)} (de)^k = \left(\sum_{d \in D(m)} d^k\right) \left(\sum_{e \in D(n)} e^k\right)$.
11. This is $\sigma_k(m) \sigma_k(n)$. With step 2, $\sigma_k$ is a [[multiplicative function|0AP80TT660]].

## Idea

When $m$ and $n$ share no factor, each divisor of $mn$ splits in exactly one way as a divisor of $m$ times a divisor of $n$. So the sum of $k$-th powers over the divisors of $mn$ factors as a product of two sums.