The Composite Prime Problem

If $n$ is even then $n^4 + 4^n$ is certainly even, and so composite. If $n=2m+1$ is odd then $n^4 + 4^n \; = \; n^4 + 2^{2n} \; = \; (n^2 + 2^n)^2 - 2^{n+1}n^2 \; = \; (n^2 + 2^n)^2 - (2^{m+1}n)^2 \; = \; \big(n^2 + 2^n - 2^{m+1}n\big)\big(n^2 + 2^n + 2^{m+1}n\big)$ Since $n^2 + 2^n - 2^{m+1}n \; = \; n^2 + 2^{m+1}(2^m-2m-1) \; > \; 1$ for all $m \ge 3$ , we see that $n^4 + 4^n$ is composite for all $n \ge 7$ , and we only need to check $n=3,5$ by hand. Since $n^4 + 4^n$ equals $145$ and $1649$ when $n=3,5$ respectively, and these numbers are divisible by $5$ and $17$ , we deduce that $n^4 + 4^n$ is composite for all integers $n > 1$ .