Maths Olympiad Prep

Library / /51 of 71

Number theory Difficulty 5.3 AIME, harder Prove it United States

Problem:
Determine with proof, a simple closed form expression for
dnϕ(d)τ(nd) \sum_{d \mid n} \phi(d) \tau\left(\frac{n}{d}\right)

Solution

Solution:
We claim the series reduces to σ(n)\sigma(n). The series counts the ordered triples (d,x,y)(d, x, y) with dn; xd; 0<yn/d;d \mid n;\ x \mid d;\ 0 < y \leq n/d; and (y,n/d)=1(y, n/d) = 1. To see this, write
dnϕ(d)τ(nd)=dnϕ(nd)τ(d) \sum_{d \mid n} \phi(d) \tau\left(\frac{n}{d}\right) = \sum_{d' \mid n} \phi\left(\frac{n}{d'}\right) \tau\left(d'\right)
so that for a given dnd' \mid n we may choose xx and yy as described above. On the other hand, we can count these triples by groups sharing a given xx. Fixing xx as a divisor of nn fixes an integer nx\frac{n}{x}. Then dd varies such that nd\frac{n}{d} is a divisor of nx\frac{n}{x}. For each divisor nd\frac{n}{d} of nx\frac{n}{x} there are precisely ϕ(nd)\phi\left(\frac{n}{d}\right) choices yy, so that by the lemma from the previous problem, there are nx\frac{n}{x} triples (d,x,y)(d, x, y) for a given xx. It follows that there are precisely σ(n)\sigma(n) such triples (d,x,y)(d, x, y).

Again, an alternative is to use the multiplicativity of the convolution, although it is now a little more difficult. Write n=pkn = p^{k} so that
dnϕ(d)τ(nd)=m=0kϕ(pm)τ(pkm)=k+1+m=1kpm1(p1)(km+1)=k+1+(m=1kpm(km+1))(m=1kpm1(km+1))=k+1+pkk+m=1k1pm=1+p++pk=σ(pk) \begin{aligned} \sum_{d \mid n} & \phi(d) \tau\left(\frac{n}{d}\right) = \sum_{m=0}^{k} \phi\left(p^{m}\right) \tau\left(p^{k-m}\right) = k+1 + \sum_{m=1}^{k} p^{m-1}(p-1)(k-m+1) \\ & = k+1 + \left(\sum_{m=1}^{k} p^{m}(k-m+1)\right) - \left(\sum_{m=1}^{k} p^{m-1}(k-m+1)\right) = k+1 + p^{k} - k + \sum_{m'=1}^{k-1} p^{m'} \\ & = 1 + p + \cdots + p^{k} = \sigma\left(p^{k}\right) \end{aligned}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.