Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Carmichael number
Summary
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 .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.