Theorem. If 2^p - 1 is prime, then p is prime.

Proof. By contradiction.
Suppose p is not prime.
Then p = rs where 1 < r<=s < p.
Thus, 2^p - 1 = 2^rs - 1 = (2^r - 1) (2^{rs - r} + 2^rs-2r + ... + 2^r + 1) Since neither of these factors is 1 or 2^p - 1, 2^p -1 is not prime, a contradiction.

Theorem. Let p and q be odd primes. If p divides 2^q - 1, then p = 1 (mod q) and p = +/-1 (mod 8).

To test whether or not a Mersenne number 2 ^q - 1 is prime, we start with various small primes r = 1 (mod q) and r = +/-1 (mod 8) and check to see if r divides 2 ^q - 1. If none of these small r divides 2 ^q - 1, then we invoke the Lucas-Lehmer test.