1

Let $n$ be a positive integer. Show that if $2^n -1$ is a prime number, then $n$ is a prime number.

This is how I started to tackle this question:

Assume that instead of $n$ being a prime number, it is a composite number. Let $n=ab$ where a and b are factors. Thus, we have $2^n-1 = 2^a*2^b-1$ When we try to factor out the $2^b$ out, we will get:

$2^b * (2^a-1/2^b)$ Since $2^b$ is one of the factors, this is a contradiction. Therefore n must be a prime number.

I know that the $-1/2^b$ is not correct as it makes one of the factors a fraction. How do I change this a little bit to make sure that my proof is right?

user2574069
  • 51
  • Not correct. Think about how $a^n-b^n$ factors. –  Apr 21 '14 at 22:27
  • 1
    $n=ab \Rightarrow 2^n-1=(2^a)^b-1\neq 2^a\cdot 2^b - 1$ – Ángel Mario Gallegos Apr 21 '14 at 22:28
  • Infact one can prove a more general result: If $x^n-1$ is prime, then $x=2$ and $n$ is a prime. I am writing a proof – Hesky Cee Apr 21 '14 at 22:35
  • Above answer by @user134824 is correct but I just want to add (as i pointed out in my comment) that if $x^p-1$ is prime, then $x=2$ and $p$ is prime. However, it is not true that $2^p-1$ is prime because $p$ is prime. – Hesky Cee Apr 21 '14 at 22:53

2 Answers2

3

It's probably easier to prove the contrapositive: if $n$ is composite then $2^n - 1$ is composite. So suppose $n$ is composite, i.e. $n=ab$ with $a$ and $b$ integers greater than $1$. Using the factorization $$ y^a - 1 = (y - 1)(y^{a-1} + y^{a-2} + \cdots + y + 1) $$ and writing $2^n - 1 = 2^{ab} - 1 = (2^b)^a - 1$, we have $$ 2^n - 1 = (2^b - 1)(2^{b(a-1)} + 2^{b(a-2)} + \cdots + 2^b + 1). $$ Specifically, I let $y=2^b$ in the factorization I gave earlier. Then $2^b-1$ divides $2^n-1$ but $2^b - 1$ is strictly less than $2^n-1$, as $b<n$. So $2^n-1$ is composite.

user134824
  • 12,212
0

Difference of powers... $(2^a-1), (2^b-1) | 2^{ab}-1$

Sandeep Silwal
  • 8,135