# Thread: if ((2^n) -1 ) is prime, prove n is prime ?! >.<

1. ## if ((2^n) -1 ) is prime, prove n is prime ?! >.<

Ok heres the question! :

if (2^n) -1 ) is prime, prove n is prime

i have attempted this question. However, i do not knw if i have started it off right, below is what i have done so far:

Suppose n is COMPOSITE, and let n = rs, where r, s >1

hence, ((2^n) -1 ) becomes if ((2^rs) -1 )

then
((2^rs) -1 )=((2^s) -1 ) (1 + (2^s) +(2^2s)+(2^3s)+...+(2^s(r-1)) )

so ((2^s) - 1) | ((2^n) -1 )

since ((2^n) -1 ) is prime .....

then after this i dont know what to do, if possible could someone please tell me how to continue please or a hint or something.

thankyou very much in advance, CoCo_RoAcH ^^

2. Use the fact that $x^m-1= (x- 1)(x^{m-1}+ x^{m-2}+ \cdot\cdot\cdot+ x^2+ x+ 1)$

3. Remember that $2^n - 1$ is prime which means its divisors are either 1 or itself.

Since $2^s - 1 \Big| 2^n - 1$.

This means either $2^s - 1 = 1$ or $2^s - 1 = 2^n - 1$.

Either way, what can you say about $a$ and $b$ ?

4. Originally Posted by o_O
Remember that $2^n - 1$ is prime which means its divisors are either 1 or itself.

Since $2^s - 1 \Big| 2^n - 1$.

This means either $2^s - 1 = 1$ or $2^s - 1 = 2^n - 1$.

Either way, what can you say about $a$ and $b$ ?

ok, im assuming when you mention a and b they are like my r and s.

so then s = 1 or s = n, and r = 1 or r = n aswell

hence, n = nx 1 or 1 x n

therefore n is prime, when 2^n -1 is prime.

Thankyou for the help! greatly appreciated! ^^