An expression with gcd and abs is transformed magically!

Question

There's a problem to calculate $\sum^{n}_{i=1}\sum^{m}_{j=1}\frac{|i-j|}{\gcd(i,j)}$, whose tutorial gives the following transformation I really don't understand. $$\sum^{n}_{i=1}\sum^{m}_{j=1}\frac{|i-j|}{\gcd(i,j)} \\ =\sum^{n}_{i=1}\sum^{m}_{j=1}\sum_{d}\frac{|i-j|}{\gcd(i,j)}[\gcd(i,j)=d] \\ =\sum_{d}\sum^{\lfloor\frac{n}{d}\rfloor}_{i=1}\sum^{\lfloor\frac{m}{d}\rfloor}_{j=1}|i-j|[\gcd(i,j)=1] \\ =\sum_{d}\sum^{\lfloor\frac{n}{d}\rfloor}_{i=1}\sum^{\lfloor\frac{m}{d}\rfloor}_{j=1}|i-j|\sum_{d'|\gcd(i,j)}\mu(d') \\ =\sum_{d}\sum_{d'}d'\mu(d')\sum^{\lfloor\frac{n}{dd'}\rfloor}_{i=1}\sum^{\lfloor\frac{m}{dd'}\rfloor}_{j=1}|i-j| \\ =\sum_{d}\sum_{d'|d}d'\mu(d')\sum^{\lfloor\frac{n}{d}\rfloor}_{i=1}\sum^{\lfloor\frac{m}{d}\rfloor}_{j=1}|i-j|$$ Please show me a bit more detail about last two steps. Thanks a lot!

Answer 1

$$\sum^{n}_{i=1}\sum^{m}_{j=1}\frac{|i-j|}{\gcd(i,j)} \\ \overset{(1)}=\sum^{n}_{i=1}\sum^{m}_{j=1}\sum_{d}\frac{|i-j|}{\gcd(i,j)}[\gcd(i,j)=d] \\ \overset{(2)}=\sum_{d}\sum^{\lfloor\frac{n}{d}\rfloor}_{i=1}\sum^{\lfloor\frac{m}{d}\rfloor}_{j=1}|i-j|[\gcd(i,j)=1] \\ \overset{(3)}=\sum_{d}\sum^{\lfloor\frac{n}{d}\rfloor}_{i=1}\sum^{\lfloor\frac{m}{d}\rfloor}_{j=1}|i-j|\sum_{d'|\gcd(i,j)}\mu(d') \\ \overset{(4)}=\sum_{d}\sum_{d'}d'\mu(d')\sum^{\lfloor\frac{n}{dd'}\rfloor}_{i=1}\sum^{\lfloor\frac{m}{dd'}\rfloor}_{j=1}|i-j| \\ \overset{(5)}=\sum_{d}\sum_{d'|d}d'\mu(d')\sum^{\lfloor\frac{n}{d}\rfloor}_{i=1}\sum^{\lfloor\frac{m}{d}\rfloor}_{j=1}|i-j|$$

I suppose that by the last two steps you mean equalities (4) and (5).

---

In (4) we want to change order of summation. We have that $d'$ divides both $i$ and $j$. This means that $i=kd'$ and $j=ld'$ for some $l$ and $k$. To get $1\le id \le n$ we need to have $1\le kd'd\le n$, meaning that $k$ is between $1$ and $\lfloor \frac n{d'd}\rfloor$. Similarly we can get bounds for $l$.

After this transformation we have $|i-j|=|kd'-ld'|=d'|k-l|$.

From this we get $$\sum_{d}\sum^{\lfloor\frac{n}{d}\rfloor}_{i=1}\sum^{\lfloor\frac{m}{d}\rfloor}_{j=1}|i-j|\sum_{d'|\gcd(i,j)}\mu(d') =\\ \sum_{d}\sum^{\lfloor\frac{n}{dd'}\rfloor}_{k=1}\sum^{\lfloor\frac{m}{dd'}\rfloor}_{l=1}d'|k-l|\sum_{d'}\mu(d') = \\ \sum_{d} \sum_{d'}d'\mu(d') \sum^{\lfloor\frac{n}{dd'}\rfloor}_{k=1}\sum^{\lfloor\frac{m}{dd'}\rfloor}_{l=1}|k-l|$$

This is the same as in your post, the only difference is that variables are denoted by $i$ and $j$ instead of $k$ and $l$.

---

In the equation (5) we simply denote $d'd$ as the new $d$. This means that after this change $d$ must be multiple of $d'$, so we sum only over the pairs where $d'\mid d$. (If it helps to make it clearer, you can choose a new variable name to denote this expression, for example $d''=dd'$. It is clear that $d\mid d''$ and, conversely, every multiple of $d'$ is of this form.)