20040328, 18:58  #1 
Mar 2004
3×167 Posts 
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^111 = 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? 
20040328, 19:47  #2  
"William"
May 2003
New Haven
3×787 Posts 
Quote:
For prime exponents, it's known that the factors must be (1 mod 8) or (7 mod 8). See, for example Will Edgington. 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 

20040328, 20:57  #3 
Mar 2004
3×167 Posts 
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. 
20040329, 02:31  #4  
Jun 2003
Russia, Novosibirsk
2·107 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Does n have the form (a^p+b^p)/(a+b) for p > 2?  carpetpool  carpetpool  1  20170130 13:36 
Special Form of Mersenne and Fermat Number Factors  michael  Math  31  20150904 05:57 
Factors with special form  RedGolpe  Factoring  5  20111103 18:38 
Missing factors at the 'Known Factors' page  MatWurS530113  PrimeNet  11  20090121 19:08 
Concordant Form  Citrix  Math  8  20060319 20:45 