Factors of the Form 7 mod 8
 

It is possible to prove that if Mersenne number M_p is composite, then it has at least one factor of the form 7 mod 8. For example, M_11 = 2^11-1 = 23*89, and 23 = 8*2+7.

Does anyone have any statistics on what percentage of "large" factors (say 60+ or 61+ bit) that have been found are 7 mod 8?

[QUOTE=dominicanpapi82]It is possible to prove that if Mersenne number M_p is composite, then it has at least one factor of the form 7 mod 8.[/QUOTE]

For n>=3, M(n) = 2^n-1 = 8*2^(n-3)-1 = 7 mod 8, so the number itself is 7 mod 8.

For prime exponents, it's known that the factors must be (1 mod 8) or (7 mod 8). See, for example [URL=http://www.garlic.com/~wedgingt/mersenne.html]Will Edgington[/URL].

If the factors are ALL (1 mod 8), the product would be (1 mod 8), so there must be at least one factor that is (7 mod 8). In fact, there must be an odd number of factors that are (7 mod 8).

For the question about the number of factors that are 1 or 7 mod 8, are you only interested in composite Mersenne numbers with prime exponents? You can pull such information from Will Edgington's lowm.txt and factoredM.txt, but it would take some work to pull out only the prime exponents.

William

I am considering large factors of Mersenne numbers M(n), and I am only considering prime values of n.

As William showed above, an odd number of prime divisors of M(p) must be (7 mod 8). Hence at least one of its factors must be (7 mod 8). My hope is that MOST known large factors found through seiving methods like Prime95, which does not discriminate between potential factors which are (1 mod 8) or (7 mod 8), are actually (7 mod 8). If so, then if your goal is simply to prove compositeness by finding a factor, then it may be more beneficial to trial divide by potential factors which are (7 mod 8) once your potential factors become large.

By the way, I say "once your potential factors become large" because small primes are more likely than large primes to divide elements from a set of randomly distributed numbers. Although Mersenne numbers are not randomly distributed, there is no evidence which would make us believe that smaller primes are LESS likely to divide a Mersenne number than larger primes.

[QUOTE=dominicanpapi82]Does anyone have any statistics on what percentage of "large" factors (say 60+ or 61+ bit) that have been found are 7 mod 8?[/QUOTE]

It is about 44.4% for 7 mod 8 and 55.6% for 1 mod 8