Let $\{f_i\}_{i\in\mathbb N}$ be the sequence of Fibonacci numbers, i.e. $1,2,3,5,8,13,21,34,55,\cdots$, For every integer $n\gt3$ prove that $$4\mid\phi(f_n)$$ where $\phi$ is Euler's totient function.
By using the formula $\phi(p_1^{\alpha_1}\ldots p_k^{\alpha_k})=p_1^{\alpha_1-1}\ldots p_k^{\alpha_k-1}(p_1-1)\ldots(p_k-1)$ for distinct primes $p_i$ and natural numbers $\alpha_i$, we can say that the problem is equivalent to show that for $n\gt3$, $f_n\notin \{2^{\epsilon}q^k|k\in \mathbb N, q\equiv3\pmod4 \text{ be a natural prime number},\epsilon\in\{0,1\}\}$.