First note that: (sum on both sides)
The idea is that iff
Indeed, to prove this:
, conversly if then and
Now since
It follows easily that: (only one of the terms is not 0 )
My proof of (1) is based on the following observation: then by a simple counting argument ( appears as many times as multiples of there are in between 1 and n -both included-, that is ): ...