Strong pseudoprime

An odd natural number n is called a strong pseudoprime if it is a composite number that behaves with respect to a common factor with its base as a prime: to write ( with d odd), it must be one of the congruences

Or

Be satisfied for some r with 0 ≤ r

A strong pseudo prime number is a pseudoprime with respect to a (repeatedly carried out and explained below ) consequence of the Fermat's little theorem.

Derivation

After Fermat's little theorem is true for any prime number p and for each to prime a:

(in words: p divides (p -1) -th power of a minus 1 ). Composite numbers that also have regard to a prime base a this property are called Fermat primes to base a pseudo Due

Applies to every (odd) prime p that one of the two factors on the right standing must be divisible by p ( is a product divisible by a prime, then one of the factors must be divisible by it ). This provides a more sensitive condition and leads to the concept of Eulerian pseudo- primes. The second factor can be split further, if (P-1 ) / 2 is an even number. In this case, one gets:

Applies now ( with d odd), so the process can be repeated a total of s times and obtained the statement that one of the p s 1 must divide factors. In congruence, this is the condition that is called at the beginning of the article ( they are also called strong Fermat congruence ). A strong pseudo- prime number is thus a pseudo- prime number with respect to the strong Fermat congruence.

Examples

For the Carmichael number 561 ( a Fermat pseudoprime with respect to all prime bases) applies:

And one finds the decomposition

As a basis we choose 2 If 561 is a prime number would be, then they would have one of the factors on the right share. Since the residues modulo 561 of 2k for k = 35, 70, 140, 280 equal to 263, 166, 67 and 1, 561 does not notify of the factors and thus the number is not prime.

This is the approach of Miller - Selfridge -Rabin primality tests. Since each number n is less than n strong pseudoprime for at most a quarter of the bases, there are no absolute strong pseudo prime numbers ( in contrast, there are those in the Eulerian and Fermat pseudo prime numbers - the latter being the aforementioned Carmichael numbers ).

There are to each base infinitely many strong pseudo prime numbers. Of the bases 2, 3 and 5 are the results:

Base 2

Base 3:

Base 5:

The smallest number that appears in all three episodes, is 25,326,001th For a prime test for small numbers is therefore sufficient testing to bases 2, 3 and 5