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

• Mar 18th 2009, 01:33 AM
CoCo_RoAcH
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 ^^
• Mar 18th 2009, 04:52 AM
HallsofIvy
Use the fact that $x^m-1= (x- 1)(x^{m-1}+ x^{m-2}+ \cdot\cdot\cdot+ x^2+ x+ 1)$
• Mar 18th 2009, 06:10 AM
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$ ?
• Mar 18th 2009, 01:47 PM
CoCo_RoAcH
Quote:

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! ^^