Pseudoprime

A pseudoprime number is a composite natural number that has certain properties in common with prime numbers, but is not itself a prime number . It is called the pseudoprime for this property. Since there are many possibilities for such properties, the term pseudoprime does not make sense without specifying the property.

A historically significant example of a pseudoprime number is the number . It is a Fermatian pseudoprime to the base (and some other bases too). ${\displaystyle 341=11\cdot 31}$ ${\displaystyle 2}$

background

Pseudoprimes arose from the need to find algorithms that can reliably tell whether a number is a prime number or not (see Fermatscher prime number test , Lucas test , Solovay-Strassen test and Miller-Rabin test ). Since these algorithms are not perfect, you also get numbers that are not prime numbers, but still behave like prime numbers in relation to a special algorithm. In order to optimize the algorithms for searching for prime numbers, these pseudoprimes are also examined more closely.

A significant class of pseudoprimes is derived from the Fermat little theorem . The corresponding numbers are therefore also called Fermatsche pseudoprimes .

Types of pseudoprimes

Fermatsche pseudoprimes

→ Main article : Fermatsche pseudoprime number

According to Fermat's little theorem , for every prime number for every primordial basis that is. ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle a}$ ${\displaystyle a^{p-1}\equiv 1\mod p}$

A composite natural number n is called Fermat's pseudoprime for the base if and are relatively prime to each other and the same congruence is fulfilled as with a prime number: ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle n}$

${\displaystyle a^{n-1}\equiv 1\mod n}$

The first example was found by Sarrus in 1819 : the number is divisible by, although it is a compound. ${\displaystyle 2^{341-1}-1}$ ${\displaystyle 341}$ ${\displaystyle 341=11\cdot 31}$

Relatives of the Fermat pseudoprimes

The Fermat pseudoprimes include the Carmichael numbers , Euler's pseudoprimes, and the strong pseudoprimes .

• Carmichael number:

  A Carmichael number is a pseudo Fermat primes for which for each to prime base with the following applies: ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle 1<a<n}$

  ${\displaystyle a^{n-1}\equiv 1\mod n}$

• Euler's pseudoprime:

  An odd composite natural number is called Euler's pseudoprime with base a if and are relatively prime to each other and ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle n}$

  ${\displaystyle a^{\frac {n-1}{2}}\equiv \pm 1\mod n}$

  applies.

  Every Euler base pseudoprime is a Fermat base pseudoprime. ${\displaystyle a}$

• Strong pseudoprime:

  An odd composite natural number is called a strong base pseudoprime if ${\displaystyle n=d\cdot 2^{s}+1}$ ${\displaystyle a}$

  ${\displaystyle a^{d}\equiv 1\mod n}$

  or

  ${\displaystyle a^{d\cdot 2^{r}}\equiv -1\mod n}$

  applies to a with . ${\displaystyle r}$ ${\displaystyle 0\leq r<s}$

  Every strong pseudoprime to the base is an Euler pseudoprime to the same base. ${\displaystyle a}$

Perrinian pseudoprimes

The recursively defined Perrin sequence has the property that for every prime number the -th term in the sequence is divisible by . Perrinian pseudoprimes are natural numbers for which the -th member P _n is divisible by , although it is composite. The smallest Perrin pseudoprime is . ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle P_{p}}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle 271441=521^{2}}$

More pseudoprimes

• Euler-Jacobian pseudoprimes
• Fibonacci pseudoprimes, Lucassian pseudoprimes , Somer-Lucassian pseudoprimes, and strong Lucassian pseudoprimes
• Frobenius pseudoprimes and strong Frobenius pseudoprimes

literature

• Paul Erdős and Carl Pomerance : On the Number of False Witnesses for a Composite Number. Mathematics of Computation 46 , 259-279, 1986.
• Carl Pomerance: The Search for Prime Numbers. Scientific American 12/1982.
  German translation: Prime numbers in the rapid test. Spectrum of Science 02/1983. With a photo of a replica of Lehmer's bike chain computer from 1926.
• Carl Pomerance: Computational Number Theory. In: Timothy Gowers (Ed.): The Princeton companion to mathematics. Pp. 348–362, Princeton University Press, 2008 ( online ; PDF; 249 kB).
• Paulo Ribenboim : The New Book of Prime Number Records. Springer-Verlag, 1996.

Web links

Wikibooks: Pseudoprime Numbers  - Learning and Teaching Materials

• Pseudoprimes. At: mathe-schule.de. (PDF; 89 kB).
• Final Answers. Modular arithmetic. At: numericana.com.