Find all $n\in \Bbb N $ such that $4$ does not divide $\phi(n)$ How can we find all $n\in \Bbb N $ such that $4$ does not divide $\phi(n)$?
 A: Recall that $\varphi$ is multiplicative: if $a$ and $b$ are relatively prime, then $\varphi(ab)=\varphi(a)\varphi(b)$.
Recall also that if $j\ge 1$, and $p$ is prime, then $\varphi(p^j)=(p-1)p^{j-1}$.
In particular, if $p$ is congruent to $1$ modulo $4$, then $\varphi(p^j)$ is divisible by $4$.
If $n$ is divisible by $8$, then $\varphi(n)$ is divisible by $4$.
From multiplicativity, if $n$ is divisible by two distinct odd primes, then $\varphi(n)$ is divisible by $4$.  
Similarly, if $n$ is divisible by $4$ and by an odd prime, then $\varphi(n)$ is divisible by $4$. 
So we only need to examine the cases $n=1$, $2$, $4$, $p^l$, and $2p^l$, where $p$ is an odd prime congruent to $3$ modulo $4$, and $l\ge 1$.  In all these cases, $\varphi(n)$ is not divisible by $4$.
A: I am assuming that you are taking $\phi$ to be the Euler totient function.
$\phi (n)$ =  $\phi (p_{1}^{k_1}...p_{n}^{k_n})$ = $\phi (p_{1}^{k_1}) ...\phi (p_{n}^{k_n})$ = $(p_{1}^{k_1}-p_{1}^{k_1-1})...(p_{n}^{k_n}-p_{n}^{k_n-1})$
(Where the $p_{i}$ are the distinct prime factors of n).
Now consider this modulo 4. And assume for now that none of the $p_{i}'s$ are 2. Then $p_{i} \equiv$ 1 or 3 mod 4.
Can you work it out from here? (Of course you will have to add the $p_{i}$ = 2 case in after, but this is not very difficult).
Spoiler : Clearly if any $p_i \equiv 1$ mod $4$ then $p_{i}^{k_i}-p_{1}^{k_1-1}$ $\equiv$ $0$ mod $4$
So we must have $p_{i}$ $\equiv 3$ mod $4$. But then $p_{i}^{k_i}-p_{1}^{k_1-1}$ $\equiv$ $2$ mod $4$
So the only numbers n that are such that $\phi (n)$ is not divisible by 4 are of the form n = $p_{i}^{k_i}$ where $k_i$ is some natural number and $p_i$ $\equiv$ to 3 mod 4.
Oh, and of course we must not forget our case $p_i$ = 2. In this case it is clear than the only number $n$ with a factor of 2, with $\phi (n)$ not divisible by 4 is n = 2 or 4 or $2p_{1}^{k_1}$ where again $p_i$ $\equiv$ 3 mod 4.
A: Another approach: if
$$n=\prod_{i=1}^kp_i^{a_i}\;\;,\;\;p_i\,\,\text{primes}\;\;,\;\;0<a_i\in\Bbb N$$
then
$$\phi(n)=n\prod_{i=1}^k\left(1-\frac{1}{p_i}\right)=n\prod_{i=1}^k\frac{p_i-1}{p_i}$$
So: if $\,n\,$ is divisible by two or more odd integers the above produc is divisible by $\,4\,$ , as $\,p_i-1\,$ is even in this case.
Also if $\,2^k\mid n\;\;,\;\;k\ge 3\,$ , then $\,4\mid\phi(n)\,$ , as there is only one factor equal to $\,2\,$ in the product's denominator that cancels, leaving $\,2^{k-1}\,$ as a factor of $\,\phi(n)\,$ .
Thus, we're searching for numbers that are divisible by at most one odd prime and\or by at most the second power of $\,2\,$ , and these numbers are
$$1,\,2,\,4,\,2p^r,\,p^r\;\;,\;\;p\;\;\text{an odd prime}$$ 
A: Since you apparently know the formula that
$$
  \phi(p_1^{m_1+1}\ldots p_k^{m_k+1}) = (p_1-1)p_1^{m_1}\ldots(p_k-1)p_k^{m_k}
$$
when the $p_i$ are distinct primes, there is a very simple argument. 
One sees that every first occurence of an odd prime factor in the factorization of $n$, and every occurence of a factor $2$ except the first, each contribute at least one factor $2$ to $\phi(n)$, and more than one factor $2$ in case of (odd) primes $p\equiv 1\pmod4$. So to have $4\not\mid\phi(n)$, what remains of the factorisation of $n$ after removing the first occurrence of $2$ (if any) and any non-first occurrences of other primes must be either empty or consist of a single prime $p\not\equiv 1\pmod4$. So one finds that either $n\in\{1,2,4\}$, or $n$ is a power of a prime $p\equiv3\pmod4$ possibly multiplied by $2$.
(This is just André Nicholas' answer with fewer cases.)
