Are any Mersenne factors 1 mod p^2? - Page 4

charybdis · 2023-01-12, 00:08

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)²) for prime factors?

Andrew Usher · 2023-01-12, 13:02

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.

alpertron · 2023-01-14, 14:39

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².

Actually we do not know whether m is prime or composite.

alpertron · 2023-01-15, 12:32

I searched the complete range 0-1000M and I found no more solutions.

Andrew Usher · 2023-01-15, 13:24

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.

alpertron · 2023-01-15, 13:34

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.

Dr Sardonicus · 2023-01-15, 15:41

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]

alpertron · 2023-01-15, 15:56

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.

Dr Sardonicus · 2023-01-15, 16:29

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 M_p, say

(r₁, ..., 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.

Andrew Usher · 2023-01-15, 21:34

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.

Dr Sardonicus · 2023-01-16, 01:28

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, run-of-the-mill 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₄₉₃₃ 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)) (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 10¹⁵ 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?

2023-01-15, 15:41	#40
Dr Sardonicus 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 == pa + 1 and d2 == (pb + 1) (mod p^2), then d1d2 is also a divisor, and d1d2 == p(a + b) + 1 (mod p^2. From the assumption that M_p is squarefree, it follows that, if M_p == pA + 1 (mod p^2), and d is a divisor of M_p, and d == pa + 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 2023-01-15 at 15:43 Reason: xignif posty

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
factors of Mersenne numbers	bhelmes	Number Theory Discussion Group	21	2021-09-15 02:07
Mersenne factors 2kp+1	ATH	Miscellaneous Math	7	2020-10-09 11:09
factors of Mersenne numbers	bhelmes	Miscellaneous Math	8	2020-09-14 17:36
Distribution of Mersenne Factors	tapion64	Miscellaneous Math	21	2014-04-18 21:02
Known Mersenne factors	CRGreathouse	Math	5	2013-06-14 11:44

2023-01-12, 13:02	#35
Andrew Usher Dec 2022 111000000₂ 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 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². Actually we do not know whether m is prime or composite.

2023-01-15, 12:32	#37
alpertron Aug 2002 Buenos Aires, Argentina 2·761 Posts	I searched the complete range 0-1000M and I found no more solutions.

2023-01-15, 13:24	#38
Andrew Usher Dec 2022 2⁶·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.

2023-01-15, 15:56	#41
alpertron Aug 2002 Buenos Aires, Argentina 1522₁₀ 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, 21:34	#43
Andrew Usher Dec 2022 2⁶×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) 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 14362₈ 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, run-of-the-mill 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₄₉₃₃ 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 2k (mod p) for the prime factors q = 2kp + 1 of M_p. Invoking the "Assumption of Ignorance" would give a default answer of each of the p values of 2k (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)) (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 10¹⁵ and may be higher by now. Has anyone here compiled statistics for 2k (mod p) for prime* factors q = 2kp + 1 or know where they are?