# 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.
$$\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}$$