Можно наверное еще так:
Ваша сумма есть не что иное, как
свертка Дирихле функций

и

. Ну пусть Ваша сумма есть

, тогда она мультипликативна так как функции Мебиуса и Эйлера мультипликативны.
Очевидно, что

(из мультипликативности).
Пусть

тогда

. Значит,

Ну посчитаем для

Нетрудно убедиться, что
Здесь я также пользуюсь тем, что

при

Осталось их перемножить и все
(Оффтоп)
Руст опередил меня