4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Are you familiar with Fermat’s Little Theorem? $\endgroup$ – Arturo Magidin Aug 14 '19 at 5:36
  • 1
    $\begingroup$ 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. $\endgroup$ – Greg Martin Aug 14 '19 at 5:47
5
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Aug 14 '19 at 6:05
2
$\begingroup$

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$

$\endgroup$
-1
$\begingroup$

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

See also this article on the identity.

$\endgroup$
7
  • 4
    $\begingroup$ We prefer answers to not rely this heavily on external links. Please consider writing the identity into the same itself. As it stands now, if cut-the-knot.org's servers are down, or they decide to move that specific page to a different address, then this answer becomes almost worthless as it stands. $\endgroup$ – Arthur Aug 14 '19 at 5:52
  • $\begingroup$ @Arthur What you say is correct. But the more pressing matter related to site hygiene and this question is that it has been asked 10+ times already. $\endgroup$ – Jyrki Lahtonen Aug 14 '19 at 6:08
  • 1
    $\begingroup$ @JyrkiLahtonen Speaking of broken links. Your link doesn't work on mobile. $\endgroup$ – Arthur Aug 14 '19 at 6:10
  • 1
    $\begingroup$ @Arthur : Done! Though i disagree on your view. IF the cut the knot servers are down, the curious student will make a google search Sophie Germain Identity and find the answer for himself :) $\endgroup$ – crskhr Aug 14 '19 at 8:59
  • 1
    $\begingroup$ Yes, using the name, one can search for the solution. But the answer is still not self-contained (at least to the degree that I personally prefer). And @JyrkiLahtonen "Sorry, math input on mobile platform is not supported yet, please visit this site on PC or tablet." It's not a question about missing plugin. They specifically bar mobile browsers from entering the site. But yes, many (and perhaps even most) are on computers or tablets, and your point wasn't that site in particular, but rather your claim was backed up by the info behind the link, so your point still stands. $\endgroup$ – Arthur Aug 14 '19 at 11:44

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