# 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?

-
I guess he means induction on $k=mn$. So your inductive step would be supposing the claim is true for any pair $(m',n')$ with $m'n'<mn$ (and such that $m'$ and $n'$ are coprimes) and proving it is true for $mn$. –  Niccolò Sep 14 '12 at 1:32
@Niccolò Okay, that makes sense. To prove it is true for $mn$, you can use the result from Ex. 2.9.2, where the divisors of $m$ and $n$ are each less than $m$ and $n$, except of course for $m$ and $n$ themselves, which you can pull out of the sum (while altering the limits of the summation). I'm sure this will work, I just need to work out the details. –  Richard Sullivan Sep 14 '12 at 1:43
Now my next question, is Stillwell's way of wording this awkward, or is the problem on my end? –  Richard Sullivan Sep 14 '12 at 1:44
It could have been worded more clearly, but it's not actionable, in my opinion. @Niccolò's interpretation was somewhat clearer. –  Rick Decker Sep 14 '12 at 2:04