Mersenne divisor

Mersenne primes have always been the most sought after primes ever since Euclid connected them to perfect numbers over two millennia ago. When searching for new Mersennes, you first look for small divisors (called Mersenne divisors), then apply the Lucas-Lehmer test. These divisors must have a very special form because Fermat and Euler proved:

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

(The proof is linked below.) Sometimes, just the fact that a number divides a Mersenne is enough to show it is prime:

Let p ≡ 3 (mod 4) be prime. 2p+1 is also prime if and only if 2p+1 divides Mp.

(The proof is also linked below.)

See Also: Mersennes, CunninghamProject

Related pages (outside of this work)

Printed from the PrimePages <> © Chris Caldwell.