mersenneforum.org Are any Mersenne factors 1 mod p^2?
 Register FAQ Search Today's Posts Mark Forums Read

2023-01-12, 00:08   #34
charybdis

Apr 2020

16678 Posts

Quote:
 Originally Posted by Andrew Usher Composite factors with the property should be O(log p) instead of O(log log p), but again that assumes full factorisation.
Shouldn't it be O((log log p)2) for prime factors?

 2023-01-12, 13:02 #35 Andrew Usher   Dec 2022 13916 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.
 2023-01-14, 14:39 #36 alpertron     Aug 2002 Buenos Aires, Argentina 22×3×53 Posts I've just found another solution. Let m = (2281903623-1)/4929034977952529199403122399722497889153231. m is a divisor of 2281903623-1 and it is congruent to 1 modulo 2819036232. Actually we do not know whether m is prime or composite.
 2023-01-15, 12:32 #37 alpertron     Aug 2002 Buenos Aires, Argentina 22×3×53 Posts I searched the complete range 0-1000M and I found no more solutions.
 2023-01-15, 13:24 #38 Andrew Usher   Dec 2022 1001110012 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.
2023-01-15, 13:34   #39
alpertron

Aug 2002
Buenos Aires, Argentina

150010 Posts

Quote:
 Originally Posted by Andrew Usher 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.
That is not entirely correct. We do not know if the last one I found is prime or composite. At this moment I'm running P-1 with B1 = 1M, B2 = 30M. Other people ran trial factoring with bound 2^76 without finding any factor.

You can see the status here.

Last fiddled with by alpertron on 2023-01-15 at 13:38

 2023-01-15, 15:41 #40 Dr Sardonicus     Feb 2017 Nowhere 3×2,113 Posts Suppose for the sake of discussion that Mp is squarefree. Suppose further than Mp 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 Mp. 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 Mp, 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 Mp, 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 Mp is squarefree, it follows that, if Mp == p*A + 1 (mod p^2), and d is a divisor of Mp, and d == p*a + 1 (mod p^2), then Mp/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 2023-01-15 at 15:43 Reason: xignif posty
 2023-01-15, 15:56 #41 alpertron     Aug 2002 Buenos Aires, Argentina 22·3·53 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.
2023-01-15, 16:29   #42
Dr Sardonicus

Feb 2017
Nowhere

3×2,113 Posts

Quote:
 Originally Posted by alpertron 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.
Yes, I figured that out. Full marks!

If you list the "reduced factors" < p of the known prime divisors and the remaining cofactor of Mp, say

(r1, ..., rt)

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 Mp 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 2023-01-15 at 17:54

 2023-01-15, 21:34 #43 Andrew Usher   Dec 2022 313 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) 79-digit 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.
 2023-01-16, 01:28 #44 Dr Sardonicus     Feb 2017 Nowhere 11000110000112 Posts I don't know what the smart money is on the "expected" number of prime factors of Mp as a function of p, or how large the number of prime factors might reasonably be expected to be. For ordinary, run-of-the-mill numbers of size N, it's something like log(log(N)) if memory serves. For Mp that would be something like log(p). The exponent 4933 seems extraordinary. M4933 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 Mp 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 Mp. 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 (Mp - 1)/p (mod p). Choosing the value 0 (mod p) would then indicate that there "should" be about log(log(X)) (base-2) Wieferich primes up to X. However, the numerical data does not seem to support this. The largest known (base-2) Wieferich prime is 3511, and the search bound is at least of order 1015 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?

 Similar Threads Thread Thread Starter Forum Replies Last Post bhelmes Number Theory Discussion Group 21 2021-09-15 02:07 ATH Miscellaneous Math 7 2020-10-09 11:09 bhelmes Miscellaneous Math 8 2020-09-14 17:36 tapion64 Miscellaneous Math 21 2014-04-18 21:02 CRGreathouse Math 5 2013-06-14 11:44

All times are UTC. The time now is 21:56.

Fri Mar 31 21:56:02 UTC 2023 up 225 days, 19:24, 0 users, load averages: 0.57, 0.84, 0.86