# $n^4 + 4^n$ is a not a prime [duplicate]

Prove that $$n^4 + 4^n$$ is not a prime for all $$n > 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.

• Are you familiar with Fermat’s Little Theorem? – Arturo Magidin Aug 14 '19 at 5:36
• It's not a complete solution, but it's nice to be able to note that when $n$ is odd and not a multiple of $5$, we have $n^4+4^n \equiv 1+4\equiv0\pmod 5$, so is not prime. – Greg Martin Aug 14 '19 at 5:47

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.

• Approach0 gives more than ten duplicates on our site. As a trusted user it is expected from you to search, when it is likely that a question has been asked earlier. – Jyrki Lahtonen Aug 14 '19 at 6:05

Firstly, I’ll show that we can factorise $$x^4+4y^4$$. $$x^4+4y^4=x^4-4x^2y^2+4y^4-4x^2y^2= \left(x^2+2y^2\right)^2-\left(2xy\right)^2= \left(x^2+2xy+2y^2\right)\left(x^2-2xy+2y^2\right)$$

Back to the question, when $$n=2m+1$$ that $$m$$ is a positive integer, we can substitute $$x=n$$ and $$y=2^m$$ into the polynomial above, we’ll get $$n^4+4\times\left(2^m\right)^4=n^4+4\times4^{2m}=n^4+4^{2m+1}=n^4+4^n=\left(n^2+2^{m+1}n+2^{2m+1}\right)\left(n^2-2^{m+1}n+2^{2m+1}\right)$$ Therefore, $$n^4+4^n$$ is not a prime for all odd number $$n>1$$

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).$$