Pseudoprime: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Karsten Meyer
mNo edit summary
 
(14 intermediate revisions by 5 users not shown)
Line 1: Line 1:
A '''Pseudoprime''' is a composite number, which have with [[Prime number|Prime numbers]] common properties.
{{subpages}}
A '''pseudoprime''' is a composite number that has certain properties in common with [[prime number]]s.


==Introduce==
== Introduction ==
If you would find out if a number is a prime number, you have properties to test it. A property of prime numbers, that they are only divisible by one and itself. Some of the properties are not only true to prime numbers. So you can say, that every prime number has the form: <math>6n - 1\ </math> or <math>6n + 1\ </math>. Not only prime numbers has these form, but also the composite numbers 25, 35, 49, 55, 65, 77, 85, 91, ... .
To find out if a given number is a prime number, one can test it for properties that all prime numbers share. One property of a prime number is that it is only divisible by one and itself. This is a defining property: it holds for all primes and no other numbers.  
So, in relation of the property <math>6n - 1\ </math> or <math>6n + 1\ </math>, you could say, that 25, 35, 49, 55, 65, 77, 85, 91, ... are pseudoprimes. There exist better properties, wich leads to special pseudoprimes:


== Different kinds of Pseudoprimes ==
However, other properties hold for all primes and also some other numbers. For instance, every prime number greater than 3 has the form <math>6n - 1\ </math> or <math>6n + 1\ </math> (with ''n'' an integer), but there are also composite numbers of this form: 25, 35, 49, 55, 65, 77, 85, 91, &hellip; . So, we can say that 25, 35, 49, 55, 65, 77, 85, 91, &hellip; are pseudoprimes with respect to the property of being of the form <math>6n - 1\ </math> or <math>6n + 1\ </math>. There exist better properties, which lead to special pseudoprimes, as outlined below.
 
== Different kinds of pseudoprimes ==
{| border="1" cellspacing="0"
{| border="1" cellspacing="0"
|Property ||kind of Pseudoprime
!align="center"|Property !!kind of pseudoprime
|-
|-
|<math>a^{n-1} \equiv 1 \pmod{n}</math> ||[[Fermat pseudoprime]]
|<math>a^{n-1} \equiv 1 \pmod{n}</math> ||[[Fermat pseudoprime]]
Line 27: Line 29:
|<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, 11
|-
|21 ||Euler pseudoprime ||8, 13
|-
|49 ||strong pseudoprime ||18, 19, 30, 31
|-
|561 ||Carmichael number ||
|-
|1729 ||absolute Euler pseudoprime ||
|}[[Category:Suggestion Bot Tag]]

Latest revision as of 07:01, 8 October 2024

This article is a stub and thus not approved.
Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
This editable Main Article is under development and subject to a disclaimer.

A pseudoprime is a composite number that has certain properties in common with prime numbers.

Introduction

To find out if a given number is a prime number, one can test it for properties that all prime numbers share. One property of a prime number is that it is only divisible by one and itself. This is a defining property: it holds for all primes and no other numbers.

However, other properties hold for all primes 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, we can 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, as outlined below.

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, 11
21 Euler pseudoprime 8, 13
49 strong pseudoprime 18, 19, 30, 31
561 Carmichael number
1729 absolute Euler pseudoprime