# Induction in proof of multiplicativity of Euler totient function

(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<mn$” to show that
$$mn=\phi(mn)+\phi(m)\left(\sum_{e|n,e<n}\phi(e)\right)+\phi(n)\left(\sum_{d|m,d<m}\phi(d)\right)+\sum_{d|m,d<m,e|n,e<n}\phi(d)\phi(e)$$

I really don’t understand what Stillwell means by “induction on $de<mn$”. Can anyone offer some insight as to how to proceed? It’s likely that this is simple, but simple things often elude me.

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<mn$. Then,

\begin{aligned} mn &= \sum_{d|m,e|n}\phi(de) \\ &= \phi(mn) + \sum_{d|m,d<m}\phi(dn) + \sum_{e|n,e<n}\phi(me) + \sum_{d|m,d<m,e|n,e<n}\phi(de) \\ &= \phi(mn) + mn^\prime + m^\prime n + m^\prime n^\prime \end{aligned}

where $m^\prime<m$ and $n^\prime< n$. (That last step was gotten by applying the result from Ex. 2.9.2. See the OP, above.)

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?