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

Solution 1:

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

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