Probable prime

In number theory, a probable prime (PRP) is an integer that satisfies a specific condition also satisfied by all prime 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 coprime to n and calculate an [math]\displaystyle{ a^n \equiv 1 }[/math] modulo n. If the result is different from 1, n is composite. If it is 1, n may or may not be prime; n is then called a (weak) probable prime to base a.

External links

• Probable prime
• PRP Records maintained by H.& R. Lifchitz

Number classes

General numbers

Integer Natural Even Odd Rational Irrational Real Prime Probable prime

Special numbers

Mersenne 2n-1 Fermat 22n+1 Proth k•2n+1 Riesel k•2n-1 Woodall n•2n-1 Cullen n•2n+1 Double Mersenne 22p-1-1 Perfect 2n-1(2n-1) Leyland xy ± yx Gen.Repunit (b^n-1)/(b-1)

Prime numbers

Mersenne Proth Riesel Williams (b±1)bn±1 Carol/Kynea (bn±1)2-2 Multifactorial n!j±1