Pseudoprime: Difference between revisions
imported>Karsten Meyer m (→Introduction) |
imported>Karsten Meyer mNo edit summary |
||
Line 28: | Line 28: | ||
|- | |- | ||
|<math>V_n(P,Q) - P\ </math> is divisible by <math>n\ </math> | |<math>V_n(P,Q) - P\ </math> is divisible by <math>n\ </math> | ||
|} | |||
== Table of smallest Pseudoprimes == | |||
{| border="1" cellspacing="0" | |||
!colspan="3" align="center"|smallest Pseudoprimes | |||
|- | |||
!Number !!Kind of Pseudoprime !!Bases | |||
|- | |||
|15 ||Fermat pseudoprime ||4, 15 | |||
|- | |||
|21 ||Euler pseudoprime ||8, 13 | |||
|- | |||
|49 ||strong pseudoprime ||18, 19, 30, 31 | |||
|- | |||
|561 ||Carmichael number || | |||
|- | |||
|1729 ||absolute Euler pseudoprime || | |||
|} | |} | ||
[[Category:Mathematics Workgroup]] | [[Category:Mathematics Workgroup]] | ||
[[Category:CZ Live]] | [[Category:CZ Live]] |
Revision as of 05:05, 6 February 2008
A pseudoprime is a composite number that has certain properties in common with prime numbers.
Introduction
If you want to find out if a given number is a prime number, you can to test it based on some properties that all prime numbers share. A property of prime numbers is that they are only divisible by one and itself. This is a defining property: it holds for all prime numbers and no other numbers.
However, other properties hold for all prime numbers and also some other numbers. For instance, every prime number, greater than 3, has the form or (with n an integer), but there are also composite numbers of this form: 25, 35, 49, 55, 65, 77, 85, 91, … . So, you could say that 25, 35, 49, 55, 65, 77, 85, 91, … are pseudoprimes with respect to the property of being of the form or . There exist better properties, which lead to special pseudoprimes:
Different kinds of pseudoprimes
Property | kind of pseudoprime |
---|---|
Fermat pseudoprime | |
Euler pseudoprime | |
strong pseudoprime | |
is divisible by | Carmichael number |
is divisible by | Perrin pseudoprime |
is divisible by |
Table of smallest Pseudoprimes
smallest Pseudoprimes | ||
---|---|---|
Number | Kind of Pseudoprime | Bases |
15 | Fermat pseudoprime | 4, 15 |
21 | Euler pseudoprime | 8, 13 |
49 | strong pseudoprime | 18, 19, 30, 31 |
561 | Carmichael number | |
1729 | absolute Euler pseudoprime |