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

Advertisements

About mathtuition88

http://mathtuition88.com
This entry was posted in maths tuition and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.