Let $p$ be a prime number. Is there any $n$ such that $2^n-1=p^2$? In general is there any n such that $2^n-1=p^k$ for some integer $k$? If there isn't, Is there any proof for that?
$\begingroup$
$\endgroup$
3
-
4$\begingroup$ What is the connection to graph spectra? $\endgroup$– Douglas ZareCommented May 11, 2016 at 15:43
-
5$\begingroup$ en.wikipedia.org/wiki/Catalan%27s_conjecture $\endgroup$– Douglas ZareCommented May 11, 2016 at 15:46
-
3$\begingroup$ Since $p^{2} \equiv 1$ (mod $8$) for odd $p$, we can't have $2^{n} = p^{2}+1$, and more generally, $2^{n}= p^{k}+1$ gives that $k$ must be odd. Of course any Mersenne prime $p$ works with $k = 1$, so suppose $k > 1.$ However, it is easy to check that $\frac{p{k}+1}{p+1}$ is then odd, a contradiction. So the only solutions (to the second question) are when $p$ is a Mersenne prime and $k=1$. There are no solutions to the first question ( Obsolete by Douglas Zare's link to a more general answer). $\endgroup$– Geoff RobinsonCommented May 11, 2016 at 15:59
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
One can use elementary results to show that existence of such a $p$ is unlikely.
Note in general that squares are 0 or 1 mod 4, so something of the form $r^2+1$ being also of the form $2^n$ for integer $r$ means $n$ is $0$ or $1$. Thus $k$ cannot be even for there to be an integer $p$ and integers $n\gt 1$ and $k$ with $2^n -1 =p^k$ holding.
Thus if there is a solution, $p^k + 1$ and its factor $p+1$ must be powers of $2$ (since $k$ must be odd). Thus $\gcd(p+1,\frac{p^k +1}{p+1})$ is also a power of $2$. But this gcd is $\gcd(p+1,k)$, so divides $k$. So the gcd is 1. So one of the two factors must be $1$. Thus (excluding $p=0$) $k=1$, and the argument above did not depend on $p$ being prime. So all that is left are Mersenne numbers $p$, not many of which are prime.
Gerhard "Hoping This Is Not Homework" Paseman, 2016.05.11.
answered May 11, 2016 at 16:13
-
$\begingroup$ Apologies to Geoff Robinson, whose slightly more elementary argument I just noticed in the comments after typing this one. Gerhard "Should Use Parity More Often" Paseman, 2016.05.11. $\endgroup$ Commented May 11, 2016 at 16:15