Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
4  
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
5  
The only candidates are $k=2^n$, for the same reason as the Fermat numbers. –  André Nicolas Jul 2 '12 at 16:54
5  
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 1

up vote 2 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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