Pseudoprime

A Pseudoprime is a composite number, which have with Prime numbers common properties.

Introduce

If you would find out if a number is a prime number, you have properties to test it. A property of prime numbers, that they are only divisible by one and itself. Some of the properties are not only true to prime numbers. So you can say, that every prime number has the form: $6n-1\$ or $6n+1\$. Not only prime numbers has these form, but also the composite numbers 25, 35, 49, 55, 65, 77, 85, 91, ... . So, in relation of the property $6n-1\$ or $6n+1\$, you could say, that 25, 35, 49, 55, 65, 77, 85, 91, ... are pseudoprimes. There exist better properties, which leads 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\$