Carmichael number

related topics
{math, number, function}
{rate, high, increase}

In number theory, a Carmichael number is a composite positive integer n which satisfies the congruence

for all integers b which are relatively prime to n (see modular arithmetic). They are named for Robert Carmichael. The Carmichael numbers are the Knödel numbers K1.

Contents

Overview

Fermat's little theorem states that all prime numbers have the above property. In this sense, Carmichael numbers are similar to prime numbers; in fact, they are called Fermat pseudoprimes. Carmichael numbers are sometimes also called absolute Fermat pseudoprimes.

Carmichael numbers are important because they pass the Fermat primality test but are not actually prime. Since Carmichael numbers exist, this primality test cannot be relied upon to prove the primality of a number, although it can still be used to prove a number is composite.

Still, as numbers become larger, Carmichael numbers become very rare. For example, there are 20,138,200 Carmichael numbers between 1 and 1021 (approximately one in 50 billion numbers.)[1] This makes tests based on Fermat's Little Theorem slightly risky compared to others such as the Solovay-Strassen primality test.

Korselt's criterion

An alternative and equivalent definition of Carmichael numbers is given by Korselt's criterion.

It follows from this theorem that all Carmichael numbers are odd, since any even composite number that is square-free (and hence has only one prime factor of two) will have at least one odd prime factor, and thus p − 1 | n − 1 results in an even dividing an odd, a contradiction. (This is also easily seen from the fact that − 1 is a Fermat witness for any even number.)

Discovery

Korselt was the first who observed the basic properties of Carmichael numbers, but he could not find any examples. In 1910, Carmichael found the first and smallest such number, 561, and hence the name "Carmichael number".

Full article ▸

related documents
Goodstein's theorem
Well-order
Local ring
Diophantine set
Group representation
Kolmogorov space
Convex set
Lebesgue measure
Laurent series
Controllability
Cartesian product
Euler's totient function
Kruskal's algorithm
Axiom of regularity
Conjunctive normal form
Symmetric group
Generalized Riemann hypothesis
Monotonic function
Mersenne twister
Golomb coding
Algebraic topology
Analytic geometry
Diffeomorphism
Automated theorem proving
Isomorphism theorem
Tree (data structure)
Search algorithm
Constant of integration
Exact sequence
Differential topology