Pseudoprimes

Ryan Schipfer 13 Feb 2009 17:33

**Pseudoprimes** are integers which re not actually prime, but share a property common to all prime numbers.

One example of a pseudoprime are composite integers, $x$, which satisfy Fermats little theorem, when $x$ is used in place of p. That is if $(x,a)=1$ $x$ is not a prime and $a^(x-1)\congruent 1 \mod x$ is true, then x is is a pseudoprime to base a. Actually, these are a special pseudoprimes known as **Fermat pseudoprimes**. If $x$ is a pseudoprime for all values of $a$ that are coprime to $x$, then $x$ is a **Carmichael Number**.

For more on pseudoprimes, check out: http://primes.utm.edu/glossary/page.php?sort=Pseudoprime