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.

Definition. If prime p>2 does not divide a and
if there exists an integer b such that a = b² (mod p), then a is called a quadratic residue modulo p;
otherwise, it is a nonquadratic residue modulo p.

Legendre introduced the following notation:

(a/p) = +1 if a is a quadratic residue modulo p, -1 otherwise.
It is also convenient to define (a/p) = 0 when p divides a.

Euler proved the following congruence: (a/p) = a^(p-1)/2 (mod p) .

In particular, (2/p) = +1 when p = +/- 1 (mod 8), (2/p) = -1 when p = +/- 3 (mod 8).

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

Proof.
If p divides 2^q - 1, then 2^q = 1 (mod p) so the order of 2 (mod p) divides q.
Since q is prime, the order of 2 (mod p) must be q.
By Lagrange's Theorem, the order of 2 (mod p) divides p-1.
Thus, p = 1 (mod q).

Since, 2^q = 1 (mod p) , 2^q+1 = 2 (mod p) so (2 ^(q+1)/2)² = 2 (mod p). Thus, 2 is a quadratic residue mod p.
It follows from the consequence of Euler's congruence that p = +/-1 (mod 8).

A typical Mersenne prime search runs as follows. For some set of prime exponents Q, remove candidates q in Q by checking whether 2 ^q = 1 (mod r) for various small primes r = 1 (mod q) and r = +/-1 (mod 8). For the survivors, we then invoke the Lucas-Lehmer test.