4
$\begingroup$

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.

$\endgroup$

marked as duplicate by Bill Dubuque number-theory Jun 26 '17 at 13:40

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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

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.

$\endgroup$
  • $\begingroup$ I love this. Is there another proof or approach to this problem? $\endgroup$ – Imago Jan 3 '16 at 11:22
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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