[proofplan] We prove multiplicativity by expanding the convolution at $mn$ when $\gcd(m,n)=1$. The key arithmetic fact is that every divisor of $mn$ has a unique factorization as a product $ab$ with $a \mid m$ and $b \mid n$. This turns the single divisor sum over $mn$ into a double sum over divisors of $m$ and $n$, and multiplicativity of $f$ and $g$ separates the summand. The prime-power formula then follows by listing the divisors of $p^a$. [/proofplan] [step:Define the convolution and verify its value at $1$] Let $h: \mathbb{N} \to \mathbb{C}$ denote the Dirichlet convolution $h=f*g$, so \begin{align*} h(n)=\sum_{d \mid n} f(d)g\left(\frac{n}{d}\right) \end{align*} for every $n \in \mathbb{N}$. The only positive divisor of $1$ is $1$, hence \begin{align*} h(1)=f(1)g(1)=1 \cdot 1 = 1. \end{align*} [/step] [step:Factor every divisor of $mn$ into a divisor of $m$ and a divisor of $n$] Let $m,n \in \mathbb{N}$ satisfy $\gcd(m,n)=1$. [claim:Divisor factorization for coprime products] The map \begin{align*} \Phi: \{(a,b) \in \mathbb{N}^2 : a \mid m,\ b \mid n\} &\to \{d \in \mathbb{N} : d \mid mn\} \\ (a,b) &\mapsto ab \end{align*} is a bijection. Its inverse sends a divisor $d \mid mn$ to \begin{align*} \left(\gcd(d,m), \gcd(d,n)\right). \end{align*} [/claim] [proof] First let $a \mid m$ and $b \mid n$. Since $ab$ divides $mn$, the map $\Phi$ is well-defined. We prove injectivity. Suppose $a_1,a_2 \mid m$ and $b_1,b_2 \mid n$ satisfy \begin{align*} a_1b_1=a_2b_2. \end{align*} Because $a_1$ and $a_2$ divide $m$, and $b_1$ and $b_2$ divide $n$, the coprimality condition $\gcd(m,n)=1$ implies \begin{align*} \gcd(a_i,b_j)=1 \end{align*} for all $i,j \in \{1,2\}$. From $a_1b_1=a_2b_2$, the integer $a_1$ divides $a_2b_2$. Since $\gcd(a_1,b_2)=1$, Euclid's lemma gives $a_1 \mid a_2$. By the same argument, $a_2 \mid a_1$. Hence $a_1=a_2$, and then $b_1=b_2$. We prove surjectivity. Let $d \in \mathbb{N}$ satisfy $d \mid mn$. Define \begin{align*} a := \gcd(d,m), \qquad b := \gcd(d,n). \end{align*} Then $a \mid m$ and $b \mid n$. We show that $d=ab$. Let $q$ be any prime number, and let $\nu_q(k)$ denote the exponent of $q$ in the prime factorization of a positive integer $k$. Since $\gcd(m,n)=1$, at most one of $\nu_q(m)$ and $\nu_q(n)$ is positive. Also $d \mid mn$, so \begin{align*} \nu_q(d) \le \nu_q(mn)=\nu_q(m)+\nu_q(n). \end{align*} Using the definition of greatest common divisor in terms of prime exponents, \begin{align*} \nu_q(a)+\nu_q(b) &= \min\{\nu_q(d),\nu_q(m)\}+\min\{\nu_q(d),\nu_q(n)\} \\ &= \nu_q(d). \end{align*} The last equality holds because the two prime exponents $\nu_q(m)$ and $\nu_q(n)$ are not both positive, while $\nu_q(d)$ is bounded by their sum. Therefore $ab$ and $d$ have the same exponent at every prime $q$, so $d=ab$. Thus $\Phi$ is surjective. [/proof] [guided] The point of this step is to replace divisors of the product $mn$ with pairs of divisors, one from $m$ and one from $n$. This replacement is valid only because $m$ and $n$ are coprime. Define the map \begin{align*} \Phi: \{(a,b) \in \mathbb{N}^2 : a \mid m,\ b \mid n\} &\to \{d \in \mathbb{N} : d \mid mn\} \\ (a,b) &\mapsto ab. \end{align*} If $a \mid m$ and $b \mid n$, then $ab \mid mn$, so $\Phi$ is well-defined. To prove injectivity, suppose \begin{align*} a_1b_1=a_2b_2, \end{align*} where $a_1,a_2 \mid m$ and $b_1,b_2 \mid n$. Since $\gcd(m,n)=1$, every divisor of $m$ is coprime to every divisor of $n$, so $\gcd(a_i,b_j)=1$ for all $i,j \in \{1,2\}$. The equality gives $a_1 \mid a_2b_2$. Since $\gcd(a_1,b_2)=1$, Euclid's lemma gives $a_1 \mid a_2$. Reversing the roles of $a_1$ and $a_2$ gives $a_2 \mid a_1$, hence $a_1=a_2$. Substituting back gives $b_1=b_2$. To prove surjectivity, let $d \mid mn$. We define \begin{align*} a := \gcd(d,m), \qquad b := \gcd(d,n). \end{align*} Then $a \mid m$ and $b \mid n$. We must prove that $d=ab$. For a prime number $q$, let $\nu_q(k)$ be the exponent of $q$ in the prime factorization of $k \in \mathbb{N}$. Since $\gcd(m,n)=1$, at most one of $\nu_q(m)$ and $\nu_q(n)$ is nonzero. Also $d \mid mn$, hence \begin{align*} \nu_q(d) \le \nu_q(mn)=\nu_q(m)+\nu_q(n). \end{align*} Therefore \begin{align*} \nu_q(a)+\nu_q(b) &= \min\{\nu_q(d),\nu_q(m)\}+\min\{\nu_q(d),\nu_q(n)\} \\ &= \nu_q(d). \end{align*} Thus $ab$ and $d$ have the same prime exponent for every prime $q$, so $d=ab$. This proves that $\Phi$ is bijective. [/guided] [/step] [step:Separate the divisor sum using multiplicativity of $f$ and $g$] Using the bijection from the previous step, every divisor $d$ of $mn$ can be written uniquely as $d=ab$ with $a \mid m$ and $b \mid n$. For such $a$ and $b$, \begin{align*} \frac{mn}{ab}=\frac{m}{a}\frac{n}{b}. \end{align*} Since $a \mid m$ and $b \mid n$, and since $\gcd(m,n)=1$, we have $\gcd(a,b)=1$ and \begin{align*} \gcd\left(\frac{m}{a},\frac{n}{b}\right)=1. \end{align*} Therefore multiplicativity of $f$ and $g$ gives \begin{align*} f(ab)=f(a)f(b), \qquad g\left(\frac{mn}{ab}\right) = g\left(\frac{m}{a}\frac{n}{b}\right) = g\left(\frac{m}{a}\right)g\left(\frac{n}{b}\right). \end{align*} Hence \begin{align*} h(mn) &= \sum_{d \mid mn} f(d)g\left(\frac{mn}{d}\right) \\ &= \sum_{a \mid m}\sum_{b \mid n} f(ab)g\left(\frac{mn}{ab}\right) \\ &= \sum_{a \mid m}\sum_{b \mid n} f(a)f(b)g\left(\frac{m}{a}\right)g\left(\frac{n}{b}\right) \\ &= \left(\sum_{a \mid m} f(a)g\left(\frac{m}{a}\right)\right) \left(\sum_{b \mid n} f(b)g\left(\frac{n}{b}\right)\right) \\ &= h(m)h(n). \end{align*} Thus $h=f*g$ is multiplicative. [guided] We now use the divisor factorization to turn the convolution sum over $mn$ into a product of two convolution sums. By the previous step, each divisor $d \mid mn$ has a unique expression $d=ab$, where $a \mid m$ and $b \mid n$. Therefore the sum defining $h(mn)$ may be rewritten as a double sum: \begin{align*} h(mn) &= \sum_{d \mid mn} f(d)g\left(\frac{mn}{d}\right) \\ &= \sum_{a \mid m}\sum_{b \mid n} f(ab)g\left(\frac{mn}{ab}\right). \end{align*} For each pair $a \mid m$ and $b \mid n$, the quotient satisfies \begin{align*} \frac{mn}{ab}=\frac{m}{a}\frac{n}{b}. \end{align*} Because every divisor of $m$ is coprime to every divisor of $n$, we have $\gcd(a,b)=1$. Also $\frac{m}{a}$ divides $m$ and $\frac{n}{b}$ divides $n$, so \begin{align*} \gcd\left(\frac{m}{a},\frac{n}{b}\right)=1. \end{align*} These are exactly the hypotheses needed to use multiplicativity of $f$ and $g$. Hence \begin{align*} f(ab)=f(a)f(b) \end{align*} and \begin{align*} g\left(\frac{mn}{ab}\right) = g\left(\frac{m}{a}\frac{n}{b}\right) = g\left(\frac{m}{a}\right)g\left(\frac{n}{b}\right). \end{align*} Substituting these identities into the double sum gives \begin{align*} h(mn) &= \sum_{a \mid m}\sum_{b \mid n} f(a)f(b)g\left(\frac{m}{a}\right)g\left(\frac{n}{b}\right). \end{align*} The variables $a$ and $b$ range independently, so this finite double sum factors as a product: \begin{align*} h(mn) &= \left(\sum_{a \mid m} f(a)g\left(\frac{m}{a}\right)\right) \left(\sum_{b \mid n} f(b)g\left(\frac{n}{b}\right)\right) \\ &= h(m)h(n). \end{align*} Together with $h(1)=1$, this proves that $h=f*g$ is multiplicative. [/guided] [/step] [step:List the divisors of a prime power to obtain the formula] Let $p$ be a prime number and let $a \ge 0$ be an integer. The positive divisors of $p^a$ are precisely \begin{align*} 1,p,p^2,\dots,p^a. \end{align*} Equivalently, they are the integers $p^j$ with $0 \le j \le a$. Therefore the definition of $h=f*g$ gives \begin{align*} (f*g)(p^a) &= h(p^a) \\ &= \sum_{j=0}^{a} f(p^j)g\left(\frac{p^a}{p^j}\right) \\ &= \sum_{j=0}^{a} f(p^j)g(p^{a-j}). \end{align*} This proves the prime-power formula and completes the proof. [/step]