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

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.

• Definitely well-known. More generally, if $m\mid n$ then $2^m-1$ is a factor of $2^n-1.$ – Thomas Andrews Jan 17 at 20:02
• Diffence of two squares ? – Donald Splutterwit Jan 17 at 20:03
• It is $a^2-b^2=(a-b)(a+b)$ from highschool, with $a=2^n$ and $b=1$. We called it "third binomial formula". – Dietrich Burde Jan 17 at 20:03
• it comes about due to the iteration of 2x+1 having remainder a mersenne. – user645636 Jan 17 at 20:05
• see if all mersennes were prime, they'd form a cunningham chain of first kind. which is ironic since there are only two places in such a chain that a mersenne exponent could be. – user645636 Jan 17 at 20:20

\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.
• you can also think of this as $2x+1$ iterated from $x=M_n$ doing so $n$ times Iterates the remainder 1 to $M_n$ so you get the factorization above. – user645636 Jan 17 at 23:40