A fast factorization method for Mersenne numbers

Question

Given a prime number $p$ and a Mersenne number $M=2^p-1$:

1. Is it true for every prime factor $q$ of $M$ that $q\equiv1\pmod{p}$?

   For example, $p=29$ and $M=536870911=233\cdot1103\cdot2089$:

   • $ 233=29\cdot 8+1$

   • $1103=29\cdot38+1$

   • $2089=29\cdot72+1$

2. If yes, then is there a method which exploits this fact in order to factorize $M$ (or decide it is prime), which is faster than the fastest methods in use for numbers in general?

Answer 1

1. $q|(2^p-1)\Rightarrow 2^p\equiv 1\pmod q$. Therefore, the order of $2$ in the multiplicative group $\Bbb Z_q^*$ divides $p$ and, since $p$ is prime and $2\neq 1$, it's exactly $p$. By Lagrange's theorem, $p|(q-1)$, that is, $q\equiv 1\pmod p$.

2. I don't know about the fastest methods, but the top ten prime numbers are Mersenne numbers...

Remark: You can use weaker theorems than Lagrange's. Little Fermat's theorem, for example.

Answer 2

In general, every divisor of $\frac{x^p-1}{x-1}$ where $x \in \mathbb{Z}$ and $p$ prime is $\equiv 1 \pmod p$.