Proof question?

Question

Liouville's lambda function λ(n) is defined by factoring n into a product of primes n = (p_1)^k_1 + (p_2)^k_2 +...(p_r)^k_r and then setting λ(n) = (-1)^(k_1 + k_2 +...k_r)

The function g(n) is defined as follows):
G(n) = λ(a_1) + λ(a_2) + ... λ(a_r), where a_1 through a_r are the divisors of n.

I noticed that when you compute the value of G(n), it is 1 for perfect squares and -2 for all other values. How do I prove this?

Answer 1

I may be reading this wrong, but it looks to me like:

g(n) = 1 is n is a perfect square and 0 if not

To see this, we can use induction on the number of prime factors a number has.

Base case: n has 0 prime factors, so n=1, so G(n) = L(n) = 1

Assume: if n has exactly r prime factors then g(n) = 1 is n is a perfect square and 0 if not.

Now suppose n has r+1 prime factors, let the largest be p and let its exponent be k. Notice that:

G(n) = G(n/(p^k)) * (1 - 1 + 1 .... + (-1)^k)
(to see this note that any divisor of n is a divisor of n/(p^k) times a power of p with exponent between 0 and k)

Now, we can see that n is a square iff both n/(p^k) and p^k are squares. Similarly, G(n)=1 iff both G(n/(p^k)) = 1 (meaning n/(p^k) is a square) and (1 - 1 + 1 .... + (-1)^k) = 1 (meaning k is even so p^k is a square).

So we have shown by induction that g(n) = 1 is n is a perfect square and 0 if not.