# $n = 2^p - 1$ Prove that if n is prime then p must also be prime. [duplicate]

This question already has an answer here:

My first thought was to try a contradiction; So given n is prime assume p is not prime i.e $p = p_{1}^{\alpha1} .... p_{r}^{\alpha r}$. But i didnt know where to go from there.

## marked as duplicate by Bill Dubuque number-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Jun 26 '17 at 13:40

• Try to use that $a^k-b^k=(a-b)(a^{k-1}+...+b^{k-1})$ – mrprottolo Jan 3 '16 at 11:18

If $p = a\cdot b$ where $a \neq 1, b \neq 1$ then $n = 2^{ab} - 1 = (2^a)^b - 1 = (2^a-1)(2^{a(b-1)} + ...+ 1)$ is clearly composite.
Assume that $p$ is not a prime, and let $k$ be $p$'s smallest prime divisor.
We have $2^k-1|2^p-1$ and $2^k-1 > 1$, so $2^p-1$ cannot be a prime as desired.
If $1<x\le y$ then $2^x-1$ divides $2^{xy}-1$. Moreover $1<2^x-1<2^{xy-1}$, which is enough to conclude.