Let such that . Then Proof:
Let the prime factorization of be . Every nonzero contribution to the sum above comes from divisors of with non-repeated prime factors, so the product of a subset of . So our sum is
Theorem: Möbius inversion formula
Let be functions of and let Then Proof:
We have where we see that the inner sum is zero unless , so we do indeed have that this equals .