I have been trying to solve this problem for past 2 days, but I havent come up with a formal solution.

I have tried to change the order of sums and grouping by gcd but couldnt get any further than getting a bound on distinct values of gcd .
Can someone please help?
Source: PE 530