# How to prove this property of Mersenne number factors?

Let us denote a prime factor of Mersenne number as $q$ . How to prove following :

$(M_p\equiv0\pmod q \land q\equiv 1 \pmod 8) \Rightarrow q\equiv 1 \pmod {4\cdot p}$

There is a proof that any prime $q$ that divides $2^p − 1$ must be $1$ plus a multiple of $2p$ but I think that is possible to prove this stricter condition. I guess that one should use Fermat's Little Theorem as starting point for this proof .

• By Fermat's Theorem, $q\equiv 1 \pmod{p}$. If further we ask that $q\equiv 1\pmod 8$, then $q\equiv 1 \pmod {8p}$. – André Nicolas Nov 27 '11 at 20:01
• @AndréNicolas,you have small typo...it should be $q^{p-1} \equiv 1 \pmod p$ – Peđa Terzić Nov 28 '11 at 7:07
• It is true that $q^{p-1}\equiv 1 \pmod p$. But I do mean $q\equiv 1 \pmod {p}$. Since $q$ divides $2^p-1$, we know that $2^p\equiv 1 \pmod q$. By Fermat's theorem, $2^{q-1}\equiv 1 \pmod{q}$. Since the order of $2$ modulo $q$ is not $1$, it follows that this order is $p$, and therefore $p$ divides $q-1$. Or in other words, $q \equiv 1 \pmod{p}$. – André Nicolas Nov 28 '11 at 7:24

## 1 Answer

If $x\equiv a\pmod{m}$ and $x\equiv b\pmod{n}$, then $x$ is uniquely defined modulo $\frac{mn}{\gcd(m,n)}$. The proof is that we also have $x\equiv a\pmod{\frac{m}{\gcd(m,n)}}$ and $x\equiv b\;(n)$. Now $\frac{m}{\gcd(m,n)}$ and $n$ are two coprime moduli. The Chinese Remainder Theorem implies a unique solution for $x$ modulo the product of the moduli.

Given that $q\equiv1\;\pmod{8}$ and the fact you cite that $q\equiv1\pmod{2p}$, then since $p$ is coprime to $2$, it must be that $q\equiv1\pmod{8p}$, since $8p = \frac{8\cdot2p}{\gcd(8,2p)}$. This is even stronger than what you have proposed.