# Modular restrictions on Mersenne divisors

On this page we prove the following theorem
(which we use on our page about Mersenne
primesand the historical note "the
Largest Known Prime by Year"). Fermat discovered and use the first
part of this theorem (*p* ≡ 1 modulo *q*) and Euler discovered
the second.

**Theorem.**- Let
*p*and*q*be odd primes. If*p*divides M_{q}, then*p*≡ 1 (mod*q*) and*p*≡ +/-1 (mod 8).

Below we give a proof and an example.

**Proof.**If

*p*divides M_{q}, then 2^{q}≡ 1 (mod*p*) and the order of 2 (mod*p*) divides the prime*q*, so it must be*q*. By Fermat's Little Theorem the order of 2 also divides*p*-1, so*p*-1 = 2*kq*. This gives2

so 2 is a quadratic residue mod^{(p-1)/2}= 2^{qk}≡ 1^{k}≡ 1 (mod*p*)*p*and it follows*p*≡ +/-1 (mod 8), which completes the proof.

**Example:** Suppose *p* divides M_{31},
then the two parts of the theorem together show *p* ≡ 1 or 63 (mod
248). By 1772 Euler had used this to show M_{31} was prime.