Editing Probable prime (section)

{{Short description|Integers that satisfy a specific condition}}
{{distinguish|Provable prime}}

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 number]]s. Different types of probable primes have different specific conditions. While there may be probable primes that are composite (called [[pseudoprime]]s), 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 {{nowrap|1 < ''a'' < ''n'' − 1}}). Calculate {{nowrap|''a''<sup>''n'' &minus; 1</sup> [[modular arithmetic|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 {{nowrap|25 × 10<sup>9</sup>}}, there are 11,408,012,595 odd composite numbers, but only 21,853 pseudoprimes base 2.<ref name="PSW">{{cite journal |author1 = Carl Pomerance |author-link1 = Carl Pomerance |author2 = John L. Selfridge |author-link2 = John L. Selfridge |author3 = Samuel S. Wagstaff, Jr. |author-link3 = Samuel S. Wagstaff, Jr. |title=The pseudoprimes to 25·10<sup>9</sup> |journal=Mathematics of Computation |date=July 1980 |volume=35 |issue=151 |pages=1003–1026 |url=//math.dartmouth.edu/~carlp/PDF/paper25.pdf |jstor=2006210 |doi=10.1090/S0025-5718-1980-0572872-7 |doi-access=free }}</ref>{{rp|1005}} The number of odd primes in the same interval is 1,091,987,404.