## You are here

Homepseudoprime

## Primary tabs

# pseudoprime

A pseudoprime is a composite number $p$ 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 $b$ that is coprime to $p$, such as $b^{{p-1}}\equiv 1\mod p$ (from Fermat’s little theorem). For example, if $p$ is an odd prime, then the congruence $2^{{p-1}}\equiv 1\mod p$ will be true, but in reverse, $p$ can satisfy the congruence but turn out to be an odd composite number. Such pseudoprimes are then called pseudoprime to base $b$, and in our example with $b=2$, 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 $p$ divides an element it indexes in a Fibonacci-like sequence. For example, a Perrin pseudoprime $p$ divides $a_{p}$, where $a_{n}$ is the $n$-th element in the Perrin sequence.

# References

- 1 R. Crandall & C. Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001: 5.1

## Mathematics Subject Classification

11A51*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Comments

## trying to expose pseudo's

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