# Do there exist any odd prime powers that can be represented as $n^4+4^n$?

Well, I wrote up a solution on it, but according to the place I found the problem, it isn't quite correct. Ah, I'm simply hoping someone will point out where I got wrong.

Now, let, $n^4+4^n = p^k$, where $p$ is an odd prime and $k$ is a positive integer.

Further, $p^k \equiv 1 \pmod 2$. Therefore, $n^4 + 4^n \equiv n^4 \equiv 1 \pmod 2$, and so $n \equiv 1 \pmod 2$. $n$ must be odd.

Okay, now let, $n = 2m +1$. Substituting it in $n^4+4^n$ and using the Sophie Germain inequality, we have,

$$n^4+4\cdot4^{2m} = n^4 + 4(2^m)^4 = (n^2 + 2^n+2^{m+1}\,n)(n^2 + 2^n-2^{m+1}\,n) = p^k$$

Now, as $p^k$ can only be factorized into smaller powers of $p$, let $n^2 + 2^n+2^{m+1}\,n = p^i$, and let $n^2 + 2^n-2^{m+1}\,n = p^j$ where $i+j= k$, obviously, and $i>j$.

Now consider this:

\begin{align} p^i - p^j & \equiv 0\\ 2\cdot2^{m+1}\,n = 2^{m+2}\,n &\equiv 0 \pmod p \end{align}

But, as $p$ is odd, $\gcd(p, 2) = 1$, so $n \equiv 0 \pmod p$.

Now look at this:

\begin{align} p^i + p^j &\equiv 0 \\ 2(n^2 + 2^n) &\equiv 0 \\ n^2 + 2^n &\equiv 0 \pmod p \end{align}

But we just established that $n \equiv 0 \pmod p$, so $2^n \equiv 0 \pmod p$.

Therefore, let $2^n = jp$ for some integer $j$.

Now, $2^n$ is its own prime factorization, which is unique according to the Fundamental Theorem of Arithmetic and does not include $p$. Therefore, the above statement is an impossibility! There exist no such $p$ and $n$, and no odd prime powers can be written as $n^4+4^n$.

Ah, well, that's it. Sorry for the tediousness of it. I've still no clue how to use $\LaTeX$.

Thank you everybody,

Cheers.

-
Latex is really simple in this case. Just write $p^i$ which looks like $p^i$ instead of p^i and everything looks much nicer ;) – cmmndy Dec 19 '12 at 7:41
I haven't finished reading your argument, but $p^j$ might not be $0$ mod $p$, if $j$ is $0$. Have you considered that one of your two factors of $p^k$ might be $1$? – alex.jordan Dec 19 '12 at 8:01
Use curly braces to group terms that you want to put in the exponents. – alex.jordan Dec 19 '12 at 8:02

There is the small counterexample

$$5^1=1^4+4^1$$

-
*Facepalm. How could I miss that?! Ah, thanks for that. – AlpArslan Dec 19 '12 at 8:16

I think that your argument works as long as the smaller of your two factors $$n^2+2^n−2^{m+1}n$$ is not equal to $1$. In the case of $n=1$, it does equal $1$, and you get Henry's counterexample. For larger $n$,

\begin{align}n^2+2^n−2^{m+1}n&=n^2+2^n-2^{(n+1)/2}n\\ &=n^2+\sqrt{2^n}(\sqrt{2^n}-n\sqrt{2})\end{align}

will be larger than $1$ for sure once $n$ is large enough for $\sqrt{2^n}-n\sqrt{2}>0$. This is equivalent to $2^n>2n^2$. This inequality is true for $n=7$. Calculus can confirm that it holds once $n$ is beyond $7$ too:

Let $f(n)=2^n$ and $g(n)=2n^2$. Then $f''(n)=2^n(\ln(2)^2)$ and $g''(n)=4$. So certainly for $n\ge7$, $f$ has the larger second derivative. The first derivative of $f$ at $n=7$ is $128\ln(2)$, which is larger than $g$'s first derivative at $n=7$, which is $28$. So for all $n\ge7$, $f$ has the larger first derivative. The same argument applies to $f'$ and $g'$, and so we conclude that $f(n)>g(n)$ when $n\ge7$.

We can directly check that $n^2+2^n-2^{(n+1)/2}n\neq1$ when $n$ is $3$ or $5$.

-
Ow. That's a good objection. You're right, I didn't considered that $p^j$ may be 1 after all. Thanks a bunch, mate. – AlpArslan Dec 19 '12 at 8:26
Wait. How would one use calculus for this? By finding the minima by differentiation? I'd use an inductive argument, perhaps. – AlpArslan Dec 19 '12 at 8:27
Maybe there are other ways, but calculus came to mind. The $2^n$ term dominates the $2^{(n+1)/2}n$ term pretty quickly, and you just need to show that somehow. I thought by comparing first and second derivatives to the constant function. Then perhaps directly examine some small $n$ values. – alex.jordan Dec 19 '12 at 8:31
I edited the answer to include some discussion of the role of calculus. – alex.jordan Dec 19 '12 at 8:42

For odd n>1 the expression is never prime, it can be factored into a product where each factor is the sum of two squares. $$[((2^m)+n)^2 +(2^m)^2][(2^m)^2 +((2^m)^2-n)^2]$$ where $m = (n-1)/2$

-
A stray ^2 has crept into your final term. It should be $((2^m) - n)^2$. And see this for a Mathjax tutorial. – Peter Phipps Dec 19 '12 at 12:45
Yes, but OP asks if the expression could be a prime power, not just a prime. Also, proving that neither factor could trivially equal $1$ is a separate argument. – alex.jordan Dec 19 '12 at 19:24

For odd $n>1$ the expression is never prime, it can be factored into a product where each factor is the sum of two squares: $$[((2^m)+n)^2 +(2^m)^2][(2^m)^2 +((2^m)^2-n)^2],$$ where $m = (n-1)/2$.

Looks like I didn't read the question properly thanks for the feedback. I will try and improve my answer.

Let the first factor be $A$ and the second $B$. Then we have $AB = p^k$ with $k >1$, as if $k= 1$ then we have the case $AB =5$. This means in $A$ and $B$, $n >1$, and so $m$ is at least $1$, (as $n$ is odd). Then it's easy to see that neither $A$ or $B$ is trivially $1$. So we can set $k = r+s$ and as $A > B$ we can put $A = p^r$, and $B = p^s$, with $r>s>0$. Now forming the difference of $A$ and $B$, means, we have; $$A - B = p^r - p^s = n 2^{m+2}.$$ But as $p>s>0$, we have $p$ divides $n$ ($p$ is an odd prime) but this means $p$ divides $4$, as we have assumed $p^k = n^4 + 4^n$, with $k >1$, which is absurd. Therefore the original expression is only only the power of an odd prime for the case $p = 5$.

-
Welcome to SE Paul. Please note that you don't need so many $signs in a single mathematical expression. Just put one$ sign at the beginning and one at the end of the math expression. That will also make the superfluous \$ sign above disappear. – Ittay Weiss Dec 20 '12 at 23:41