On 2^n – 1

Picking up from my last blog post, where we observed 255 = 15 x 17,

$2^{n}-1 = (2^{\frac{n}{2}}+1)*(2^{\frac{n}{2}}-1)$
$= (2^{\frac{n}{2}}+1)*(2^{\frac{n}{4}}+1)*(2^{\frac{n}{4}}-1)$
$= (2^{\frac{n}{2}}+1)*(2^{\frac{n}{4}}+1)*(2^{\frac{n}{8}}+1)*(2^{\frac{n}{8}}-1)$

If $n=2^{k}$, where $k \in Z$

$= (2^{\frac{n}{2}}+1)*(2^{\frac{n}{4}}+1)*(2^{\frac{n}{8}}+1)*(2^{\frac{n}{16}}+1) \ldots (2+1)(2-1)$
$= \prod_{i=1}^k (2^{\frac{n}{2^i}}+1)$

This is incredibly cool!

So,
$2^4-1$ = 15 = 5 x 3
$2^8-1$ = 255 = 17 x 5 x 3
$2^{16}-1$ = 65535 = 257 x 17 x 5 x 3
$2^{32}-1$ = 4294967295 = 65537 x 257 x 17 x 5 x 3

It is fascinating to see the above results in binary:

       11
      101  x
   ------
     1111  =

       11
      101 x
    10001 x
 --------
 11111111 =

       11
      101 x
    10001 x
100000001 x
-----------
16 1's    =

Primes of the form $2^{n}-1$ are called Mersenne primes. Primes of the form $2^{2^{n}}+1$ are called Fermat primes. The numbers 3, 5, 17, 257 and 65537 are the only known Fermat primes!

That concludes my random rant. Have fun with $2^{n}-1$!