1
$\begingroup$

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 .

$\endgroup$
  • $\begingroup$ 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}$. $\endgroup$ – André Nicolas Nov 27 '11 at 20:01
  • $\begingroup$ @AndréNicolas,you have small typo...it should be $q^{p-1} \equiv 1 \pmod p $ $\endgroup$ – Peđa Terzić Nov 28 '11 at 7:07
  • $\begingroup$ 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}$. $\endgroup$ – André Nicolas Nov 28 '11 at 7:24
1
$\begingroup$

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.

$\endgroup$

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.