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$ .

Then,

$\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.

Example

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.

Applications

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.)