Are any Mersenne factors 1 mod p^2?

[alpertron]

Running PRP on the cofactor requires 71 days in my computer. I think that it is too much for me.

[ATH]

Originally Posted by alpertron

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

I made my own program and found the same 22 solutions as you.

I also checked all factors from mersenne.ca from 1G to 10G, there were no solutions at all.

[LaurV]

Still reading through the topic. Is this what you want to achieve?

[ATH]

Originally Posted by LaurV

Still reading through the topic. Is this what you want to achieve?

No, this is about Mersenne factors that are:
2*k*p² + 1 instead of 2*k*p + 1

There are only 1 known example where the factor is prime:
2*674487*93077² + 1

and 20 others found in this thread that are composite and 1 unknown status:
(2^281903623-1)/4929034977952529199403122399722497889153231 (see post #36)

[Andrew Usher]

So, the reasonable question is: how did you use the mersenne.ca data if its format was such an obstacle as alpertron saw?

And, yes, this topic turns out not really to be related to Wieferich primes, except in the trivial way that the whole number (as a divisor of itself) is on the list if and only if the exponent is one, as 2^p - 1 = 1 <-> 2^(p-1) = 1, mod anything.

[ATH]

Originally Posted by Andrew Usher

So, the reasonable question is: how did you use the mersenne.ca data if its format was such an obstacle as alpertron saw?

And, yes, this topic turns out not really to be related to Wieferich primes, except in the trivial way that the whole number (as a divisor of itself) is on the list if and only if the exponent is one, as 2^p - 1 = 1 <-> 2^(p-1) = 1, mod anything.

There are lists of comma separated txt files at the bottom here with "exponent,k" so you just calculate the factor 2*k*exponent + 1 after reading the 2 values.
https://www.mersenne.ca/export/

[alpertron]

Notice that you have to sort the numbers by exponent. After you get n prime factors of 2^k - 1 from mersenne.ca, you have to test which of the 2^{n + 1} - 1 factors (we have to exclude the number 1) of 2^k - 1 are congruent to 1 mod k².

[ATH]

Originally Posted by alpertron

Notice that you have to sort the numbers by exponent. After you get n prime factors of 2^k - 1 from mersenne.ca, you have to test which of the 2^{n + 1} - 1 factors (we have to exclude the number 1) of 2^k - 1 are congruent to 1 mod k².

They are in exponent order in these files, see screenshot. https://www.mersenne.ca/export/

Don't you mean if there are n factors there are 2ⁿ - 1 options to check?

I my program I treat it as a binary number if each factor is "on" or "off" in this product: f1*f2*f3...*fn
Skip 0 because that would give the product 1, then make a loop from 1 to 2ⁿ-1 and multiply those factors that are "on" in the binary representation of that number.

For example n=5: There are 5 ways to choose 1 factor, (5 choose 2) = 10 ways to choose 2 of 5 factors, (5 choose 3) = 10 ways to choose 3 of 5, (5 choose 4) = 5 and 1 way to choose all:
5+10+10+5+1 = 2⁵-1



Edit: Ah right for each of those above I check the product as well as (2^p-1)/product and finally the number (2^p-1) itself so a total of 2*(2ⁿ-1) + 1 = 2ⁿ⁺¹ -1, you are right.

[alpertron]

Yesterday I started running PRP for (2^281903623-1)/4929034977952529199403122399722497889153231

It will require about 70 days.

[ATH]

Originally Posted by ATH

Edit: Ah right for each of those above I check the product as well as (2^p-1)/product and finally the number (2^p-1) itself so a total of 2*(2ⁿ-1) + 1 = 2ⁿ⁺¹ -1, you are right.

You don't have to actually calculate (2^p-1)/"product", I started by doing that and it took forever. Several hours to just get to 50M (on 1 core).

If N=2^p-1=a*b, and a is the "product" then b=N/a is the one we want to check mod p².

If we calculate N (mod p²) by modular exponentiation and the "product" a mod p² then:
N mod p² = (a mod p²)*(b mod p²)

But we only want to know if (b mod p²) is 1 or not, and the only way it can be 1 is if:
N (mod p²) = a (mod p²) (where a is the current "product" in our loop checking all posibilities.)

So we only need to calculate (2^p-1) mod p² once by modular exponentiation and then compare it to all the different products mod p².

[Andrew Usher]

I see (and alpertron has already gone through how that computation is best accomplished).

So is that "exponent,k" format newly added, after the search in which he said he couldn't use mersenne.ca's data? It is indeed not difficult with that.