Help with phi problem?

Question

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

Answer 1

Let 's do it step by step.
If n =1 or 2, φ(n) = 1. Otherwise, φ(n) is even,
so we want φ(n) = 2(mod 4).
If n is a power of 2, that gives n = 4.
Suppose, then
n = p_1^a_ 1 ... p_k^a_k is the decomposition of
n into its prime factors.
Then
φ(n) = p_1^(a_1 - 1) (p_1-1) ... p_k^(a_k-1)(p_k-1).
If there is more than one odd prime in this list
then the 2 or more p_i-1 factors would
make φ(n) divisible by 4.
So the only primes that can occur in this list
are 2 and at most 1 odd prime.
Next, our odd prime cannot be 1 mod 4 because
then p-1 =0(mod 4).
and the only possible power of 2 here is the first
power, since φ(2^k) is divisible by 2 if k > 1
and then φ(2^k)*(p-1) is divisible by 4.
So the only possibilities are n = 1, 2, 4,
n = p^a and n = 2p^a,
where p is an odd prime and p = 3(mod 4).
Examples: φ(9) = 6, φ(22) = 10.

Answer 2

If n has a prime factorization [i=1, n]∏p_i^(k_i), where p_1, p_2... p_n are distinct prime factors and k_1, k_2... k_n are positive integers, then φ(n) is [i=1, n]∏((p_i - 1)p_i^(k_i -1)). Now, since if p is any odd prime p-1 will be divisible by two, it follows that if there are at least two distinct odd primes in the factorization of n, then φ(n) will be divisible by 4. Also, if p≡1 mod 4 and p is a factor of n, then φ(n) will be divisible by 4. Also, if 2^k is a a factor of n, and either k≥3 or (k≥2 and n is divisible by at least one odd prime) then 4 will be a factor of φ(n). Therefore, the numbers for which φ(n) are not divisible by 4 are:

1, 2, and 4
p^k (where p is an odd prime congruent to 3 mod 4 and k is any positive integer)
2*p^k (where p is an odd prime congruent to 3 mod 4 and k is any positive integer)