0
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ Definitely well-known. More generally, if $m\mid n$ then $2^m-1$ is a factor of $2^n-1.$ $\endgroup$ – Thomas Andrews Jan 17 at 20:02
  • 2
    $\begingroup$ Diffence of two squares ? $\endgroup$ – Donald Splutterwit Jan 17 at 20:03
  • 2
    $\begingroup$ 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". $\endgroup$ – Dietrich Burde Jan 17 at 20:03
  • $\begingroup$ it comes about due to the iteration of 2x+1 having remainder a mersenne. $\endgroup$ – user645636 Jan 17 at 20:05
  • $\begingroup$ 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. $\endgroup$ – user645636 Jan 17 at 20:20
1
$\begingroup$

$$\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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user645636 Jan 17 at 23:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.