Carmichael number

In number theory, a Carmichael number is a composite number , which in modular arithmetic satisfies the congruence relation: for all integers . The relation may also be expressed in the form: for all integers which are relatively prime to . Carmichael numbers are named after American mathematician Robert Carmichael, the term having been introduced by Nicolaas Beeger in 1950 (Øystein Ore had referred to them in 1948 as numbers with the "Fermat property", or "F numbers" for short). They are infinite in number. They constitute the comparatively rare instances where the strict converse of Fermat's Little Theorem does not hold. This fact precludes the use of that theorem as an absolute test of primality. The Carmichael numbers form the subset K1 of the Knödel numbers. Fermat's little theorem states that if is a prime number, then for any integer , the number is an integer multiple of . Carmichael numbers are composite numbers which have the same property. Carmichael numbers are also called Fermat pseudoprimes or absolute Fermat pseudoprimes. A Carmichael number will pass a Fermat primality test to every base relatively prime to the number, even though it is not actually prime. This makes tests based on Fermat's Little Theorem less effective than strong probable prime tests such as the Baillie–PSW primality test and the Miller–Rabin primality test. However, no Carmichael number is either an Euler–Jacobi pseudoprime or a strong pseudoprime to every base relatively prime to it so, in theory, either an Euler or a strong probable prime test could prove that a Carmichael number is, in fact, composite. Arnault gives a 397-digit Carmichael number that is a strong pseudoprime to all prime bases less than 307: where 29674495668685510550154174642905332730771991799853043350995075531276838753171770199594238596428121188033664754218345562493168782883 is a 131-digit prime. is the smallest prime factor of , so this Carmichael number is also a (not necessarily strong) pseudoprime to all bases less than .