Carmichael number
E530314
A Carmichael number is a composite integer that nonetheless satisfies Fermat's primality test for all bases coprime to it, making it a classic example of a Fermat pseudoprime.
Statements (47)
| Predicate | Object |
|---|---|
| instanceOf |
mathematical concept
ⓘ
number theory concept ⓘ |
| characterization |
n is Carmichael iff it is composite and for every integer a, a^n ≡ a (mod n)
ⓘ
n is Carmichael iff n is square-free, composite, and for every prime p dividing n, p−1 divides n−1 ⓘ |
| classification | subset of composite integers that are Fermat-liar to all coprime bases ⓘ |
| definition | a composite integer n such that a^(n−1) ≡ 1 (mod n) for all integers a coprime to n ⓘ |
| discoveredBy | Robert Daniel Carmichael NERFINISHED ⓘ |
| discoveryYear | 1910 ⓘ |
| example |
1105
ⓘ
1729 ⓘ 2465 ⓘ 2821 ⓘ 561 ⓘ 6601 ⓘ |
| factorizationExample |
1105 = 5 × 13 × 17
ⓘ
1729 = 7 × 13 × 19 ⓘ 561 = 3 × 11 × 17 ⓘ |
| field | number theory ⓘ |
| growth | number of Carmichael numbers up to x grows faster than x^c for some c<1 ⓘ |
| isA |
Fermat pseudoprime
ⓘ
composite integer ⓘ |
| namedAfter | Robert Carmichael NERFINISHED ⓘ |
| property |
every Carmichael number has at least three distinct prime factors
ⓘ
every Carmichael number is square-free ⓘ for each Carmichael number n and each prime p dividing n, n ≡ 1 (mod p−1) ⓘ for each Carmichael number n, λ(n) divides n−1, where λ is the Carmichael function ⓘ infinitely many exist ⓘ is a universal Fermat pseudoprime ⓘ is composite but behaves like a prime in Fermat’s little theorem for coprime bases ⓘ no product of two distinct primes is a Carmichael number ⓘ passes Fermat primality test to every base coprime to it ⓘ set has asymptotic density 0 among positive integers ⓘ violates the converse of Fermat’s little theorem ⓘ |
| relatedConcept | Carmichael function NERFINISHED ⓘ |
| relatedTo |
Fermat primality test
NERFINISHED
ⓘ
Fermat’s little theorem NERFINISHED ⓘ composite number ⓘ prime number ⓘ pseudoprime ⓘ strong pseudoprime ⓘ |
| relation |
generalization of specific Fermat pseudoprimes to all coprime bases
ⓘ
subset of Fermat pseudoprimes ⓘ |
| smallestElement | 561 ⓘ |
| symbolicDefinition | n is Carmichael iff n is composite and a^(n−1) ≡ 1 (mod n) for all a with gcd(a,n)=1 ⓘ |
| theorem | Alford–Granville–Pomerance proved in 1994 that there are infinitely many Carmichael numbers NERFINISHED ⓘ |
| use |
demonstrates limitations of Fermat primality test
ⓘ
used as counterexamples in primality testing ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.