For which positive integers n is $\varphi(n)$ divisible by 4? For which positive integers n is $\varphi(n)$ divisible by 4
where $\varphi(n)$ is the Euler Phi-function?
 A: Remark(I): Suppose that $n=\prod_{i=1}^kp_i^{\alpha _i}$; then: 
$$\varphi(n)=\prod_{i=1}^m \Bigg((p_i-1)p_i^{\alpha_i -1}\Bigg).$$
Remark(II): Suppose that $\gcd(m,m')=1$; 
then $\varphi(m\cdot m')= \varphi(m)\cdot \varphi(m').$

So we can get the following results: 
Lemma(I):If $n$ has at least one prime factor of the form $4k+1$; 
then it's euler's function is divisible by $4$. Because in it's factorization the factor $p-1$ appears. 
Lemma(II):If $n$ has two distict odd prime factor of the form $4k+3$ 
like $p,q$ in it's factorization; 
then in the factorization of it's totient-function the product of $p-1$ and $q-1$ appears; so it's euler's function must divisible by $4$.
Lemma(III): 
If the power of $2$ in the prime factorization of $n$ is equal or greater than $3$; 
then it's euler's function is divisible by $4$.
Lemma(IV): 
If the power of $2$ in the prime factorization of $n$
is equal or greater than $2$; and $n$ also has another odd prime factor; 
then it's euler's function is divisible by $4$.


Lemma(V): $\varphi(n)$ is $\color{Red}{\text{not divisible}}$ by $4$  $\color{Blue}{\text{iff and only if}}$ $n$ has one of the following forms: 


*

*$n=1$ or $n=p^m$ where $p\overset{4}{\equiv}3$;

*$n=2$ or $n=2\cdot p^m$ where $p\overset{4}{\equiv}3$;

*$n=4$.
$\color{Red}{\text{Except}}$ these values; for all other values $\varphi(n)$ is divisible by $4$.
Proof:  


*

*$n$ could not have any odd prime factor of the form $4k+1$.  

*Also it could not has more than one odd prime factor.  

*So it has at most one odd prime factor of the form $4k+3$,
and no any prime factor of the form $4k+1$. 
So it's general form is like the following $n=2^{\beta}\cdot p^{\alpha}$; where $p\overset{4}{\equiv}3$; and by a simple calculation the proof will be end...
A: Hint. If $\prod_{i=1}^mp_i^{r_i}$ is the  prime factorization of $n$
then by the product formula
$$\varphi(n)=n\prod_{i=1}^m\left(1-\frac{1}{p_i}\right)=n\prod_{i=1}^m\frac{p_i-1}{p_i}.$$
Note that $p_i$ is odd when $p_i\not=2$ and therefore $\varphi(n)$ is multiple of $4$ when $n$ is divisible by more than one odd prime or when $n$ is divisible by $8$. Are you able to finish the work?
A: We can prove $(\phi)n$ is multiplicative and is even for $n>2$
So, it will be divisible by $4$ if
$(1):n$ is product of at least two different odd prime powers
$(2):n$ has a prime divisor $p\equiv1\pmod4$
$(3):\phi(2^{m+1})=?$ for $m\ge0$
A: Let $n=2^a m$ where $m$ is odd integer.
Then $\phi(n)=2^{a-1} \phi(m)$
$\color{blue}{Case \; I}$:
Let $a-1\ge 2,\; \text{i.e} \;$ $a\ge 3$.
Then $\phi(n)$ is divisible by $4$.
$\color{blue}{Case \; II}$:
Let $a-1=1,\;\text{i.e} \; a=2$.
Then $n=4m$ and $\phi(n)=2\phi(m)$
If $m>1$, then $\phi(m)$ is always even (because $m$ is odd also) which implies that $\phi(n)$ is divisible by $4$.
If $m=1$, then $n=4$ and $\phi(4)=2$ is not divisible by $4$.
Thus we see from Case I and II that $\phi(n)$ is divisible by $4$ if one of the following conditions holds:

$\color{maroon}{1. \;n=8m \quad\text{for any positive integer} \quad m } $
$\color{maroon}{2.\; n=4m \quad\text{for any positive integer}\quad m>1}$.

Combining these two, we get, $\color{fuchsia}{\phi(n)\text{ is divisible by}\; 4 \;\text{if}\; n=4m \;\text{for some positive integer} \; m>1}$.
$\color{blue}{Case \; III}$:
Let $a-1=0,\;$ i.e $\; a=1$.
Then $n=2m$ and $\phi(n)=\phi(m)$
Therefore $\phi(n)$ is divisible by $4$ iff $\phi(m)$ is divisible by $4$. Since $\phi(1)=1$, it is clear that $m>2$ and thus possesses a prime factorization, say $p_1^{\alpha_1 } p_2^{\alpha_2 }\cdots p_r^{\alpha_r }$ where $p_i$’s are distinct odd primes and $\alpha_i$’s are positive integers and $r\ge 1$.
Therefore
\begin{equation*}
\phi(m)=\prod_{i=1}^r p_i^{\alpha_{i-1}}(p_i-1)
\end{equation*}
Now each $(p_i-1)$ is even since each $p_i$ is odd. So $\phi(m)$ is divisible by $4$ if there are at least two such factors $(p_i-1)$, i.e $r\ge 2$.
Again if $r=1$, then $\phi(n)=p_1^{\alpha_1-1} \left(p_1-1\right)$ is divisible by $4$ iff $4|p_1-1$.
Thus from all the three cases, we can conclude that $\phi(n)$ is divisible by $4$ if

$\color{maroon}{1.\; n=4m\; \text{for some positive integer} \;m>1}$.
$\color{maroon}{2. \;n=2m \;\text{where} \;m\; \text{is odd with at least two distinct prime divisors or with one prime divisor in the form}\; 4k+1}$.

