Prime 997 revisited.

[Dr Sardonicus]

Let us not forget the numbers that have changed status.

Fermat (letters, 1630's - 1640's) claimed that all numbers 2^(2ⁿ) + 1 were prime.

Thus, 2³² + 1 changed from prime to composite (Euler, 1732; published 1738)

Mersenne claimed 2^p - 1 was prime (at least for p ≤ 257) when p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257.

Thus,

2⁶¹ -1 changed from composite to prime (Peruvshin, 1883)

2⁶⁷ - 1 changed from prime to composite (Cole, 1903)

etc

[rudy235]

Originally Posted by Dr Sardonicus

Let us not forget the numbers that have changed status.

Fermat (letters, 1630's - 1640's) claimed that all numbers 2^(2ⁿ) + 1 were prime.

Thus,

etc

In this line of thought –and this may has been asked and answered before– is there any pseudoprime to many bases (but not a Carmichael number) that was assumed to be a PRP and was later confirmed as composite?

[RomanM]

prime numbers boring. take a look into prime angles

[Dr Sardonicus]

Originally Posted by rudy235

In this line of thought –and this may has been asked and answered before– is there any pseudoprime to many bases (but not a Carmichael number) that was assumed to be a PRP and was later confirmed as composite?

Actually, that should probably be something like, "Are there any pseudoprimes that were assumed to be prime because they tested PRP to many bases, but were later proven to be composite?"

A PRP is generally understood to mean any integer greater than 1 that does not test as composite to some base(s) with a Fermat (or Euler or Miller-Rabin) test, while a "pseudoprime" is generally understood to mean a composite number that does not so test as composite.

I don't know about "assumed to be prime because they tested as PRP's but then proved composite." I don't know of any examples offhand. There might be "mundane" examples of numbers that individual users of some software package assumed to be prime because it tested as a PRP with the package's test, but later proved to be composite.

I note that though a Carmichael number n is guaranteed to test PRP by a Fermat test to any base prime to n, it may well be revealed as composite by a Miller-Rabin test. In such a case, Miller-Rabin provides a square root of 1 other than 1 or -1, hence a proper factorization. For example, Mod(2,561)^560 and Mod(2,561)^280 are both Mod(1,561), but Mod(2,560)^140 = Mod(67,561). Then gcd(67-1,561) = 33 and gcd(67+1,561) 17 are proper factors.

There are, however, ways of constructing numbers which are the product of two prime numbers, that will test as PRP's by Miller-Rabin to any given finite set of (usually prime) bases.

But who knows? The next M_p that tests PRP to base 3 may be proven composite by an LL test.

[paulunderwood]

https://primes.utm.edu/notes/proofs/a_pseudoprimes.html shows how to construct base-a pseudoprimes.

https://www.fq.math.ca/Scanned/41-4/chen.pdf and https://www.d.umn.edu/~jgreene/baillie/Baillie-PSW.html supposedly shows how to construct BPSW pseudoprimes

http://pseudoprime.com/dopo.pdf Pomerance argues for the infintude of BPSW pseudoprimes.

More at: https://en.wikipedia.org/wiki/Bailli...est#References

[rudy235]

while a "pseudoprime" is generally understood to mean a composite number that does not so test as composite.

Yes, I messed up when using the word pseudoprime. What I meant was along he line of a number that after many tests and varied approaches is indistinguishable from a true PRP but is eventually found to be composite. I.e pseudoprime. I had read somewhere of this but I can’t remember where.

[LaurV]

Originally Posted by Dr Sardonicus

Let us not forget the numbers that have changed status.
Fermat ...
Euler ...
Mersenne ...
Peruvshin ...
Cole ...

This post sounds like pledge for rehabilitation for the crackpots that visit the forum periodically...

I mean, if so many big guys made mistakes...