If n = ∏p^{r} be the prime factorization of n, let f(n) = (-1)^{∑ r} and let F(n) = ∑_{d|n} f(d). Show that F(n) = 0 or 1. For which n is F(n) = 1?

**Solution**

Answer: F(n) = 1 for n square.

If some r is odd, then the factors of n can be grouped into pairs p^{a}m, p^{r-a}m with f(p^{a}m), f(p^{r-a}m) having opposite signs. So in this case F(n) = 0.

If all r are even, so that n is a square, then we may use induction on the number N of prime factors. For N = 1, we have n = p^{2m}, so there are m+1 factors p^{2r} with f = 1 and m factors p(2r+1) with f = -1. So the result is true for N = 1. Suppose it is true for N. Take n = p^{2m}P, where P has m prime factors. Each divisor of n has the form p^{2r}s or p^{2r+1}s, where s is a divisor of P. For the first type f(p^{2r}s) = f(s), so summing over s gives 1. Then summing over r gives m+1. For the second type f(p^{2r+1}s) = -f(s), so summing over s gives -1. Then summing over r gives -m. Hence F(n) = 1 and the result is true for N+1.

© John Scholes

jscholes@kalva.demon.co.uk

15 Feb 2002