In number theory, a probable prime (PRP) is an integer that satisfies a specific condition that is satisfied by all prime numbers, but which is not satisfied by most composite numbers. Different types of probable primes have different specific conditions. While there may be probable primes that are composite (called pseudoprimes), the condition is generally chosen in order to make such exceptions rare.
Fermat's test for compositeness, which is based on Fermat's little theorem, works as follows: given an integer n, choose some integer a that is not a multiple of n; (typically, we choose a in the range 1 < a < n − 1). Calculate an − 1 modulo n. If the result is not 1, then n is composite. If the result is 1, then n is likely to be prime; n is then called a probable prime to base a. A weak probable prime to base a is an integer that is a probable prime to base a, but which is not a strong probable prime to base a (see below).
For a fixed base a, it is unusual for a composite number to be a probable prime (that is, a pseudoprime) to that base. For example, up to 25 × 109, there are 11,408,012,595 odd composite numbers, but only 21,853 pseudoprimes base 2.[1]: 1005 The number of odd primes in the same interval is 1,091,987,404.