| Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3). |
Navigation
| Topics | Help • Register • News • History • How to • Sequences statistics • Template prototypes |
Difference between revisions of "Probable prime"
(restored) |
m |
||
| Line 1: | Line 1: | ||
| − | In [[ | + | 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 number|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 test for compositeness, which is based on [[Wikipedia:Fermat%27s_little_theorem|Fermat's little theorem]], works as follows: |
:Given an integer ''n'', choose some integer ''a'' [[coprime]] to ''n'' and calculate an <math>a^n \equiv 1</math> [[Modular arithmetic|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''. | :Given an integer ''n'', choose some integer ''a'' [[coprime]] to ''n'' and calculate an <math>a^n \equiv 1</math> [[Modular arithmetic|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== | ==External links== | ||
| − | *[ | + | *[[Wikipedia:Probable_prime|Wikipedia]] |
*[http://www.primenumbers.net/prptop/prptop.php PRP Records] maintained by H.& R. Lifchitz | *[http://www.primenumbers.net/prptop/prptop.php PRP Records] maintained by H.& R. Lifchitz | ||
[[Category:Math]] | [[Category:Math]] | ||
Revision as of 10:33, 6 February 2019
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
- Wikipedia
- PRP Records maintained by H.& R. Lifchitz
