This question is about exercise 2.31 in Apostol's Introduction to Analytic Number Theory.
The question asks us the following: if $f$ is a multiplicative arithmetic function, and $g$ is a completely multiplicative arithmetic function, and furthermore for all primes $p$ and $n \geq 1$ we have the relation
$$
f(p^{n+1}) = f(p)f(p^n) – g(p)f(p^{n-1}),
$$
then for all $n, m$
$$
f(n)f(m) = \sum_{d \mid \gcd(n, m)} g(d) f\left(\frac{nm}{d^2}\right).
$$
More than any exercise so far in this book, this looks completely arbitrary to me. I have solved it: you can consider the question only for $n=p^a, m=p^b$, and then it follows for arbitrary $n, m$ by multiplicativity of $f, g$; and we can prove it for $p^a \leq p^b$ by induction on $a$. But that has really taught me nothing: I don't understand why it might make some sense that this is true.
If $g(p) = 0$ for all primes $p$, then the relation we start from becomes $f(p^n) = f(p)^n$ — i.e., $f$ is completely multiplicative. Thus maybe we can see the $g(p)f(p^{n-1})$ as a sort of error term of the complete multiplicativity of $f$. But this doesn't help me see why the result makes sense.
Another approach I tried was noting that the relation allows us to write $f(p^k)$ as a polynomial in $f(p), g(p)$, but I wrote out a few and I didn't see a pattern I understood.
So my question is: where does this identity come from? How should I understand it, visualize it, "get" it? How would one come up with an exercise like this?
Best Answer
This identity a generalisation of the fact that
$$ f(m)f(n) = f(mn) $$
whenever $(m,n)=1$, which holds for any multiplicative function $f$. On seeing this, it's a natural question what happens when $m$ and $n$ are not coprime.
So we're asking for what $f(m)f(n)$ is for a multiplicative function for general $n$. We expect that $f(mn)$ is a 'main term' - indeed, if $f$ is completely multiplicative, then this is exactly what it is. And we know that it is also what it is when $(m,n)=1$. So we expect something like
$$ f(m)f(n) = f(mn) + E$$
where $E$ is some correction term that should depend only on $(m,n)$ and $mn$, and should vanish if $(m,n)=1$ or if $f$ is completely multiplicative.
The exercise gives an explicit form for $E$. As you say, there is some amount of calculation involved, but a small amount of trial and error would naturally lead to the correct form. One might begin, for example, by saying that we should measure how far the multiplicative $f$ is from being completely multiplicative. Completely multiplicative means $f(p^{n+1})=f(p)f(p^n)$, so one might define the function $F(p^{n})=f(p^{n+1})-f(p)f(p^n)$.
If you try and put that into $f(m)f(n)-f(mn)-E$ then it becomes apparent that it would be very convenient for an inductive argument if $F(p^n)$ could be 'factored' as $g(p)f(p^{n-1})$. Thus the hypothesis in the exercise.