# Compositeness of $n^4+4^n$ [duplicate]

My coach said that for all positive integers $n$, $n^4+4^n$ is never a prime number.

So we memorized this for future use in math competition. But I don't understand why is it?

In order to get a prime, we need $n$ odd. So $4^n=4\cdot 4^{2k}$ for some $k$, and therefore $4^n=4\cdot (2^k)^4$ where $k=\frac{n-1}{2}$.

Now use the factorization $$x^4+4y^4=(x^2-2xy+2y^2)(x^2+2xy+2y^2),$$ with $x=n$ and $y=2^{(n-1)/2}$.

The case $n=1$ gives the lone prime. For all other $n$, we have $x^2-2xy+2y^2\gt 1$.

Remark: It is hard to judge whether the above factorization is "natural." Perhaps it will look more reasonable if we express $x^4+4y^4$ as a difference of squares: $$x^4+4y^4=(x^2+2y^2)^2-4x^2y^2.$$

You can work $\bmod 5$:

As Jossie said, if $n$ is even, then both numbers are even. If $n$ is odd, set $n = 5k + r$;

If not, you can repeatedly use the fact that for $p$ a prime and $(a, p) = 1, a^{p - 1} = 1 \pmod p$ and so $a^p = a \pmod p$;

in this case, $(a, 5) = 1$ , then $a^{4n} = 1 \pmod 5$

$0 \leq r <5$ . Then

$4^n + n^4 = 4^{5k + r} + r^4 \pmod 5 = 4^{5k} 4^r + r^4 = 4^{r + 1} + 1 = 4$. $4^r + 1 = 4 + 1 = 5 \pmod 5$.

• O.K, let me address that case. – DBFdalwayse Sep 10 '13 at 3:57
• It was useful, dealt with four-fifths of the cases. – André Nicolas Sep 10 '13 at 4:43
• Right;thanks, but maybe not useful-enough, given you covered all cases. Sorry, editor. – DBFdalwayse Sep 10 '13 at 4:44
• After a while, one gets to value partial results. – André Nicolas Sep 10 '13 at 4:46