Modular restrictions on Mersenne divisors

By Chris Caldwell

On this page we prove the following theorem (which we use on our page about Mersenne primes and 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 = 2kq.  This gives

2^(p-1)/2 = 2^qk ≡ 1^k ≡ 1 (mod p)

so 2 is a quadratic residue mod p and it follows p ≡ +/-1 (mod 8), which completes the proof.

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