Let d be a prime divisor of M_{Mp}. We know that

A factor d will always be of the form **2*k*m + 1** where m = M(p) = 2^{p} - 1 is a Mersenne prime.

Note that, since m == 1 (mod 3), factors of M(m) cannot have k == 1 (mod 3),

since 2*k*m + 1 == 0 (mod 3) in that case.

Chris Nash pointed out on the Mersenne list (1999 Sep 22) that, for odd Mersenne exponents, k must be 0 or 1 mod 4,

since, otherwise, 2 is not a quadratic residue of the supposed factor.

The combination of the prior two restrictions limits k to 0, 5, 8, and 9 modulo 12.

The program uses a sieving process. We start with a long list of ks and we reject all those ks for which the corresponding factor d is divisible by a prime q = 3, 5, 7, 11, ...

up to some suitable limit.

For each k that survives we compute d and see if it divides into M_{Mp}.

All calculations are done modulo d.

© MoreWare 2012