Carmichael number

A natural number is called a Carmichael number, named after the mathematician Robert Daniel Carmichael, if it is a Fermatian pseudoprime with respect to all bases that are alien to it. Carmichael numbers play a role in the analysis of primality tests.

Every Carmichael number is square-free and the product of at least three prime numbers. The smallest Carmichael number is the number 561 = 3-11-17. In 1994 Carl Pomerance, W. R. Alford and Andrew Granville proved the existence of infinitely many Carmichael numbers.

It is easy to recognize a Carmichael number if you know its prime factorization. This is thanks to Korselt's theorem (see below). It is also relatively easy to generate Carmichael numbers, especially since algorithms like J. Chernick's exist. But it is problematic - especially with large numbers - to recognize whether a number is a Carmichael number. Carmichael numbers have this difficulty in common with prime numbers, because either a factorization is performed or the small Fermat theorem is applied to the number, in which case one must test for divisibility for the bases that do not point to a primality and do not occur in prime numbers. In practice, distinguishing an undecomposed Carmichael number from a prime is made easier by the fact that there are no strong Carmichael numbers. One can always find a divisible base a for any Carmichael number the prime number property $a^{(n-1)/2}\equiv \left({\tfrac {a}{n}}\right){\pmod {n}}$ (using the Jacobi symbol and notation for congruence) is violated.

Definition

DefinitionA
composite natural number is called a Carmichael number if the following congruence is satisfied for all numbers $a,$ here called "basis", that are divisible from

$a^{n-1}\equiv 1{\pmod {n}}$ .

ExampleAs
mentioned, $n:=561=3\cdot 11\cdot 17$
is the smallest Carmichael number. Namely, for all bases $a,$ which have no prime factor in common with , $a^{n-1}\equiv 1{\pmod {n}}$ .

561 is divisible by 3, 11, 17, 33, 51, and 187. However, congruence does not hold for these divisors: ³⁵⁶⁰ ≡ 375 mod 561, ¹¹⁵⁶⁰ ≡ 154 mod 561, ¹⁷⁵⁶⁰ ≡ 34 mod 561, etc.

Theorem of Korselt

Already in 1899 Alwin Reinhold Korselt proved the following theorem:

A natural number is a Carmichael number if and only if it is not prime and square-free and for all its prime divisors holds that p-1 n-1 divides the number

TighteningBecause of
the identity $n-1={\frac {n}{p}}-1+(p-1){\frac {n}{p}}$ holds for any prime divisor a natural number :

$n-1\equiv {\frac {n}{p}}-1{\pmod {p-1}}.$

Thus the second part of Korselt's theorem can also be formulated as: A number is a Carmichael number exactly if for each of its prime divisors holds: p-1 divides ${\frac {n}{p}}-1$ .

Carmichael then in 1910 found the first number, 561, which satisfies the properties of Korselt 's theorem.

Carmichael number

Definition

Theorem of Korselt

Search by letter