# Factors of Mersenne Numbers

From ProofWiki

## Theorem

Let $p$ and $q$ be prime numbers such that $p$ is a divisor of the Mersenne number $M_q$.

Then both of these properties apply:

- $p \equiv 1 \pmod q$
- $p \equiv \pm 1 \pmod 8$

## Proof

Suppose $p \mathop \backslash M_q$.

Then $2^q \equiv 1 \pmod p$, and the order of $2 \pmod p$ divides $q$ from Integer to Power of Multiple of Order.

By Fermat's Little Theorem, the order of $2 \pmod p$ also divides $p-1$.

Hence we have $p - 1 = 2 k q$ and hence $p \equiv 1 \pmod q$.

We also have, from above:

- $2^{\left({p-1}\right)/2} \equiv 2 q k \equiv 1 \pmod p$

and so $2$ is a quadratic residue $\pmod p$.

Thus it follows from the Second Supplement to the Law of Quadratic Reciprocity that $p \equiv \pm 1 \pmod 8$.

$\blacksquare$

## Notes

Proof courtesy of The Prime Pages: Modular restrictions on Mersenne divisors.

This proof was originally provided by Fermat.