Pseudoprime

A pseudoprime is a composite number that has certain properties in common with prime numbers.

Introduction

If you want to find out if a given number is a prime number, you can to test it based on some properties that all prime numbers share. A property of prime numbers is that they are only divisible by one and itself. This is a defining property: it holds for all prime numbers and no other numbers.

However, other properties hold for all prime numbers and also some other numbers. For instance, every prime number has the form $6n-1\$ or $6n+1\$ (with n an integer), but there are also composite numbers of this form: 25, 35, 49, 55, 65, 77, 85, 91, … . So, you could say that 25, 35, 49, 55, 65, 77, 85, 91, … are pseudoprimes with respect to the property of being of the form $6n-1\$ or $6n+1\$. There exist better properties, which lead to special pseudoprimes:

Different kinds of pseudoprimes

Property	kind of pseudoprime
$a^{n-1}\equiv 1{\pmod {n}}$	Fermat pseudoprime
$a^{\frac {n-1}{2}}\equiv 1{\pmod {n}}$	Euler pseudoprime
$a^{\frac {n-1}{2}}\equiv (n-1){\pmod {n}}$
$a^{d}\equiv 1{\pmod {n}}$	strong pseudoprime
$a^{d\cdot 2^{r}}\equiv -1{\pmod {n}}$
$a^{n}-a\$ is divisible by $n\$	Carmichael number
$P_{n}\$ is divisible by $n\$	Perrin pseudoprime
$V_{n}(P,Q)-P\$ is divisible by $n\$