PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: High Entry average rating: No information on entry rating
pseudoprime (Definition)

"pseudoprime" is owned by CompositeFan.
(view preamble | get metadata)

View style:


Attachments:
table of pseudoprimes below 2000 in bases 2 to 16 (Example) by PrimeFan
Log in to rate this entry.
(view current ratings)

Cross-references: Perrin sequence, Perrin pseudoprime, sequence, indexes, divides, Sarrus numbers, term, Neil Sloane, OEIS, prime, odd, Fermat's little theorem, coprime, base, congruence, positive, primality, composite number
There are 4 references to this entry.

This is version 3 of pseudoprime, born on 2007-03-13, modified 2008-05-30.
Object id is 9068, canonical name is PseudoprimeP.
Accessed 1191 times total.

Classification:
AMS MSC11A51 (Number theory :: Elementary number theory :: Factorization; primality)

Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy
trying to expose pseudo's by leavemsg2 on 2009-05-01 14:21:47
I'm posing the conjecture:
Does this criteria always expose 2-pseudoprimes ???
(sorry if I'm not using the maths totally correctly)

let 2^(Q-1) mod Q == 1 where Q = 4m +1 (possibly pseudo)
now, 'Q' is prime iff the above criteria and...
2^(Q-1)-2 mod 'q' == -1, 0
where 'q' is 'Q' w/all 2's factored out.

it approves primes...
eg. Q= 641 = 4*160 +1 and 2^640 mod 641 == 1
q= 5 or 640 w/all the 2's factored out
then, 2^640-2 mod 5 == -1, so 641 truly is prime.

and dis-allows pseudos...
eg. Q= 341 = 4*85 +1 and 2^340 mod 341 == 1
q= 85 or 340 w/all 2's factored out
then, 2^340-2 mod 85 == 14, so 341 is pseudo.

eg. Q= 101 = 4*25 +1 and 2^100 mod 101 == 1
q= 25 or 100 w/all the 2's factored out
then, 2^100-2 mod 25 == -1, so 101 truly is prime.

I think that it's always 'true', but can't prove it!

from a cursory glance, it looks O.K.?
it takes a pseudo to know a pseudo...

Bill Bouris
[ reply | up ]

Interact
post | correct | update request | add derivation | add example | add (any)