How to Factorize 2^n-1
If is composite, we may write where .
The key point is that both factors are greater than 1.
If , we can see that .
How to Remember this Result
The hard part is remembering this identity: . 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: is the sum of a Geometric Progression with first term 1, and common ratio , for a total of terms. That is,
. Multiplying both sides by gives the boxed result.
Primes of the form are known as Mersenne Primes. Using the result above, we can show that if is a prime, then is a prime. (We prove the contrapositive: If is composite, then we show that is also composite.)