**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 *a**n* − 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

### Other articles related to "probable prime, prime":

**Probable Prime**- Variations

... An Euler

**probable prime**to base a is an integer that is indicated

**prime**by the somewhat stronger theorem that for any

**prime**p, a(p − 1)/2 equals modulo p, where is ... An Euler

**probable prime**which is composite is called an Euler–Jacobi pseudoprime to base a ... using the fact that the only square roots of 1 modulo a

**prime**are 1 and −1 ...

### Famous quotes containing the words prime and/or probable:

“My *prime* of youth is but a frost of cares,

My feast of joy is but a dish of pain,

My crop of corn is but a field of tares,

And all my good is but vain hope of gain:

The day is past, and yet I saw no sun,

And now I live, and now my life is done.”

—Chidiock Tichborne (1558–1586)

“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)