Exponential Prime Powers

The question, when stated in mathematical terms is:

$4^n + n^4 = p^j$

The idea as with all such number theory questions with the word "prime" is to factorise . Well, for our case, for the sake of simplicity in factorisation, we shall first deal with the case when $p \neq 2$ , in other words $n$ is odd. So we let $n = 2k+1$ for a certain $k$ . The next big idea is that when one sees a power of $4$ and one needs a factorisation, one should use the Sophie Germain Identity .

So applying the identity, we can easily get:

$n^4 + 4^{2k+1} = n^4 + 4 \times 4^{2k} = (n^2 + 2^n + 2^{k+1}n)(n^2 + 2^n - 2^{k+1}n) = p^j$

However, since $p$ is a prime, the smaller of these two factors might be $1$ . Intuitively, we split this into two sub-cases:

(i) None of the factors is $1$ . Basically this means we can rewrite the equation as follows:

(a) $n^2 + 2^n + 2^{k+1}n = p^x$

(b) $n^2 + 2^n -2^{k+1}n = p^y$

where clearly $x + y = j, x > y$ . Now when we see two equations that look alike and have $+ , -$ , in other words, they look like conjugates, one very clean method is to sum and subtract them. In our case, (a) - (b) trivially gives:

$2 \times 2^{k+1}n = 2^{k+2}n \equiv 0 (mod p)$

Now, recall that we assumed $gcd(2,p) =1$ , this means that due to the above equation, we have $n \equiv 0 (mod p$ (*). Similarly, (a) + (b) would give:

$2n^2 + 2\times 2^n = 2n^2 + 2^{n+1} \equiv 0 (mod p)$

This is the trick! We have that $p | n$ so this implies that $2^{n+1} \equiv 0 (mod p)$ , clearly contradicting our assumption that $gcd(2,p) = 1$ . Whence, in conclusion, there are no solutions for this case.

(ii) Suppose the smaller factor is $1$ . Solving $n^2 + 2^n - 2^{k+1}n = 1$ might be quite a pain, and even disastrous. A simpler method here would be to consider when $n^2 + 2^n - 2^{k+1}n > 1$ (^) reducing it to sub-case (i) which we did above and reduce the amount of manual checking that we need to do. So, rewriting (^), we have:

$n^2 + 2^n - 2^{k+1}n = n^2 + 2^n - 2^{\frac{n+1}{2}} = n^2 + \sqrt{2^n}(\sqrt{2^n} + n\sqrt{2}$

Opting for a looser bound, we can see that this expression would be $> 1$ once $\sqrt{2^n} + n\sqrt{2} > 0$ . We can rewrite this into a neater form as $2^n > 2n^2$ . Reasonably guessing, we can see that for $n = 7$ the inequality holds. Once plotting this on graph paper, we can remark that once these two curves intersect, for values greater than the intersection point, the value of the exponential one would definitely be greater than that of the square. The interested reader might want to rigorously prove this using some elementary calculus. Putting all this together, these imply that we only have to check for $n < 7$ . One readily gets that $n = 1$ is a solution. (We get $5 = 5^1$ )

Wait! We are not done yet. What happens if $p = 2$ . Well, then we would need $n^4 + 4^n = 2^j$ . Trivially this implies that the powers of $2$ in $n^4$ and $4^n$ needs to be the same, or in other words $n^4 = 4^n$ . Clearly, $n =2 ,4$ are the only solutions. And surely we get $p^ j = 2^5, 2^9$ respectively.

In conclusion, the final answer is $2^5 + 2^9 + 5$ which evaluates as 549 .

P.S. I'm sorry for the long solution, but I personally feel that it is more instructive going through one's thought processes and motivation.

Checking the small cases when $n = 1, 2, 3, 4$ and 5, we see that $4^n + n^4 = 5, 32, 145, 512$ and 1649 respectively. Of these, 145 and 1649 are not prime powers while the rest are, so three possible prime powers that can be written in the form $4^n + n^4$ are 5, 32 and 512. Now assume $n > 5$ .

Case 1. $n$ is even. $n^4 + 4^n$ is clearly even, so if it is a prime power, it must be a power of 2. But for $n > 4$ , we have $4^n > n^4$ (this can be easily checked using induction). So $4^n < 4^n + n^4 < 2*4^n$ , so $2^(2n) < 4^n + n^4 < 2^{2n+1}$ . This means $4^n + n^4$ is not a power of 2, so it cannot be a prime power for all even $n > 5$ .

Case 2. $n$ is odd. If $n$ is odd, then $n = 2k+1$ for some integer $k > 2$ . Then

$\begin{aligned} n^4 + 4^n &=n^4 + n^2(2^{n+1}) + 2^{2n} - n^2(2^{n+1}) \\ &= (n^2 + 2^{2k+1})^2 - n^2(2^{k+1})^2 \\ &=(n^2+2^{2k+1}-n2^{k+1})(n^2+2^{2k+1}+n2^{k+1})\\ \end{aligned}$

Therefore, if $4^n + n^4$ is a power of a prime $p$ , then $p$ is odd (since $4^n + n^4$ is odd for all odd $n$ ) and both factors must be a multiple of $p$ (since they are not 1). Their difference will also be a multiple of $p$ , so we know that p divides $n*2^{k+2}$ . But $p$ is odd, so $p$ divides $n$ . Now, since $p$ divides both $n$ as well as the first factor $n^2 - n*2^{k+1} + 2^{2k+1}$ , then $p$ must divide $2^{2k+1}$ . But $p$ is odd, so this is not possible. Therefore, there is no such prime $p$ and $4^n + n^4$ is not a power of a prime for all odd $n > 5$ .

Therefore, the only prime powers that can be written in the form $4^n + n^4$ are 5, 32 and 512. Our answer is thus 5 + 32 + 512 = 549.

We have 2 cases: Case 1: $n\leq 4$ $n = 1$ we get 5, which is $5^{1}$ . For $n = 2$ we get $32 = 2^{5}$ . For $n = 3$ we get 145, which isn't a perfect prime power. $n = 4$ we get $2^{9}$ .

Case 2 : $n \geq 5$ We split this into 2 cases, depending on the parity of $n$ . i) n is even We claim that n is a power of 2. If $n \neq 2^{k}$ for some $k$ Let $n = 2a$ Then $2^{4}[a^{4} + 2^{4a-4}] = p^{r}$ for some prime p and $n\in \mathbb{N}$ Note that $p = 2$ Dividing both sides by 16(note that this is always possible) $a^{4} + 2^{4a-4} = 2^{r-4}$ And we conclude that a is even. Since this process can't go to infinity, we get a is a power of 2. It just remains to note that if $n = 2^{k}$ Then $2^{4k} + 2^{2^{k+1}}$ is never a power of 2 when k is greater than 2 (since n is at least 5) by factorization since one of them is one more than a power of 2.

ii) n is odd Then $4^{n} + n^{4} = (n^{2} + 2^{n} + 2^{\frac{n+1}{2}})(n^{2} + 2^{n} - 2^{\frac{n+1}{2}})$ Note that the first factor is greater than the second. And also note that 3 times the second term is always less than the first(which can be proven by simple inequality) and thus they must not be both powers of a prime. And thus,their product is not a power of a prime.

[Latex edits - Calvin]

Let's split up the problem into two cases. Case 1 , n is even: We know that $4^{n} + n^4$ is even. Which means that it has to be a prime power of two. In other words, there exists a positive integer k such that $2^{k} = 4^{n} + n^4$ In order for this to happen, $4^{n} = n^4$ Solving this equation we get two possible solutions, $n = 2, 4$ Case 2 , n is odd: Let $x = 2^{(n-1)/2}$ Because n is odd, we can rewrite $4^{n} + n^4$ as $n^4 + 4x^{2}$ Which allows us to factor it as $(n^{2}+2x^{2}-2nx)(n^{2}+2x^{2}+2nx)$ This is a pretty useful factorization. You should probably store it in the back of your head if you haven't already. If the whole expression was a prime power, the GCD of the two factors must be a prime power as well. In addition, since the GCD of the two also divides their difference, 4nx must be a prime power as well. If 4nx is a prime power, it must be a prime power of two. However, we established that n is odd, which means there is only one possibility: $n=1$ By a simple check we see that this works. $$ Combining our results : We see that the only three values of n that work are 1,2, and 4. Plugging in and summing, we get that $5+32+512 = \boxed{549}$

Suppose that $n=2m$ is even and that $N = n^4 + 4^n$ is a prime power. Since $N$ is even we must have $N = 2^k$ for some $k \ge 2n$ , so that $n^4 \; = \; 2^k - 2^{2n} \; = \; 2^{2n}\big(2^{k-2n} - 1\big)$ Hence $n = 2^mx$ where $x$ is an odd integer with $x^4 = 2^{k-2n}-1$ . Since $x^4 \equiv 1$ modulo $4$ we deduce that $2^{k-2n}-1 \equiv 1$ modulo $4$ , and hence $k-2n=1$ . Thus we deduce that $n^4 = 2^{2n}$ , and hence $n^2 = 2^n$ . It is easy to show by induction that $2^n > n^2$ for all $n \ge 5$ , so we deduce that either $n=2$ , with $N=32$ , or else $n=4$ , with $N=512$ .

If $n=2m+1$ is odd and $N=n^4 + 4^n$ is a prime power, then since $N$ is odd it must be an power of an odd prime $p$ . Then $\begin{array}{rcl} N & = & n^4 + 4^n \; = \; (n^2 + 2^n)^2 - 2^{n+1}n^2 \\ & = & (n^2 - 2^{m+1}n + 2^{2m+1})(n^2 + 2^{m+1}n + 2^{2m+1}) \\ & = & \big[(n-2^m)^2 + 2^{2m}\big]\big[(n+2^m)^2 + 2^{2m}\big] \end{array}$ We can find integers $0 \le i < j$ such that $(n-2^m)^2 + 2^{2m} \; = \; p^i \qquad (n+2^m)^2 + 2^{2m} \; = \; p^j$ If $i \ge 1$ then $p$ divides both $(n-2^m)^2 + 2^{2m}$ and $(n+2^m)^2 + 2^{2m}$ , and so $p$ divides the difference $2^{m+2}n$ of these two numbers. Thus $p$ divides $n$ . But that implies that $p$ divides $N-n^4 = 4^n$ , which is impossible. Thus we deduce that $i=0$ , so that $(n-2^m)^2 + 2^{2m} = 1$ . This implies that $m=0$ and $n=1$ , so that $N=5$ .

Thus the desired answer is $32 + 512 + 5 = 549$ .

I started by simply substituting positive integer values of n.

n = 1: $4^{1}+1^{4}=5$ , which is a prime power: $5^{1}$

n = 2: $4^{2}+2^{4}=32$ , which is a prime power: $2^{5}$

n = 3: $4^{3}+3^{4}=145$ , not a prime power since $145=(5)(29)$

n = 4: $4^{4}+4^{4}=512$ , which is a prime power: $2^{9}$

n = 5: $4^{5}+5^{4}=1649$ , not a prime power since $1649=(17)(97)$

I didn't test any cases beyond that, knowing that my answer must be less than 1000 and all other results will be greater than 1649.

$5+32+512=549$

Substitute n=1,2,4,(I only try those three digits because due to a^n+n^a I just need to test the factors of a which is enough)We get that 5=5^1, 32=2^5, 512=2^9. And then add them together which gives 549.Thank you.

Listed all values of 4^i+i^4 For i=1 : 5 For i=2 : 32 For i=3 : 145 For i=4 : 512 For i=5 : 1649 For i=6 : 5392 For i=7 : 18785 For i=8 : 69632 For i=9 : 268705 For i=10 : 1058576 For i=11 : 4208945 For i=12 : 16797952 For i=13 : 67137425 For i=14 : 268473872 For i=15 : 1073792449 For i=16 : 4295032832 For i=17 : 17179952705 For i=18 : 68719581712 For i=19 : 274878037265 For i=20 : 1099511787776

Checked for prime factors of each item using http://www.mathsisfun.com/numbers/prime-factorization-tool.html Tool is limited up to 4294967296 only.

And out of the all the values, only 5, 32, and 512 could be represented in p^k form. Their sum is 549.

Firstly, assume $n>1$ . From Sophie Germain Identity, $n^4+4^n=(n^2+n\cdot2^{k+1}+2^{2k+1})(n^2-n\cdot2^{k+1}+2^{2k+1})$ Consider it is $p^k$ then, $p|n^2+n\cdot2^{k+1}+2^{2k+1},n^2-n\cdot2^{k+1}+2^{2k+1}\Longrightarrow p|n\cdot2^{k+2}$ If $p|n,p|n^4+4^n\implies p|2$ . Else, $p|2$ . Either way, we have that $n=2^k$ . Now, obviously we have $2^{2^{k+1}}+2^{4k}=2^m$ for some $m\in\mathbb N$ To make this happen we must have $2^{k+1}=4k$ otherwise, we would have an odd factor greater than $1$ on the left side. Thus, $2^{k-1}=k\implies k=1,2$ So, $n=1,2,4$ and then the sum is $5+32+512=\boxed{549}$