Pseudoprimes

This article needs more work.

Please help by expanding it!

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

To find out if a given number is a prime number, one can test it for properties that all prime numbers share. One property of a prime number is that it is only divisible by one and itself. This is a defining property: it holds for all primes and no other numbers.

However, other properties hold for all primes and also some other numbers. For instance, every prime number greater than 3 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, … (see A038509). So, we can 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, as outlined below.

A theorem by Sierpinski states that if n is a pseudoprime (odd or even), then 2^n-1 is a pseudoprime, meaning they are infinite.

Hierarchy of pseudoprimes

Hierarchy of Pseudoprimes
$\scriptstyle n\$ divides $\scriptstyle U_{n}(P,Q)-\left({\frac {D}{n}}\right)$ and $\scriptstyle n\$ divides $\scriptstyle V_{n}(P,Q)-P\$
Fermat pseudoprimes
Euler pseudoprimes Euler-Jacobi pseudoprimes Strong pseudoprimes

A great part of the different sort of pseudoprimes is family. So is a strong pseudoprime an Euler pseudoprime and also a Fermat pseudoprime. On the other hand is every Fermat pseudoprime a special case of pseudoprime of the form $\scriptstyle p\,$ divides $\scriptstyle V_{p}(P,Q)-P\$ (Lucas sequences#Lucas sequences and the prime numbers.

Here is the hierarchy from the most generally form of pseudoprime to the most especially form of pseudoprime:

• Pseudoprimes of the form $\scriptstyle n\$ divides $\scriptstyle U_{n}(P,Q)-\left({\frac {D}{n}}\right)$ and the form $\scriptstyle n\$ divides $\scriptstyle V_{n}(P,Q)-P\$===

Lucas pseudoprimes ($\scriptstyle n\$ divides $\scriptstyle F_{n}-\left({\frac {D}{n}}\right)$, where $\scriptstyle F_{n}\,$ is a Fibonacci number) is a form of pseudoprimes which matches the form $\scriptstyle n\$ divides $\scriptstyle U_{n}(P,Q)-\left({\frac {D}{n}}\right)$.

Likewise are Fibonacci pseudoprimes ($\scriptstyle n\$ divides $\scriptstyle L_{n}-P\$, where $\scriptstyle L_{n}\,$ is a Lucas number) is a form of pseudoprimes which matches the form $\scriptstyle n\$ divides $\scriptstyle V_{n}(P,Q)-P\$

It is a bit confusing, that the Lucas pseudoprimes calculated with Fibonacci numbers, and the Fibonacci pseudoprimes calculated with Lucas numbers.

Fermat pseudoprimes ($\scriptstyle a^{n}\equiv a{\pmod {n}}$) are the special case of pseudoprimes of the form $\scriptstyle n\$ divides $\scriptstyle V_{n}(P,Q)-P\$, where $\scriptstyle Q=a\,$ and $\scriptstyle P=a+1\,$, so that $\scriptstyle n\$ divides $\scriptstyle V_{n}(a+1,a)-V_{1}(a+1,a)\$.

• Fermat pseudoprimes

There are some sorts of pseudoprimes, which are Fermat pseudoprimes. The two best-known forms are:

1. Carmichael numbers, which is Fermat pseudoprime for every integer $\scriptstyle a\,$ and
2. Euler pseudoprimes

• Euler pseudoprimes and Euler-Jacobi pseudoprimes

• Strong pseudoprimes