# Carmichael number

A natural number is called a Carmichael number , named after the mathematician Robert Daniel Carmichael , if it is a Fermat pseudoprime number with respect to all bases that are relatively prime 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 , WR Alford, and Andrew Granville proved the existence of infinitely many Carmichael numbers.

It is easy to see a Carmichael Number knowing 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 the one according to J. Chernick exist. However, it is problematic - especially with large numbers - to recognize whether a number is a Carmichael number. The Carmichael numbers have this difficulty in common with the prime numbers, because either a factorization is carried out or the little Fermat's theorem is applied to the number, whereby the bases that do not point to a primality and that do not appear in prime numbers are used , must test for divisibility . In practice, distinguishing an undecomposed Carmichael number from a prime number is made easier by the fact that there are no strong Carmichael numbers. For every Carmichael number one can always find a coprime basis , so that the prime number property (using the Jacobi symbol and the notation for congruence ) is violated. ${\ displaystyle n}$${\ displaystyle a}$${\ displaystyle a ^ {(n-1) / 2} \ equiv \ left ({\ tfrac {a} {n}} \ right) {\ pmod {n}}}$

## definition

Definition
A composite natural number is called a
Carmichael number if the following congruence is fulfilled for all coprime numbers here called "base": ${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle a,}$

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

Example
As mentioned, the smallest is Carmichael number. For all bases that have no prime factor in common, the following applies . ${\ displaystyle n: = 561 = 3 \ cdot 11 \ cdot 17}$${\ displaystyle a,}$${\ displaystyle n}$${\ displaystyle a ^ {n-1} \ equiv 1 {\ pmod {n}}}$

561 is divisible by 3, 11, 17, 33, 51, and 187. However, the congruence does not apply to these factors: 3 560 ≡ 375 mod 561, 11 560 ≡ 154 mod 561, 17 560 ≡ 34 mod 561, etc.

## Theorem of Korselt

Alwin Reinhold Korselt proved the following theorem as early as 1899 :

A natural number is a Carmichael number if and only if it is not prime and free of squares and all of its prime divisors are true that the number divides.${\ displaystyle n}$${\ displaystyle p}$${\ displaystyle p-1}$${\ displaystyle n-1}$

Tightening
due to the identity applies to every prime factor of a natural number : ${\ displaystyle n-1 = {\ frac {n} {p}} - 1+ (p-1) {\ frac {n} {p}}}$${\ displaystyle p}$${\ displaystyle n}$

${\ displaystyle 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 if and only if it applies to each of its prime divisors: divides . ${\ displaystyle n}$${\ displaystyle p-1}$${\ displaystyle {\ frac {n} {p}} - 1}$

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

## The sequence of the Carmichael numbers

Carmichael numbers have at least three prime factors, none of which are double. As mentioned in the introduction, it has been known since 1994 that there are an infinite number of Carmichael numbers.

The table shows the Carmichael numbers (sequence A002997 in OEIS ) below 100000 and relates them to the Carmichael function and the Euler's function . ${\ displaystyle \ lambda}$${\ displaystyle \ varphi}$

Carmichael number ${\ displaystyle n}$ Prime factors ${\ displaystyle \ lambda (n)}$ ${\ displaystyle (n-1) / \ lambda (n)}$ ${\ displaystyle \ varphi (n)}$ ${\ displaystyle \ varphi (n) / \ lambda (n)}$
561 3⋅11⋅17 80 7th 320 4th
1105 5-13-17 48 23 768 16
1729 7-13-19 36 48 1296 36
2465 5⋅17⋅29 112 22nd 1792 16
2821 7⋅1331 60 47 2160 36
6601 7⋅23⋅41 1320 5 5280 4th
8911 7⋅19⋅67 198 45 7128 36
10585 5⋅29⋅73 504 21st 8064 16
15841 7⋅31⋅73 360 44 12960 36
29341 13-37-61 180 163 25920 144
41041 7⋅11⋅13⋅41 120 342 28800 240
46657 13-37-97 288 162 41472 144
52633 7⋅73103 1224 43 44064 36
62745 3⋅5⋅47⋅89 2024 31 32384 16
63973 7⋅13⋅19⋅37 36 1777 46656 1296
75361 11⋅13⋅17⋅31 240 314 57600 240

## Generation of Carmichael Numbers

### Chernick's method

J. Chernick found a relatively simple system for constructing Carmichael numbers in 1939:

If the three numbers and are prime numbers, their product is a Carmichael number.${\ displaystyle 6m + 1.12m + 1}$${\ displaystyle 18m + 1}$${\ displaystyle (6m + 1) (12m + 1) (18m + 1)}$

For example, 1729 = 7 * 13 * 19 has this structure. It is interesting that the Carmichael number 172081 = 31 · 61 · 91 the condition “almost fulfilled”: 91 is not prime, but Fermat's pseudoprime to base 3.

### Michon's method

Gérard P. Michon found a similar method to construct Carmichael numbers:

If and the three are numbers and prime numbers, their product is a Carmichael number.${\ displaystyle m \ equiv 326 \ mod \ 616}$${\ displaystyle 7m + 1.8m + 1}$${\ displaystyle 11m + 1}$${\ displaystyle (7m + 1) (8m + 1) (11m + 1)}$

${\ displaystyle m}$must then be divisible by 3, otherwise one of the three factors is divisible by 3.
Example: for are the three numbers and are prime and their product is a Carmichael number. A Carmichael number with 1000 digits generated with this method is ${\ displaystyle m = 24966}$${\ displaystyle 174763,199729}$${\ displaystyle 274627}$

${\ displaystyle (12936 \ cdot 10 ^ {329} -59827428149) \ cdot (14784 \ cdot 10 ^ {329} -68374203599) \ cdot (20328 \ cdot 10 ^ {329} -94014529949).}$

Based on an idea by Paul Erdős , much larger Carmichael numbers can be constructed with the help of group theoretical considerations and modern computer algorithms. In July 2012, after extensive exhaustion of already known methods, a Carmichael number with more than 10 billion prime factors and almost 300 billion decimal places was presented.

## Asymptotic number

Erdős suspected as early as 1956 that there are many Carmichael numbers are infinite, and that their number is below a barrier no exponent exists with in any capacity . ${\ displaystyle C (x)}$${\ displaystyle x}$${\ displaystyle a <1}$${\ displaystyle C (x) ${\ displaystyle x}$

The proof of Alford / Granville / Pomerance provides the lower estimate of the number function for all sufficiently large . This result was improved in 2005 to be large enough . Calculations to suggest a growth with the lower estimate , so that Daniel Shanks was convinced that it was a very safe upper estimate for the number function. However, through discussion with the authors mentioned, he was convinced that Erdös' conjecture might correspond to the true asymptotics. In 2002, Granville and Pomerance published an analysis of the distribution of the Carmichael numbers on the basis of further plausible and well-founded assumptions, which provided a result (no proof) both in accordance with Erdős' argument and in accordance with the empirical results for small and thus that of Shank's highlighted apparent contradiction resolved. ${\ displaystyle C (x)> x ^ {2/7}}$${\ displaystyle x}$${\ displaystyle C (x)> x ^ {0.33}}$${\ displaystyle x}$${\ displaystyle x = 10 ^ {15}}$${\ displaystyle x ^ {1/3}}$${\ displaystyle x ^ {1/2}}$${\ displaystyle x}$

## swell

1. ^ WR Alford, A. Granville, C. Pomerance: There are Infinitely Many Carmichael Numbers , Ann. Math. 139 , 703-722, 1994.
2. ^ Derrick Henry Lehmer : Strong Carmichael numbers. J. Austral. Math. Soc. 21 (Series A) (1976), pp. 508-510
3. For (simple) proof see Eric W. Weisstein: "Carmichael number" (→ Weblinks).
4. Steven Hayman, Andrew Shallue: Constructing a ten billion factor Carmichael number (PDF file; 91 kB) Poster at the ANTS X conference, San Diego, July 2012
5. ^ See Crandall, Pomerance: Prime Numbers , p. 122
6. ^ Glyn Harman: On the number of Carmichael numbers up to x , Bull. London Math. Soc. 37 , 641-650, 2005.
7. ^ A. Granville, C. Pomerance: Two contradictory conjectures concerning Carmichael numbers. (PDF; 347 kB) Math. Comp. 71 (2002), No. 238, pp. 883-908