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 − 1 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.
Read more about Probable Prime: Properties, Variations
Famous quotes containing the words probable and/or prime:
“I have very lately read the Prince of Abyssinia [Samuel Johnson’s Rasselas]MI am almost equally charmed and shocked at it—the style, the sentiments are inimitable—but the subject is dreadful—and, handled as it is by Dr. Johnson, might make any young, perhaps old, person tremble—O heavens! how dreadful, how terrible it is to be told by a man of his genius and knowledge, in so affectingly probable a manner, that true, real happiness is ever unattainable in this world!”
—Frances Burney (1752–1840)
“One wants in a Prime Minister a good many things, but not very great things. He should be clever but need not be a genius; he should be conscientious but by no means strait-laced; he should be cautious but never timid, bold but never venturesome; he should have a good digestion, genial manners, and, above all, a thick skin.”
—Anthony Trollope (1815–1882)