# Sum of powers and prime numbers

I'm not able to find solutions of the following equation: $$2^k+3^k=p$$ where $p$ is a prime number and $k \in N$. It's easy to show that we have a solution when $k=1,2,4$. Is it possible to find any other solutions or the only possible values of $k$ are the previous ones? Thank you in advance.

• A small remark : if $k$ is a solution, then all odd multiples of $k$ (bigger than $k$) are not solution. Indeed, if $n > 1$ is odd, since $2^k \equiv -3^k \mod p$, then $2^{nk} \equiv -3^{nk} \mod p$. We deduce $2^{nk} + 3^{nk}$ is a multiple of $p$, so it can't be prime (because $2^{nk} + 3^{nk} > 2^k + 3^k = p$). And you're reduced to checking for $k$ a power of $2$. – Joel Cohen Jul 2 '12 at 16:50
• The only candidates are $k=2^n$, for the same reason as the Fermat numbers. – André Nicolas Jul 2 '12 at 16:54
• A comment on the Online Encyclopedia of Integer Sequences says "Next term, if it exists, is > 10^125074". oeis.org/A082101 – Tom Cooney Jul 2 '12 at 17:02

## 1 Answer

We begin with two simplifying observations:

Observation 1: If $m=2^k+3^k$ where $k=ab$ where $a$ is odd, then $m$ is divisible by $2^b+3^b$.

Proof: Let $s=2^b$ and $t=3^b$. We have $2^{ab}+3^{ab}=s^a+t^a=(s+t)(s^{a-1}-s^{a-2} \cdot t+\cdots-s \cdot t^{a-2}+t^{a-1}).$ (See e.g. MathWorld.) (QED)

[NB. A comment on Sloane's A082101 asserts that it must be divisible by $5$, which is incorrect (e.g. $2^{10}+3^{10}=60073$).]

Hence, for $m$ to be prime, we must have that $k=0$ or $k$ is a power of $2$. So we will switch to studying $n=2^{2^k}+3^{2^k}$.

Observation 2: If $n=2^{2^k}+3^{2^k}$, and $p$ is an odd prime divisor of $n$, then $p=2^{k+1}q+1$ for some $q \in \mathbb{Z}^+$.

Proof: Let $x$ be a primitive root modulo $p$. Define $t,s,r$ to be the minimum positive integers such that $2 \equiv x^t \pmod p$, $r \equiv x^s \pmod p$ and $-1 \equiv x^r \pmod p$.

We know $x^{2r} \equiv 1 \pmod p$. Hence $|\mathbb{Z}_p^*|=\varphi(p)=p-1$ divides $2r$ (since $x$ is a primitive root). Hence $r=c \cdot (p-1)/2$ for some $c \in \mathbb{Z}^+$. We know $r$ divides $|\mathbb{Z}_p^*|=\varphi(p)=p-1$ by Lagrange's Theorem. Hence $c \in \{1,2\}$. We conclude $c=1$ (as otherwise, $r=p-1$ and $x^r \equiv -1 \pmod p$ contradicts Fermat's Little Theorem). Hence $r=(p-1)/2$.

Since $p$ divides $n$, we know $x^{2^k t} \equiv x^{r+2^k s} \pmod p$, or equivalently $2^k t \equiv r+2^k s \pmod {p-1}$. We rearrange this to give $2^k (t-s) \equiv r \pmod {p-1}$. Importantly, $2^k (t-s) \not\equiv 0 \pmod {p-1}$. Thus, if $2^w$ is the largest power of $2$ dividing $p-1$, then $2^k (t-s) \not\equiv 0 \pmod {2^w}$, since $2^w$ does not divide $r=(p-1)/2$. Hence $w \geq k+1$. (QED)

(Note similar observations can be shown for Fermat numbers.)

I used these observations to perform trial division, which came up with the following:

2^(2^1)+3^(2^1) is prime: 13
2^(2^2)+3^(2^2) is prime: 97
2^(2^3)+3^(2^3) has a proper divisor: 17
2^(2^4)+3^(2^4) has a proper divisor: 3041
2^(2^5)+3^(2^5) has a proper divisor: 1153
2^(2^6)+3^(2^6) has a proper divisor: 769
2^(2^7)+3^(2^7) has a proper divisor: 257
2^(2^8)+3^(2^8) has a proper divisor: 72222721
2^(2^9)+3^(2^9) has a proper divisor: 4043777
2^(2^10)+3^(2^10) has a proper divisor: 2330249132033
2^(2^11)+3^(2^11) has a proper divisor: 625483777
2^(2^12)+3^(2^12) has a proper divisor: 286721
2^(2^13)+3^(2^13) has a proper divisor: 14496395542529
2^(2^14)+3^(2^14) has a proper divisor: 2752513
2^(2^15)+3^(2^15) has a proper divisor: 65537
2^(2^16)+3^(2^16) has a proper divisor: 319291393
2^(2^17)+3^(2^17) has a proper divisor: 54498164737
2^(2^18)+3^(2^18)=n does not satisfy 2^(n-1) = 1 (mod n) [Fermat's primality test.]
2^(2^19)+3^(2^19) has a proper divisor: 7340033
2^(2^20)+3^(2^20) has a proper divisor: 23068673
2^(2^21)+3^(2^21) has a proper divisor: 2878894768129
2^(2^22)+3^(2^22) has a proper divisor: 453236490241
2^(2^23)+3^(2^23) has a proper divisor: 106216554497
2^(2^24)+3^(2^24) has a proper divisor: 342456532993

2^(2^27)+3^(2^27) has a proper divisor: 488015659009


For $k=18$, my computer didn't easily find a divisor, so I ran a base $2$ Fermat primality test, which showed that $2^{(2^{18})}+3^{(2^{18})}$ is definitely not a prime. So now the smallest open case is $2^{(2^{25})}+3^{(2^{25})}$, which has 16009533 digits. If it were prime (and it almost certainly won't be), it would be the 4-th largest known (see "The Largest Known Primes--A Summary").

Heuristic: Assume, for the sake of argument, that the probability of a natural number $n$ being prime is independent and approximately $1/\ln n$ (which is vaguely justified by the prime number theorem). Then the expected number of primes of the form $2^{2^k}+3^{2^k}$ is $O(1)$.

Non-proof: The expected number of primes of the form $2^{2^k}+3^{2^k}$ is $\sum_{k \geq 0} \mathrm{Pr}[n=2^{2^k}+3^{2^k} \text{ is prime}] = \sum_{k \geq 0} 1/\ln n$. We observe that $n \geq e^{2^k}$, so $\sum_{k \geq 0} 1/\ln n \leq 1/2^k=2$. (QED)

If we start the sum at $k=25$, we can estimate the probability of another prime of the desired form existing at $5.96 \times 10^{-8}$.

Of course, the independence assumption is invalid (e.g. if $n$ is prime and $n \geq 3$ then $n+1$ is not prime). But this gives a feeling that it would be possible not to have any more primes of this form. (Similar heuristics are used to argue that there's probably no more Fermat primes.)

Answer: I think the only possible answer to your question will be "don't know, but probably not" for a long time (similar to Fermat Numbers).

(I also wish to acknowledge the use of Primeform (OpenPFGW), along with my own code, for the computations in this answer.)