(Updated below)
I'm working through John Stillwell's Elements of Algebra, and while his exercises are generally crafted to be not too difficult, there's one that I don't even understand what it's saying, let alone how to actually complete the proof it's asking for.
The exercises in Section 2.9 walk the reader through an alternative proof of $\phi(mn)=\phi(m)\phi(n)$ when $\mathrm{gcd}(m,n)=1$, where $\phi$ is the Euler totient function. (A different proof is given earlier.)
Exercise 2.9.2 asks the reader to show that if $\mathrm{gcd}(m,n)=1$, then $mn=\sum_{f|mn}\phi(f)=\sum_{d|m,e|n}\phi(de).$ I was able to do this easily enough.
Then Exercise 2.9.3 says to "use Exercise 2.9.2 and induction on $de
I really don't understand what Stillwell means by "induction on $de
Update on 2012-09-17:
Niccolò was very helpful in the comments in clarifying what was meant by Stillwell's comment on induction, and I'm sure that's what was meant, but I still can't seem to prove the statement in Ex. 2.9.3 by induction. (I thought it would be a straightforward matter of working out the details for the proof, and it may be, but I can't see it.)
So, here's my best attempt (such as it is): Assume that the equation above with the sums holds for $m^\prime n^\prime
$\begin{aligned} mn &= \sum_{d|m,e|n}\phi(de) \\ &= \phi(mn) + \sum_{d|m,d
where $m^\prime
Now I can use the inductive hypothesis on the last three terms, but it doesn't seem to get me anywhere (I think). I'll spare you the resulting sum which includes nine summations with various limits involving $m$, $m^\prime$, $n$, and $n^\prime$. It doesn't seem to help, unless I'm missing some clever way of combining all those sums.
Can anyone provide any help?