If n = ∏pr 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 pam, pr-am with f(pam), f(pr-am) 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 = p2m, so there are m+1 factors p2r 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 = p2mP, where P has m prime factors. Each divisor of n has the form p2rs or p2r+1s, where s is a divisor of P. For the first type f(p2rs) = f(s), so summing over s gives 1. Then summing over r gives m+1. For the second type f(p2r+1s) = -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