Navigation
Topics  Register • News • History • How to • Sequences statistics • Template prototypes 
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 (sometimes called Fermat primality test) is based on Fermat's little theorem. It 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.
Therefore Fermat's test can definitively tell only if a number is composite. Otherwise, if the test is not indicating compositeness, applying another primality test (like LucasLehmer test) will be needed to find out if the number is really composite or not.
External links
 Probable prime
 PRP Records maintained by H.& R. Lifchitz
Number classes
General numbers 
Special numbers 
Prime numbers 
