Fermat pseudoprimes are composite numbers that pass the Fermat primality test for a specific base, but are not actually prime numbers.
The Fermat primality test is a probabilistic test used to determine if a number is likely prime or composite. It is based on Fermat's Little Theorem, which states that if a number p is prime, then for any base a, a^(p-1) is congruent to 1 mod p.
Fermat pseudoprimes are important because they demonstrate that the Fermat primality test is not a foolproof method for determining primality. They also have applications in cryptography and number theory.
Fermat pseudoprimes exist for all odd bases in the range 2 to (p-1)/2, where p is the pseudoprime being tested. In other words, if p is the number being tested and it is a Fermat pseudoprime, then it will pass the test for all odd bases between 2 and (p-1)/2.
Fermat pseudoprimes can be distinguished from actual prime numbers by using other primality tests, such as the Miller-Rabin test or the Lucas-Lehmer test. These tests have a higher probability of correctly identifying primes and can be used to verify the primality of a number that has passed the Fermat test for a specific base.