[proofplan] The proof has two ingredients. First, distinct prime-power factors in the prime factorization of $n$ are pairwise coprime. Second, multiplicativity over two coprime factors extends by induction to any finite product of pairwise coprime factors. Applying this finite-product form to the prime-power decomposition gives the displayed formula, and the uniqueness of prime factorization then shows that the prime-power values determine the whole function. [/proofplan] [step:Show that distinct prime-power factors are pairwise coprime] For each index $i \in \{1,\dots,r\}$, define \begin{align*} q_i := p_i^{a_i}. \end{align*} We claim that $q_i$ and $q_j$ are coprime whenever $i \neq j$. Indeed, if an integer $d \geq 2$ divided both $q_i$ and $q_j$, then some prime divisor $\ell$ of $d$ would divide both $p_i^{a_i}$ and $p_j^{a_j}$. Since $p_i$ and $p_j$ are prime, this forces $\ell=p_i$ and $\ell=p_j$, hence $p_i=p_j$, contradicting the distinctness of the primes in the factorization. Therefore \begin{align*} \gcd(q_i,q_j)=1 \end{align*} for all $i \neq j$. [/step] [step:Extend multiplicativity from two factors to finitely many pairwise coprime factors] We prove the following finite-product form of multiplicativity: if $q_1,\dots,q_r \in \mathbb{N}$ are pairwise coprime, then \begin{align*} f(q_1\cdots q_r)=\prod_{i=1}^{r} f(q_i). \end{align*} For $r=1$, the assertion is the identity $f(q_1)=f(q_1)$. Suppose the assertion holds for some $r-1 \geq 1$. Define \begin{align*} Q_{r-1}:=\prod_{i=1}^{r-1}q_i. \end{align*} Because $q_r$ is coprime to each $q_i$ for $1 \leq i \leq r-1$, it is coprime to their product: \begin{align*} \gcd(Q_{r-1},q_r)=1. \end{align*} By multiplicativity of $f$ applied to the coprime integers $Q_{r-1}$ and $q_r$, \begin{align*} f(q_1\cdots q_r) &= f(Q_{r-1}q_r) \\ &= f(Q_{r-1})f(q_r). \end{align*} Using the induction hypothesis on $q_1,\dots,q_{r-1}$ gives \begin{align*} f(Q_{r-1})f(q_r) &= \left(\prod_{i=1}^{r-1} f(q_i)\right)f(q_r) \\ &= \prod_{i=1}^{r} f(q_i). \end{align*} This proves the finite-product formula by induction. [guided] We want to use multiplicativity more than once. The definition only gives a rule for two coprime inputs at a time, so we first prove that this two-factor rule can be iterated. Let $q_1,\dots,q_r \in \mathbb{N}$ be pairwise coprime. We prove by induction on $r$ that \begin{align*} f(q_1\cdots q_r)=\prod_{i=1}^{r} f(q_i). \end{align*} For $r=1$, the statement says $f(q_1)=f(q_1)$, so the base case holds. Assume now that the formula has been proved for $r-1$ pairwise coprime integers, where $r \geq 2$. Define \begin{align*} Q_{r-1}:=\prod_{i=1}^{r-1}q_i. \end{align*} The reason for introducing $Q_{r-1}$ is that the full product can be viewed as a product of two factors: \begin{align*} q_1\cdots q_r = Q_{r-1}q_r. \end{align*} To apply multiplicativity, we must verify that these two factors are coprime. Since $q_r$ is coprime to each of $q_1,\dots,q_{r-1}$, no prime divides both $q_r$ and any $q_i$ with $i<r$. Hence no prime divides both $q_r$ and the product $Q_{r-1}$, and therefore \begin{align*} \gcd(Q_{r-1},q_r)=1. \end{align*} Multiplicativity of $f$ now applies to $Q_{r-1}$ and $q_r$, giving \begin{align*} f(q_1\cdots q_r) &= f(Q_{r-1}q_r) \\ &= f(Q_{r-1})f(q_r). \end{align*} The induction hypothesis applies to $q_1,\dots,q_{r-1}$, so \begin{align*} f(Q_{r-1}) = \prod_{i=1}^{r-1} f(q_i). \end{align*} Substituting this into the previous identity yields \begin{align*} f(q_1\cdots q_r) &= \left(\prod_{i=1}^{r-1} f(q_i)\right)f(q_r) \\ &= \prod_{i=1}^{r} f(q_i). \end{align*} Thus multiplicativity over two coprime factors extends to any finite product of pairwise coprime factors. [/guided] [/step] [step:Apply the finite-product formula to the prime-power decomposition] Using the notation $q_i=p_i^{a_i}$, the prime factorization of $n$ is \begin{align*} n=\prod_{i=1}^{r}q_i. \end{align*} The first step showed that $q_1,\dots,q_r$ are pairwise coprime, and the second step showed that multiplicativity applies to finite products of pairwise coprime integers. Therefore \begin{align*} f(n) &= f\left(\prod_{i=1}^{r}q_i\right) \\ &= \prod_{i=1}^{r} f(q_i) \\ &= \prod_{i=1}^{r} f(p_i^{a_i}). \end{align*} This proves the displayed formula. [/step] [step:Conclude that the prime-power values determine the function] The value at $1$ is fixed by the definition of multiplicativity: \begin{align*} f(1)=1. \end{align*} For every integer $n \geq 2$, the [Fundamental Theorem of Arithmetic](/theorems/730) gives a unique expression \begin{align*} n=p_1^{a_1}\cdots p_r^{a_r} \end{align*} with $p_1,\dots,p_r$ distinct primes and $a_1,\dots,a_r \in \mathbb{N}$ (citing a result not yet in the wiki: Fundamental Theorem of Arithmetic). The formula proved above then expresses $f(n)$ entirely in terms of the values $f(p_i^{a_i})$. Hence the collection of values $f(p^a)$ for primes $p$ and integers $a \geq 1$, together with $f(1)=1$, determines $f(n)$ for every $n \in \mathbb{N}$. [/step]