Pseudoprime: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Jitse Niesen
(rewrite intro)
imported>Karsten Meyer
Line 9: Line 9:
== Different kinds of pseudoprimes ==
== 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]]

Revision as of 18:59, 29 January 2008

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

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 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