Worlds of David Darling
Encyclopedia of Science
   
Home > Encyclopedia of Science

pseudoprime




A number that passes the test of Fermat's little theorem (FLT) for prime numbers but actually isn't a prime. FLT says that if p is prime and a is coprime to p, then ap-1 - 1 is divisible by p. If a number x is not prime, a is coprime to x, and x divides ax-1 - 1, then x is called a pseudoprime to base a.

A number x that is a pseudoprime for all values of a that are coprime to x is called a Carmichael number. The smallest pseudoprime for in base 2 is 341. It isn't prime because 341 = 11 × 31; however, it satisfies FLT: 2340 - 1 is divisible by 341.


Related categories

   • PRIME NUMBERS
   • TYPES OF NUMBER