Euler's phi function $\phi(n)$ is even for all $n \geq 3$; when is it not divisible by $4$? Problem 1: Show that $\phi(n)$ is even for all $n \geq 3$. 
Proof: Assume that n is a power of 2, let us say that $n=2^k$, with $k \geq 2$. By the Phi Function Formula, we have $\phi(n) = \phi(2^k)=2^k - 2^{k-1}=2^k(1/2)=2^{k-1}$, which $\phi(n)$ is an even integer.
If n isn't a power of 2, then it is divisible by an odd prime p. Thus, $n=p^km$, where $k \geq 1$ and $gcd(p^k,m)=1$. By the theorem $\phi(mn)=\phi(n)\phi(m)$,
$\phi(n)=\phi(p^km)=\phi(p^k)\phi(m)=p^k(p-1)\phi(m)$,
which is 2|p-1, since p is odd prime.
Problem 2: Describe, with proof, all $n$ for which $\phi(n)$ is divisible by $2$, but not by $4$.
How would you solve this problem? Can you use Problem 1?

HINT: If $p$ is prime, $\varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)$. If $m$ and $n$ are relatively prime, then $\varphi(mn)=\varphi(m)\varphi(n)$. And every $n\ge 1$ is a product of powers of distinct primes. These facts make the first question very easy to answer and are sufficient to answer the second question as well. 
You might find it helpful to look at some numerical data while you’re thinking about the problem:
$$\begin{array}{c|c|c}
n&\text{prime factorization}&\varphi(n)\\ \hline
2&2^1&1\\
3&\color{blue}{3^1}&2\\
4&2^2&2\\
5&\color{blue}{5^1}&4\\
6&2^1\cdot\color{blue}{3^1}&2\\
7&\color{blue}{7^1}&6\\
8&2^3&4\\
9&\color{blue}{3^2}&6\\
10&2^1\cdot\color{blue}{5^1}&4\\
11&\color{blue}{11^1}&10\\
12&2^2\cdot\color{blue}{3^1}&4\\
13&\color{blue}{13^1}&12\\
14&2^1\cdot\color{blue}{7^1}&6\\
15&\color{blue}{3^1}\cdot\color{blue}{5^1}&8\\
16&2^4&8\\
17&\color{blue}{17^1}&16\\
18&2^1\cdot\color{blue}{3^2}&6\\
19&\color{blue}{19^1}&18\\
20&2^2\cdot\color{blue}{5^1}&8\\ \hline
25&\color{blue}{5^2}&20\\ \hline
27&\color{blue}{3^3}&18\\ \hline
30&2^1\cdot\color{blue}{3^1}\cdot\color{blue}{5^1}&8
\end{array}$$
You might also find this article useful.
