A very nice factorization of numbers $2^{2n} -1$:

112 Views Asked by At

Mersenne primes and factorization of numbers of the form $2^n -1$ are my object of interest currently. I stumbled into a neat pattern.

All numbers of the form $2^{2n} -1$ where $n \in \mathbb{N}$ have a simple, quick factorization technique. Namely, numbers of the form $2^{2n} - 1$ factor into $(2^n - 1) \cdot (2^n + 1).$

For example: Take $2^6 - 1 = 63$ which can be represented as $2^{2 \cdot 3} - 1 = 63$. The factorization of 63 is $(2^3 - 1)\cdot(2^3 + 1) = 7 \cdot 9 = 63.$

Another Example: Take $2^{12} -1 = 4095. $ By this rule, $2^{12} - 1 = (2^6 -1) \cdot (2^6 + 1) = 63 \cdot 65$.

I'm not entirely sure if this is an existing mathematical fact that is well-known but I have thought this worth a share.

1

There are 1 best solutions below

1
On BEST ANSWER

$$\begin{align}2^{ab} - 1 &= (2^a)^b - 1 \\&=(2^a-1)\left(\sum\limits_{i=0}^{b-1}2^{ai}\right),\end{align}$$

because of the factorization of $x^n-y^n$; it's well-known. In fact, the factorization you're using is just the difference of squares $a^2-b^2$ with $a=2^n$ and $b=1$.

That's why Mersenne primes are of the form $2^p-1$ for prime $p$ and not other general exponents.