Composite PRP

[paulunderwood]

Originally Posted by henryzz

Carmichael numbers are too easy. What is the largest non-Carmichael number that is known to be b-prp?

2^(2^82589933-1)-1 is 2-PRP

[henryzz]

Originally Posted by paulunderwood

2^(2^82589933-1)-1 is 2-PRP

And non-trivial

[paulunderwood]

Originally Posted by henryzz

And non-trivial

A little more on the subject... A proof that there are infinitely many pseudoprimes base a

[LaurV]

Originally Posted by ATH

There are no composite 3-PRP of the form 2ⁿ-1 for all n<100,000 (including composite n).

And there may be none at all. Something similar to Pepin test for Fermats may go also for Mersennes, but this is still an open question (as opposite to a "conjecture", where we can "guess" or "heuristically prove" one way or the other, here we have no clue). My belief is that a mersenne number which is 3-PRP is also prime, and this also applies to mersenne factors, if we restrict the exponent to be prime. But of course, I have no clue how could we prove that. This falls in the same category as the infinitude of Wieferich primes, or the mersenne numbers with prime exponents being square free - we have no guess, in either direction.

[chris2be8]

Has anyone checked for a Mersenne number that's a Lucas pseudoprime? Any such would also be a BPSW pseudoprime which would be an interesting discovery. Or can it be proved there are none such?

Chris

[Dr Sardonicus]

Originally Posted by paulunderwood

2^(2^82589933-1)-1 is 2-PRP

How do you know it isn't a Carmichael number?

[JeppeSN]

Originally Posted by LaurV

My belief is that a mersenne number which is 3-PRP is also prime, and this also applies to mersenne factors, if we restrict the exponent to be prime.

239 is a prime. The Mersenne number 2^239-1 has as a factor the number 10974881. That number, 10974881, is really a 3-PRP. So by your belief, 10974881 should be a prime.

But as you may have guessed, 10974881 is not a 5-PRP. In fact:

10974881 = 1913 * 5737

Can someone come up with a conjecture on the number of counterexamples of this type?

/JeppeSN

[a1call]

Largest fake prime number holds 300 billion digits
A 300-billion-digit number is the biggest known pseudoprime
...
To hunt out the fakes, Shallue and colleague Steven Hayman created an algorithm that looks at a list of numbers to find a subset that, when multiplied together, produces a particular target – in this case, a pseudoprime that passes Fermat’s test.

https://www.newscientist.com/article...illion-digits/

[LaurV]

Originally Posted by JeppeSN

239 is a prime. The Mersenne number 2^239-1 has as a factor the number 10974881. That number, 10974881, is really a 3-PRP

Whoops...
Never managed to do any tests, it was some small light blinking in a corner of my mind, and bothering me regularly from time to time, but I never invested the time to check.
Now I am very glad you found that! It settles the blinking light... hehe
It is a pity that in this case we still can't declare the "probable fully factored" mersennes that GP2 (and others) are putting a lot of effort into, to be "fully factored for sure" ...

[GP2]

Originally Posted by LaurV

It is a pity that in this case we still can't declare the "probable fully factored" mersennes that GP2 (and others) are putting a lot of effort into, to be "fully factored for sure" ...

But we test the cofactor to multiple bases, and then Paul Underwood tests for Lucas PRP. So it's not "for sure", but a lot more than just 3-PRP.

Edit: actually, FactorDB only stores PRPs for Mersenne cofactors for exponents up to about 500k. So for the larger ones, there is no record of testing them to any base other than 3. You could do it with PFGW. In any case Paul Underwood posts his Lucas PRP results to the "disbelievers" thread.

[JeppeSN]

Originally Posted by LaurV

Whoops...

If you let n run through all odd composite 3-PRP, and test if znoroder(Mod(2, n)) is a prime, you get the counterexamples in a sorted way. The sequence goes:

10974881, 193949641, 717653129, 8762386393

I am considering submitting it to OEIS.

/JeppeSN