$n^4 + 4^n$ is a not a prime Prove that $n^4 + 4^n$ is not a prime for all $n &gt; 1$ and $n \in \mathbb{N}$.

This question appeared in the undergrad entrance exam of  the Indian Statistical institute.

When $n$ is even the proof is simple. 
For $n = 2m+1$ I am utterly stuck.
Let $n=2k+1$ with $k\geq 1$, then
$$n^4+4^n=n^4+4 \cdot 4^{2k}=n^4+4\cdot (2^k)^4=(n^2+2\cdot 2^{2k}+2^{k+1}n)(n^2+2\cdot 2^{2k}-2^{k+1}n).$$
Thus $n^4+4^n$ can be factored into non-trivial factors, when $n$ is odd.
Remember doing this as an Exercise from Ivan Niven's Number Theory book. I think this follows from an identity of Sophie Germain, namely $$a^{4} + 4b^{4} = (a^{2}+2b^{2}-2ab)(a^{2}+2b^{2}+2ab).$$

See also this article on the identity.