[proofplan] We establish the three claims in sequence, each building on the previous. Part (i) is a direct count: among the $p^k$ integers in $\{1, \ldots, p^k\}$, the ones failing to be coprime to $p^k$ are exactly the multiples of $p$. Part (ii) combines part (i) with the multiplicativity of $\varphi$ from the CRT corollary, applied to the prime power factorisation of $n$. Part (iii) is proved by showing both sides are multiplicative functions of $n$ — the left via the divisor-sum lemma, the right by direct computation $mn = m \cdot n$ — and then verifying equality on prime powers. [/proofplan] [step:Count integers coprime to $p^k$ by excluding multiples of $p$] Let $p$ be prime and $k \geq 1$. By definition, \begin{align*} \varphi(p^k) &= \#\{a \in \{1, 2, \ldots, p^k\} : (a, p^k) = 1\}. \end{align*} Since $p$ is the only prime divisor of $p^k$, the condition $(a, p^k) = 1$ is equivalent to $p \nmid a$. Therefore \begin{align*} \varphi(p^k) &= p^k - \#\{a \in \{1, 2, \ldots, p^k\} : p \mid a\}. \end{align*} The multiples of $p$ in $\{1, \ldots, p^k\}$ are $p, 2p, 3p, \ldots, p^{k-1} p = p^k$, of which there are exactly $p^{k-1}$. Therefore \begin{align*} \varphi(p^k) &= p^k - p^{k-1} = p^{k-1}(p - 1) = p^k\!\left(1 - \frac{1}{p}\right), \end{align*} establishing (i). [guided] An integer $a$ with $1 \leq a \leq p^k$ satisfies $(a, p^k) = 1$ iff it shares no prime factor with $p^k$. Since $p$ is the unique prime factor of $p^k$, this reduces to: $p \nmid a$. We count multiples of $p$ in the range: $a = jp$ with $1 \leq jp \leq p^k$, i.e., $1 \leq j \leq p^{k-1}$. This gives $p^{k-1}$ multiples. Subtracting from the total $p^k$: \begin{align*} \varphi(p^k) &= p^k - p^{k-1} = p^{k-1}(p-1). \end{align*} The equivalent form $p^k(1 - 1/p) = p^k - p^{k-1}$ is algebraically identical; this form is useful for part (ii) where it assembles into a product. [/guided] [/step] [step:Apply multiplicativity of $\varphi$ to the prime factorisation] Let $n \geq 1$ with prime factorisation $n = \prod_i p_i^{k_i}$, where the primes $p_i$ are distinct. Since distinct prime powers are pairwise coprime — for $i \neq j$, any common divisor of $p_i^{k_i}$ and $p_j^{k_j}$ must divide $(p_i, p_j) = 1$ — the [Multiplicativity of $\varphi$](/theorems/1703) theorem applies: \begin{align*} \varphi(n) = \varphi\!\left(\prod_i p_i^{k_i}\right) &= \prod_i \varphi(p_i^{k_i}). \end{align*} Substituting the formula from (i): \begin{align*} \varphi(n) &= \prod_i p_i^{k_i}\!\left(1 - \frac{1}{p_i}\right) = \left(\prod_i p_i^{k_i}\right) \prod_i \left(1 - \frac{1}{p_i}\right) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right), \end{align*} establishing (ii). In the last equality we used $n = \prod_i p_i^{k_i}$ and that the product $\prod_i (1 - 1/p_i)$ ranges over exactly the distinct prime divisors of $n$. [/step] [step:Prove the divisor-sum identity is multiplicative on both sides] Define $h: \mathbb{N} \to \mathbb{N}$ by \begin{align*} h(n) &:= \sum_{d \mid n} \varphi(d), \end{align*} and note the right side of (iii) is simply $h'(n) := n$. We show that both $h$ and $h'$ are multiplicative functions of $n$, reducing (iii) to the prime-power case. **$h$ is multiplicative:** The function $\varphi$ is multiplicative by the [Multiplicativity of $\varphi$](/theorems/1703) theorem. By the [Divisor Sum Preserves Multiplicativity](/theorems/1704) theorem, applied to $f = \varphi$, the divisor sum \begin{align*} h(n) &= \sum_{d \mid n} \varphi(d) \end{align*} is also multiplicative. **$h'(n) = n$ is multiplicative:** For coprime $m, n$, we have $h'(mn) = mn = h'(m) h'(n)$. (In fact $h'$ is totally multiplicative, not merely multiplicative, but we only need the weaker property.) [guided] The strategy for part (iii) is the **local-to-global principle for multiplicative functions**: if two multiplicative functions agree on all prime powers $p^k$, they agree on all positive integers, because any positive integer $n$ factors uniquely as $n = \prod_i p_i^{k_i}$ into pairwise coprime prime powers, and multiplicativity lets both sides factor identically. We verify both sides are multiplicative. **Left side $h(n) = \sum_{d \mid n} \varphi(d)$:** Since $\varphi$ is multiplicative (by [Multiplicativity of $\varphi$](/theorems/1703), applied to the CRT pairwise-coprime factorisation), and the divisor sum $h(n) = \sum_{d \mid n} \varphi(d)$ is formed from a multiplicative function by the divisor-sum construction, the [Divisor Sum Preserves Multiplicativity](/theorems/1704) theorem gives multiplicativity of $h$. We verify the hypothesis of that theorem: we need $\varphi$ multiplicative, which we have. Therefore $h(mn) = h(m) h(n)$ for coprime $m, n$. **Right side $h'(n) = n$:** This is totally multiplicative: $h'(mn) = mn = h'(m) h'(n)$ for all $m, n \in \mathbb{N}$, with or without coprimality. Once both sides are multiplicative and known to agree on prime powers, they agree everywhere. So our remaining task is to verify (iii) for $n = p^k$. [/guided] [/step] [step:Verify the divisor-sum identity on prime powers] For $n = p^k$ with $p$ prime and $k \geq 0$, the divisors of $p^k$ are exactly $1, p, p^2, \ldots, p^k$. Using $\varphi(1) = 1$ and the formula $\varphi(p^j) = p^j - p^{j-1}$ for $j \geq 1$ from (i), \begin{align*} h(p^k) = \sum_{d \mid p^k} \varphi(d) &= \varphi(1) + \varphi(p) + \varphi(p^2) + \cdots + \varphi(p^k) \\ &= 1 + (p - 1) + (p^2 - p) + \cdots + (p^k - p^{k-1}). \end{align*} This sum telescopes: successive terms cancel except $-p^0$ (from $\varphi(1) = 1 = p^0$, canceling against the implicit $-p^0$ at the start of the next term only after regrouping). Explicitly, \begin{align*} \sum_{j=0}^k \varphi(p^j) &= 1 + \sum_{j=1}^k (p^j - p^{j-1}) = 1 + (p^k - 1) = p^k. \end{align*} Therefore $h(p^k) = p^k = h'(p^k)$ for every prime power $p^k$. [guided] The telescoping happens because the sum $\sum_{j=1}^k (p^j - p^{j-1})$ has the form $(p^1 - p^0) + (p^2 - p^1) + (p^3 - p^2) + \cdots + (p^k - p^{k-1})$. Writing out explicitly: \begin{align*} (p - 1) + (p^2 - p) + (p^3 - p^2) + \cdots + (p^k - p^{k-1}) &= -1 + p^k, \end{align*} since every intermediate $p^j$ appears once with a $+$ and once with a $-$. Adding the $\varphi(1) = 1$ at the start: \begin{align*} h(p^k) &= 1 + (-1 + p^k) = p^k. \end{align*} [/guided] [/step] [step:Combine the multiplicativity and the prime-power check to finish (iii)] Both $h$ and $h'$ are multiplicative, and $h(p^k) = h'(p^k)$ for every prime power $p^k$. For any $n \geq 1$ with prime factorisation $n = \prod_i p_i^{k_i}$ (distinct primes, pairwise coprime prime powers), \begin{align*} h(n) &= \prod_i h(p_i^{k_i}) = \prod_i p_i^{k_i} = n = h'(n), \end{align*} where the first equality uses multiplicativity of $h$ (and iterated application across pairwise coprime factors), and the second uses the prime-power check. The base case $n = 1$ is handled by $h(1) = \varphi(1) = 1 = h'(1)$. Therefore \begin{align*} \sum_{d \mid n} \varphi(d) &= n \quad \text{for all } n \geq 1, \end{align*} completing part (iii). Combined with (i) and (ii), all three claims are proved. [/step]