Factorize 2^n-1 (when n is composite)

How to Factorize 2^n-1

If n is composite, we may write n=ab where a,b>1.


\begin{aligned}    2^n-1&=2^{ab}-1\\    &=(2^a-1)(1+2^a+2^{2a}+2^{3a}+\dots+2^{(b-1)a}).    \end{aligned}

The key point is that both factors are greater than 1.


If a=2, b=5, we can see that 2^{10}-1=1023=(2^2-1)(1+2^2+2^4+2^6+2^8).

How to Remember this Result

The hard part is remembering this identity: \boxed{2^{ab}-1=(2^a-1)(1+2^a+2^{2a}+2^{3a}+\dots+2^{(b-1)a})}. It is essentially a “telescoping sum”, and you can prove it by expanding the right hand side and cancelling all like terms.

We can also view it as a Geometric Series as follows: \dfrac{1((2^a)^b-1)}{2^a-1} is the sum of a Geometric Progression with first term 1, and common ratio 2^a, for a total of b terms. That is,

\dfrac{1((2^a)^b-1)}{2^a-1}=1+2^a+2^{2a}+\dots+2^{(b-1)a}. Multiplying both sides by 2^a-1 gives the boxed result.


Primes of the form 2^n-1 are known as Mersenne Primes. Using the result above, we can show that if 2^n-1 is a prime, then n is a prime. (We prove the contrapositive: If n is composite, then we show that 2^n-1 is also composite.)