Interchange of index in double summation -: $\sum_{n \leq x} \sum_{d | (n,K)} \mu(d) = \sum_{d | K} \sum_{n \leq x, d | n} \mu(d)$

Question

Can someone give a rigorous explanation for the interchange of index of summation. I am able to show that two sets consisting of the tuple $(n, d)$ satisfying conditions in LHS and RHS respectively, both the sets are same. Means the partion in two ways will give same union and then we can proceed. Although I am not very convinced and not getting the feeling with this. If some more rigorous approach is there then please tell me.

Answer 1

You've described a perfectly rigorous proof of the equality—the sets of tuples are the same.

I'm guessing what you are hoping for is a purely mechanical or algebraic rule that allows one to interchange summations without having to think about the underlying set of tuples. Satisfying as that would be, I don't believe it exists: the mathematically valid way to think about interchanging summations is by fully understanding the underlying set of tuples. (The same comment holds for interchanging integrals as well.)

The best I can offer as a system for interchanging summations is this: On the left, we first ask "which $n$s in the world appear?" and then "for a given $n$, which $d$s appear with that $n$?"; on the right, we first ask "which $d$s in the world appear?" and then "for a given $d$, which $n$s appear with that $d$?".

Answer 2

We know from elementary number theory that a natural number $d$ divides $n$ and $K$ iff it divides the greatest common divisor $(n,K$). We therefore have for $d,n,K\in\mathbb{N}$ and $x\geq 1$: \begin{align*} \left\{d:d|K,d|n,1\leq n\leq x\right\}=\left\{d:d|(n,K),1\leq n\leq x\right\} \tag{1} \end{align*}

We obtain starting with the right-hand side of OPs identity \begin{align*} \color{blue}{\sum_{d|K}\sum_{{n\leq x}\atop{d|n}}\mu(d)} =\sum_{n\leq x}\sum_{{d|K}\atop{d|n}}\mu(d) =\color{blue}{\sum_{n\leq x}\sum_{d|(n,K)}\mu(d)} \end{align*} and the claim follows

In the first step we change the order of summation which causes no harm, since the sums are all finite. In the second step we use (1).