10
$\begingroup$

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?

$\endgroup$
15
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.