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"

From Prime-Wiki
Jump to: navigation, search
(restored)
 
(mathed)
 
(4 intermediate revisions by 2 users not shown)
Line 1: Line 1:
In [[Number theory]], a '''probable prime''' (PRP) is an [[integer]] that satisfies a specific condition also satisfied by all [[prime number]]s. 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.
+
{{Shortcut|PRP|Probable prime: an [[integer]] that satisfies a specific condition also satisfied by all [[prime]] numbers.}}
 +
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 [http://en.wikipedia.org/wiki/Fermat%27s_little_theorem Fermat's little theorem], works as follows:
+
'''Fermat's test for compositeness''' (sometimes called '''Fermat primality test''') is based on [[Wikipedia:Fermat%27s_little_theorem|Fermat's little theorem]]. It 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 <math>n</math>, choose some integer <math>a</math> [[coprime]] to <math>n</math> and calculate an <math>a^n \equiv 1</math> [[Modular arithmetic|modulo]] <math>n</math>. If the result is different from 1, <math>n</math> is composite. If it is 1, <math>n</math> may or may not be prime; <math>n</math> is then called a (weak) probable prime to base <math>a</math>.
 +
 
 +
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 [[Lucas-Lehmer test]]) will be needed to find out if the number is really composite or not.
  
 
==External links==
 
==External links==
*[http://en.wikipedia.org/wiki/Probable_prime Wikipedia]
+
*[[Wikipedia:Probable_prime|Probable prime]]
 
*[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
 +
 +
{{Navbox NumberClasses}}
 +
 
[[Category:Math]]
 
[[Category:Math]]

Latest revision as of 07:28, 12 March 2024

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 [math]\displaystyle{ n }[/math], choose some integer [math]\displaystyle{ a }[/math] coprime to [math]\displaystyle{ n }[/math] and calculate an [math]\displaystyle{ a^n \equiv 1 }[/math] modulo [math]\displaystyle{ n }[/math]. If the result is different from 1, [math]\displaystyle{ n }[/math] is composite. If it is 1, [math]\displaystyle{ n }[/math] may or may not be prime; [math]\displaystyle{ n }[/math] is then called a (weak) probable prime to base [math]\displaystyle{ a }[/math].

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 Lucas-Lehmer test) will be needed to find out if the number is really composite or not.

External links

Number classes
General numbers
Special numbers
Prime numbers