20230112, 00:08  #34 
Apr 2020
1777_{8} Posts 

20230112, 13:02  #35 
Dec 2022
111000000_{2} Posts 
Yeah, when I think about it again it seems so. Of course, it's still practically O(log log n), because the number of factors we can find for a given p is constant at best.

20230114, 14:39  #36 
Aug 2002
Buenos Aires, Argentina
2·761 Posts 
I've just found another solution.
Let m = (2^{281903623}1)/4929034977952529199403122399722497889153231. m is a divisor of 2^{281903623}1 and it is congruent to 1 modulo 281903623^{2}. Actually we do not know whether m is prime or composite. 
20230115, 12:32  #37 
Aug 2002
Buenos Aires, Argentina
2·761 Posts 
I searched the complete range 01000M and I found no more solutions.

20230115, 13:24  #38 
Dec 2022
2^{6}·7 Posts 
And you'll presumably stop there, for the same reason. So we have 22 total solutions to exponent 10^9, of which 1 is a prime factor, 2 are the entire number (the Wieferich primes), and the remaining 19 composite proper divisors. The last class should comprise almost all the solutions, obviously, to the larger problem.

20230115, 13:34  #39  
Aug 2002
Buenos Aires, Argentina
2×761 Posts 
Quote:
You can see the status here. Last fiddled with by alpertron on 20230115 at 13:38 

20230115, 15:41  #40 
Feb 2017
Nowhere
2×31×103 Posts 
Suppose for the sake of discussion that M_{p} is squarefree. Suppose further than M_{p} is expressed as the product of t factors, at least all but the largest of which are known to be prime. Then there will be 2^t known divisors of M_{p}.
My ignorance of Perl is nearly complete, but that didn't stop me from trying to figure out how the script posted attacked the problem. As best I could tell, what it did was: for each divisor d of M_{p}, find the "reduced factor," which is the remainder of (d  1)/p modulo p. If this remainder is 0 for some d > 1, then d == 1 (mod p^2). This is a perfectly sound approach. I note the following: If d1 and d2 are divisors of M_{p}, gcd(d1, d2) = 1, d1 == p*a + 1 and d2 == (p*b + 1) (mod p^2), then d1*d2 is also a divisor, and d1*d2 == p*(a + b) + 1 (mod p^2. From the assumption that M_{p} is squarefree, it follows that, if M_{p} == p*A + 1 (mod p^2), and d is a divisor of M_{p}, and d == p*a + 1 (mod p^2), then M_{p}/d == p*(A  a) + 1 (mod p^2). If the divisors are listed in increasing order, then divisors whose indices add up to 2^t will have "reduced factors" whose sum is congruent to A (mod p). In the following example, we have e.g. 37 + 16 = 53, 99 + 67 = 166 == 53 (mod 113), and so on. Code:
? p=113;M=[3391,1;23279,1;65993,1;1868569,1;1066818132868207,1];D=divisors(M);v=vector(#D,i,((D[i]1)/p)%p);print(v) [0, 30, 93, 19, 38, 10, 49, 112, 68, 18, 57, 29, 48, 87, 99, 37, 16, 67, 79, 5, 24, 109, 35, 98, 54, 4, 43, 15, 34, 73, 23, 53] Last fiddled with by Dr Sardonicus on 20230115 at 15:43 Reason: xignif posty 
20230115, 15:56  #41 
Aug 2002
Buenos Aires, Argentina
1522_{10} Posts 
The idea is to generate all factors of Mp from the prime factors found in PrimeNet and the cofactor which is calculated in the script because it is not in PrimeNet.
The script uses Gray codes that have the property that only one bit is changed between two adjacent numbers. When the bit changes to "1" I perform multiplication, and when it changes to "0" I perform division. The "reduced factor" approach enables me to convert multiplications to additions and divisions to subtractions, and also to use small numbers, so the script runs a lot faster. 
20230115, 16:29  #42  
Feb 2017
Nowhere
18F2_{16} Posts 
Quote:
If you list the "reduced factors" < p of the known prime divisors and the remaining cofactor of M_{p}, say (r_{1}, ..., r_{t}) then the question becomes whether any subset of the r's adds up to a multiple of p (apart from the empty subset having sum 0). It had occured to me to wonder whether this could fail to happen for trivial reasons, like all of the r's being so small they couldn't possibly add up to a positive multiple of p. After all, t is going to be very small compared to p. The property I point out shows that the "reduced factors" of the available divisors occur in pairs (a, A  a) where the "reduced factor" of M_{p} is A < p. It's about all I have come up with so far regarding the sizes of "reduced factors". EDIT: D'oh! Of course, when formulated this way, the property I mentioned is obvious  sums over complementary subsets add up to the sum over the entire set. Last fiddled with by Dr Sardonicus on 20230115 at 17:54 

20230115, 21:34  #43 
Dec 2022
2^{6}×7 Posts 
Yes, it's rather nice it works out that way, isn't it? In fact, the modulus doesn't need to be prime because it's just algebra.
In fact the case of the r's being too small to add up to p has an important corollary: a number kp^2+1 (k < p) must be prime if one can prove (e.g. by Pocklington) any factor to be 1 mod p. This was used by the EDSAC team to find their (lucky) 79digit record in 1951, and could be used today to search for a record prime, save that the odds are so bad at current sizes. And with p = 64 we prove the primality of the Fermat number 65537  even the largest Fermat prime is so because it 'has to be'. I was assuming that cofactor to be composite because of the overwhelming chance it is (the possible primality would be only a footnote), and because I was giving a brief summary. 
20230116, 01:28  #44 
Feb 2017
Nowhere
14362_{8} Posts 
I don't know what the smart money is on the "expected" number of prime factors of M_{p} as a function of p, or how large the number of prime factors might reasonably be expected to be.
For ordinary, runofthemill numbers of size N, it's something like log(log(N)) if memory serves. For M_{p} that would be something like log(p). The exponent 4933 seems extraordinary. M_{4933} has ten known prime factors, and is known to have at least two more (the remaining cofactor is known to be composite). I suspected there had to be a lot of known prime factors when I saw two proper divisors congruent to 1 (mod 4933^2). Unfortunately, we don't have much hope of factoring most M_{p} for p of any size completely. The ones we might have hopes for would likely have very few factors. I also have no idea where the smart money is on the distribution of the values of 2*k (mod p) for the prime factors q = 2*k*p + 1 of M_{p}. Invoking the "Assumption of Ignorance" would give a default answer of each of the p values of 2*k (mod p) being equally likely. Of course, this might also apply to (M_{p}  1)/p (mod p). Choosing the value 0 (mod p) would then indicate that there "should" be about log(log(X)) (base2) Wieferich primes up to X. However, the numerical data does not seem to support this. The largest known (base2) Wieferich prime is 3511, and the search bound is at least of order 10^{15} and may be higher by now. Has anyone here compiled statistics for 2*k (mod p) for prime factors q = 2*k*p + 1 or know where they are? 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
factors of Mersenne numbers  bhelmes  Number Theory Discussion Group  21  20210915 02:07 
Mersenne factors 2*k*p+1  ATH  Miscellaneous Math  7  20201009 11:09 
factors of Mersenne numbers  bhelmes  Miscellaneous Math  8  20200914 17:36 
Distribution of Mersenne Factors  tapion64  Miscellaneous Math  21  20140418 21:02 
Known Mersenne factors  CRGreathouse  Math  5  20130614 11:44 