mersenneforum.org Prime 997 revisited.
 Register FAQ Search Today's Posts Mark Forums Read

 2022-01-24, 18:16 #12 Dr Sardonicus     Feb 2017 Nowhere 2×5×577 Posts Let us not forget the numbers that have changed status. Fermat (letters, 1630's - 1640's) claimed that all numbers 2^(2n) + 1 were prime. Thus, 232 + 1 changed from prime to composite (Euler, 1732; published 1738) Mersenne claimed 2p - 1 was prime (at least for p ≤ 257) when p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257. Thus, 261 -1 changed from composite to prime (Peruvshin, 1883) 267 - 1 changed from prime to composite (Cole, 1903) etc
2022-01-24, 19:54   #13
rudy235

Jun 2015
Vallejo, CA/.

1,093 Posts

Quote:
 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^(2n) + 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?

 2022-01-24, 19:55 #14 RomanM   Jun 2021 47 Posts prime numbers boring. take a look into prime angles
2022-01-24, 21:07   #15
Dr Sardonicus

Feb 2017
Nowhere

2×5×577 Posts

Quote:
 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 Mp that tests PRP to base 3 may be proven composite by an LL test.

 2022-01-24, 21:28 #16 paulunderwood     Sep 2002 Database er0rr 2×32×229 Posts 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 Last fiddled with by paulunderwood on 2022-01-24 at 21:29
2022-01-24, 21:33   #17
rudy235

Jun 2015
Vallejo, CA/.

1,093 Posts

Quote:
 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.

2022-01-30, 04:48   #18
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

7×1,423 Posts

Quote:
 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...

 Similar Threads Thread Thread Starter Forum Replies Last Post Hugo1177 Miscellaneous Math 1 2021-01-05 08:09 carpetpool carpetpool 5 2020-02-15 20:06 MARTHA Miscellaneous Math 7 2018-11-02 01:24 Harvey563 Open Projects 97 2011-09-30 20:19 hj47 Hardware 15 2010-07-08 20:19

All times are UTC. The time now is 13:01.

Thu May 19 13:01:53 UTC 2022 up 35 days, 11:03, 0 users, load averages: 2.77, 2.08, 1.85