Help with abstract algebra question?

Question

φ(n) is almost always divisible by 4. Describe all the n's for which φ(n) is not divisible by 4.

Answer 1

Uh, what's phi(n)? The number of factors of n?

First of all, let's figure out when it's even. That's easy. Factors pair off (a,b), where ab = n. The only exception to that would be when a = b. Thus, an integer has an odd number of factors if and only if it's a perfect square.

Next, factor n into two relatively prime pieces -- let's say r and s. n = rs. Look at the number of factors each of r and s. How many factors does n have? Well, each factor of n can be expressed uniquely as a factor of r times a factor of s. I.e., the number is just the product of the number of factors of r times the number of factors of s.

For a last hint, the number of factors of p^k, p prime, is just k+1.

Now, factor an arbitrary n into prime powers, and you should be able to figure out the whole problem pretty quickly.

Answer 2

Why your Q&A marked private?