mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Data

Reply
 
Thread Tools
Old 2004-03-28, 18:58   #1
JuanTutors
 
JuanTutors's Avatar
 
Mar 2004

3×167 Posts
Default 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?
JuanTutors is offline   Reply With Quote
Old 2004-03-28, 19:47   #2
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

3×787 Posts
Default

Quote:
Originally Posted by 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.
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 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
wblipp is offline   Reply With Quote
Old 2004-03-28, 20:57   #3
JuanTutors
 
JuanTutors's Avatar
 
Mar 2004

3×167 Posts
Default

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.
JuanTutors is offline   Reply With Quote
Old 2004-03-29, 02:31   #4
HiddenWarrior
 
HiddenWarrior's Avatar
 
Jun 2003
Russia, Novosibirsk

2·107 Posts
Default

Quote:
Originally Posted by 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?
It is about 44.4% for 7 mod 8 and 55.6% for 1 mod 8
HiddenWarrior is offline   Reply With Quote
Reply

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 2017-01-30 13:36
Special Form of Mersenne and Fermat Number Factors michael Math 31 2015-09-04 05:57
Factors with special form RedGolpe Factoring 5 2011-11-03 18:38
Missing factors at the 'Known Factors' page MatWur-S530113 PrimeNet 11 2009-01-21 19:08
Concordant Form Citrix Math 8 2006-03-19 20:45

All times are UTC. The time now is 18:01.

Sun Mar 7 18:01:08 UTC 2021 up 94 days, 14:12, 1 user, load averages: 1.24, 1.59, 1.60

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.