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) … (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\)!