|
|
|
|
|
A pseudoprime is a composite number  that passes a given primality test. In other words, a pseudoprime is a false positive on a primality test.
The primality test is usually a power congruence to a given base  that is coprime to  , such as
 (from Fermat's little theorem). For example, if  is an odd prime, then the congruence
 will be true, but in reverse,  can satisfy the congruence but turn out to be an odd composite number. Such pseudoprimes are then called pseudoprime to base  , and in our example with  , the first few are 341, 561, 645, 1105, 1387, 1729, 1905 (A001567 in Sloane's OEIS). According to Neil Sloane, writing in the OEIS, the term “pseudoprime” is sometimes used specifically to refer to pseudoprimes to base 2. These are sometimes called Sarrus numbers.
Another kind of pseudoprimes are those in which a composite  divides an element it indexes in a Fibonacci-like sequence. For example, a Perrin pseudoprime  divides  , where  is the  -th element in the Perrin sequence.
- 1
- R. Crandall & C. Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001: 5.1
|
"pseudoprime" is owned by CompositeFan.
|
|
(view preamble)
Cross-references: Perrin sequence, Perrin pseudoprime, sequence, indexes, divides, numbers, term, Neil Sloane, OEIS, prime, odd, Fermat's little theorem, coprime, base, congruence, positive, primality, composite number
There are 6 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 673 times total.
Classification:
| AMS MSC: | 11A51 (Number theory :: Elementary number theory :: Factorization; primality) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
