Fermat pseudoprime

A natural number n is Fermat pseudoprime (base a) identify if it is a composite number that behaves in relation to a relatively prime to n in base a like a prime number: namely, if the congruence

Is satisfied for the coprime to n number a.

In other words, n must divide the difference.

For example, 341 is a Fermat pseudoprime to the base 2, since 341 is a divisor of, but because 341 = 11:31 is not prime.

A Fermat pseudoprime is pseudoprime with respect to the criterion of Fermat's little theorem. This criterion is used in the Fermat primality test.

Definition

A Fermat pseudoprime to the base a is a composite natural number n for which

Applies. With respect to the base A, n behaves as a primary number.

Example: The number 91 is a Fermat pseudoprime with respect to the bases 17, 29 and 61, as, and through 91 are divisible. Although the number 91 is not prime ( 91 = 7.13), so they met for some a small Fermat's theorem.

Classes and Properties

The Fermat pseudoprimes include the Carmichael numbers, the Euler pseudo- prime numbers and the absolute Euler pseudo- prime numbers.

If n is a Fermat pseudoprime to the base a, then also the base ak and a kn ( k> 1), and - if n is odd and a < n - n to the base - a

The consequences of Fermat pseudo prime numbers to the bases 2, 3 and 5

There are infinitely many Fermat pseudoprimes to each base. These are, for example,

Base 2

Base 3

Base 5

Construction of infinitely many Fermat pseudoprimes to each base

Michele Cipolla constructed in 1904 in the following manner infinitely many Fermat pseudoprimes to each base:

For each a > 1 and every odd prime p which does not divide, is

A Fermat pseudoprime to the base a, since there are infinitely many primes, it must therefore give pseudoprimes also to each base infinitely many Fermat. Examples: