1. ## Prime Number Proof

How should i start off this proof?

If (2^n -1) is prime, prove that n is prime.

So far I've only got 2 things written down:

1. If 2^n -1 is prime then using divisor notation. 1|(2^n -1) and (2^n -1)|(2^n -1). But I dont think this helps.

2. To prove this we can prove gcd((2^n -1),n) = 1 (i.e relatively prime)

Other than that not much idea at all.

Any suggestions would be greatly appreciated.

2. Let: $\displaystyle n = ab$

We're going to use the fact that: $\displaystyle x^{y} - 1 = \left(x - 1\right)\left(x^{y-1} + x^{y-2} + \cdots + x + 1\right)$

So we then have: $\displaystyle 2^{n} - 1 = 2^{ab} - 1 = \left(2^a\right)^b - 1 = \left(2^a - 1\right)\left( \left(2^a\right)^{b-1} + \left(2^a\right)^{b-2} + \cdots + 2^a + 1\right)$

This means that: $\displaystyle \left( 2^a - 1\right) \Big| \left(2^n - 1\right)$

But $\displaystyle 2^n - 1$ is prime. So what can you conclude about its divisor $\displaystyle 2^a - 1$ ?

3. Originally Posted by o_O
So what can you conclude about its divisor $\displaystyle 2^a - 1$ ?
Is it that:

Since (2^n -1) is prime anything that divides it must be (2^n -1) or 1 itself so (2^a -1)|(2^n -1) implies that

(2^a -1) = (2^n -1) or (2^a -1)=1

=> a = n or => a = 1

so since n=ab then b = 1 or b = n.

Therfore if (2^n -1) is prime then n=ab=n x 1 so n is also prime.