2
$\begingroup$

Dear all,

When working with a group theory problem, I come up with the equation:

$$p^x-1=2^y,$$ where $p$ is a prime and $x,y$ are positive integers. I would like to show that this equation has infinitely many solutions $(p,x,y)$ ($p$ is also a variable!) but not sure if this is correct. So my question is:

Is it correct? If yes, how do we prove it?

I have another question:

Are there infinitely many primes of the form $a2^n+1$, where $a$ is a fixed number? For example, just take $a=3$.

Improve this question
$\endgroup$
7
  • $\begingroup$ For fixed $x=1$ the answer is not known. I'm not optimistic about a firm answer for your more general version. $\endgroup$
    – Will Jagy
    Commented Apr 2, 2013 at 3:10
  • 7
    $\begingroup$ From Catalan's conjecture (proved by Mihailescu) it follows that there are no solutions with $x \ne 1$ except $p=3,x=2,y=3$. As Will says, the case $x=1$ is the open question of the existence of infinitely many primes of the form $2^{2^k}+1$. $\endgroup$
    – Felipe Voloch
    Commented Apr 2, 2013 at 3:16
  • 3
    $\begingroup$ I should add that the general expectation is that there are only finitely many solutions. $\endgroup$
    – Felipe Voloch
    Commented Apr 2, 2013 at 3:19
  • 2
    $\begingroup$ The equation $p^x-1=3^y$ forces $p$ to be odd, so you're really looking at $2^x-3^y=1$. So again Catalan's conjecture/Mihailescu's theorem says there are no solutions (and similarly for any odd prime in place of $3$). $\endgroup$
    – Greg Martin
    Commented Apr 2, 2013 at 5:37
  • 1
    $\begingroup$ Greg means it forces $p$ to be even. I think $2^x-3^y=1$ was dealt with by Gersonides, long before Catalan. $\endgroup$
    – Gerry Myerson
    Commented Apr 2, 2013 at 11:16

1 Answer 1

Reset to default
3
$\begingroup$

I only answer the (newly) added question (the others being adressed in comments):

Are there infinitely many primes of the form $a2^n + 1$, where $a$ is a fixed number?

Certainly not for each $a$. More precisely, Sierpiński (1060) showed that there exist infinitely many odd $a$ such that all numbers in the set $$ \lbrace a2^n +1 \colon n \in \mathbb{N} \rbrace $$ are composite.

Such an $a$ is called a Sierpiński Number; an explict example is $78557$. Chances are this is the smallest example, and there is some ongoing computing effort to show this. See the link I gave above for further details.

For certain other $a$ there are likely infinitely many, but this is never known. The point is that the most naive heuristic would be to say that the probability of $a2^n+1$ to be prime is proportional to $1/n$ (more precisely $1/\log (a2^n +1)$ by the Prime Number Theorem) and the series over $1/n$ being divergent one expects infinitely many, just like for Mersenne Primes.

However, and necessarily in view of what I said above, there can be problems with this heuristic: Depending on the $a$ there can be 'local' restrictions (that is one finds congruences that impede the number of this form to be prime, see again the site above). Or/and, as in the Fermat case, there is a general factorization that reduces the range of the admissible exponents so much that the relevant series will converge and one thus expects at most finitely many.

One more related key-word: Primes of the form $a2^n + 1$ for $a$ odd not fixed, but $2^n \gt a$ (to avoid trivializing the condition) are called Proth primes.

Following the links on the two pages I gave you will find some more related notions and additional information.

Improve this answer
$\endgroup$
9
  • $\begingroup$ I do not want to edit for this (right away), but the 'just like for Mersenne primes' is not quite precise, as in the the Mersenne case one also has a restriction for the $n$ (it has to be prime) from a general factorization. Yet the restriction is sufficiently weak that the series over the reciprocals of the 'admissible' exponents still diverges. Moreover, some restriction (excluding certain residue classes for teh expoenent) will typically be present; yet again it will be/can be only weak so that the series over the 'admissible' ones stays divergent. $\endgroup$
    – user9072
    Commented Apr 2, 2013 at 11:42
  • $\begingroup$ It might also be worth noting that there are even prime Sierpiński numbers, such as 271129. Also the year is (of course) 1960 not 1060. $\endgroup$
    – user9072
    Commented Apr 2, 2013 at 11:50
  • $\begingroup$ Thank you, quid! That is very interesting. Now I wonder if there is a fixed number $a$ and a fixed prime $p$ such that the set $\{{ap^n+1\}}$ consists of infinitely many prime powers. Based on what you have said, I feel that this question is also open. $\endgroup$
    – Uep
    Commented Apr 2, 2013 at 13:15
  • 1
    $\begingroup$ @Noam D. Elkies: this seems close to the original proof; the paper is a page.and a half. Specifically, what is shown is that each a congruent 1 mod $(2^{32}-1)641$ and -1 mod the other (than 641) proper divisor of F_5 is an admissible choice. And, this is done via always finding a divior from the list you give. $\endgroup$
    – user9072
    Commented Apr 2, 2013 at 16:15
  • 1
    $\begingroup$ In particular, the presumably smallest mentioned above is not from the original paper but was found by Selfridge. $\endgroup$
    – user9072
    Commented Apr 2, 2013 at 16:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .