Carmichael numbers

From OeisWiki

Current revision (unreviewed)

This article needs more work.

Please help by expanding it!

The Carmichael numbers (A002997) are composite numbers $\scriptstyle n \,$ which divide $\scriptstyle b^n - b \,$ for every integer $\scriptstyle b \,$ , or equivalently Carmichael numbers have the property that $\scriptstyle b^{n-1} \,\equiv\, 1 \pmod n \,$ for all bases $\scriptstyle b \,$ coprime to $\scriptstyle n \,$ . They are named for Robert Daniel Carmichael. Carmichael numbers are sometimes also called absolute Fermat pseudoprimes.

For example, $\scriptstyle 561 \,=\, 3 \cdot 11 \cdot 17 \,$ , so 561 is a Fermat pseudoprime for all bases $\scriptstyle b \,$ coprime to 3, 11, 17.

Every Carmichael number is square-free and has at least three different prime factors.

Korselt's criterion (1899). For every Carmichael number $\scriptstyle n \,$ it holds that $\scriptstyle n-1 \,$ is divisible by $\scriptstyle p_i-1,\ 1 \,\le\, i \,\le\, \omega(n) \,$ , i.e. by every one of its prime factors $\scriptstyle p_i \,$ .

The second Carmichael number (1105) can be expressed as the sum of two squares in more ways than any smaller number. The third Carmichael number (1729) is the Hardy-Ramanujan number: the smallest number that can be expressed as the sum of two cubes in two different ways (and thus can be expressed as the sum of two cubes in more ways than any smaller number.)

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 10²¹ (approximately one in 50 billion numbers.)^[1]

Chernick's Carmichael numbers

In 1939 J. Chernick found a way to construct members of a subset of 3-Carmichael numbers. If, for a natural number $\scriptstyle m \,$ , the three numbers $\scriptstyle 6m+1 \,$ , $\scriptstyle 12m+1 \,$ and $\scriptstyle 18m+1 \,$ are prime numbers, the product $\scriptstyle M_3(m) \,=\, (6m+1) \cdot (12m+1) \cdot (18m+1) \,$ is a 3-Carmichael number (Cf. A033502.) This condition can only be satisfied if the number $\scriptstyle m\,$ ends with digits 0, 1, 5 or 6 in base 10 (i.e. $\scriptstyle m \,$ is congruent to 0 or 1 modulo 5.)

An equivalent formulation of Chernick's construction is that if $\scriptstyle p \,$ , $\scriptstyle 2p-1 \,$ and $\scriptstyle 3p-2 \,$ are prime numbers congruent to 1 modulo 6, then the product $\scriptstyle p \cdot (2p-1) \cdot (3p-2) \,$ is a 3-Carmichael number.

By the way, the Hardy-Ramanujan number, e.g. $\scriptstyle 1729 \,=\, 7 \cdot 13 \cdot 19 \,$ , is the third Carmichael number and the first Chernick Carmichael number!

Extended Chernick's Carmichael numbers

This way to construct Carmichael numbers may be extended^[2] to

$M_k(m) = (6m+1) (12m+1) \prod_{i=1}^{k-2} (9 \cdot 2^i m+1),\ k \,\ge\, 3, \,$

with the condition that each of the factors are prime and that $\scriptstyle m \,$ is divisible by $\scriptstyle 2^{k-4} \,$ .

Sequences

Carmichael numbers related sequences

A002997 Carmichael numbers.

{561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, ...}

A055553 Number of Carmichael numbers less than 10^$n$, $n$ ≥ 1.

{0, 0, 1, 7, 16, 43, 105, 255, 646, 1547, 3605, 8241, 19279, 44706, 105212, 246683, 585355, 1401644, 3381806, 8220777, 20138200, ...}

A006931 Least Carmichael number with $n$ prime factors, $n$ ≥ 3.

{561, 41041, 825265, 321197185, 5394826801, 232250619601, 9746347772161, 1436697831295441, 60977817398996785, 7156857700403137441, 1791562810662585767521, ...}

A?????? extended Chernick Carmichael numbers.

{1729, 63973, 294409, ...}

2-Carmichael numbers related sequences

There are no 2-Carmichael numbers, i.e. with exactly 2 prime factors, since Carmichael numbers must have at least 3 prime factors.

3-Carmichael numbers related sequences

A087788 3-Carmichael numbers, i.e. Carmichael numbers equal to the product of 3 primes: $\scriptstyle n \,=\, pqr \,$ , where $\scriptstyle p \,<\, q \,<\, r \,$ are primes such that $\scriptstyle a^{n-1} \,\equiv\, 1 \pmod n \,$ if $\scriptstyle a \,$ is prime to $\scriptstyle n \,$ .

{561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 46657, 52633, 115921, 162401, 252601, 294409, 314821, 334153, 399001, 410041, 488881, 512461, 530881, 1024651, 1152271, 1193221, ...}

A033502 Chernick Carmichael numbers, i.e. 3-Carmichael numbers which are the product of 3 primes of form $\scriptstyle 6m+1 \,$ , $\scriptstyle 12m+1 \,$ and $\scriptstyle 18m+1 \,$ .

{1729, 294409, 56052361, 118901521, 172947529, 216821881, 228842209, 1299963601, 2301745249, 9624742921, 11346205609, 13079177569, 21515221081, 27278026129, 65700513721, 71171308081, ...}

A046025 Numbers $\scriptstyle n \,$ such that $\scriptstyle 6n+1 \,$ , $\scriptstyle 12n+1 \,$ and $\scriptstyle 18n+1 \,$ are all primes (thus $\scriptstyle (6n+1)(12n+1)(18n+1) \,$ being Chernick Carmichael numbers).

{1, 6, 35, 45, 51, 55, 56, 100, 121, 195, 206, 216, 255, 276, 370, 380, 426, 506, 510, 511, 710, 741, 800, 825, 871, 930, 975, 1025, 1060, 1115, 1140, 1161, 1270, 1280, 1281, 1311, 1336, 1361, ...}

A174734 Prime numbers $\scriptstyle n \,$ such that $\scriptstyle 2n-1 \,$ and $\scriptstyle 3n-2 \,$ are prime (except for $\scriptstyle n \,$ = 3 giving {3, 5, 7} and where $\scriptstyle 105 \,=\, 3 \cdot 5 \cdot 7 \,$ is not a 3-Carmichael number, all are congruent to 1 modulo 6 where $\scriptstyle n(2n-1)(3n-2) \,$ are Chernick Carmichael numbers).

{3, 7, 37, 211, 271, 307, 331, 337, 601, 727, 1171, 1237, 1297, 1531, 1637, 2221, 2281, 2557, 3037, 3061, 3067, 4261, 4447, 4801, 4951, 5227, 5581, 5851, 6151, 6361, 6691, 6841, 6967, 7621, 7681, ...}

A141711 Carmichael numbers with more than 3 prime factors.

{41041, 62745, 63973, 75361, 101101, 126217, 172081, 188461, 278545, 340561, 449065, 552721, 656601, 658801, 670033, 748657, 825265, 838201, 852841, 997633, 1033669, 1050985, 1082809, 1569457, ...}

4-Carmichael numbers related sequences

A074379 4-Carmichael numbers, i.e. Carmichael numbers equal to the product of 4 primes: $\scriptstyle n \,=\, pqrs \,$ , where $\scriptstyle p \,<\, q \,<\, r \,<\, s\,$ are primes such that $\scriptstyle a^{n-1} \,\equiv\, 1 \pmod n \,$ if $\scriptstyle a \,$ is prime to $\scriptstyle n \,$ .

{41041, 62745, 63973, 75361, 101101, 126217, 172081, 188461, 278545, 340561, 449065, 552721, 656601, 658801, 670033, 748657, 838201, 852841, 997633, 1033669, 1082809, 1569457, 1773289, 2100901, ...}

A?????? extended Chernick 4-Carmichael numbers.

{63973, ...}

A?????? Carmichael numbers with more than 4 prime factors. (Below 321197185, first Carmichael number with 6 prime factors, same as 5-Carmichael numbers.)

{825265, 1050985, 9890881, 10877581, 12945745, 13992265, 16778881, 18162001, 27336673, 28787185, 31146661, 36121345, 37167361, 40280065, 41298985, 41341321, 41471521, ...}

5-Carmichael numbers related sequences

A112428 Carmichael numbers equal to the product of 5 primes.

{825265, 1050985, 9890881, 10877581, 12945745, 13992265, 16778881, 18162001, 27336673, 28787185, 31146661, 36121345, 37167361, 40280065, 41298985, 41341321, 41471521, ...}

6-Carmichael numbers related sequences

A112429 Carmichael numbers equal to the product of 6 primes.

{321197185, 413631505, 417241045, 496050841, 509033161, 611397865, 612347905, 638959321, 672389641, 832060801, 834720601, 868234081, 945959365, 986088961, 1074363265, 1177800481, ...}

7-Carmichael numbers related sequences

A112430 Carmichael numbers equal to the product of 7 primes.

{5394826801, 6295936465, 12452890681, 13577445505, 15182481601, 20064165121, 22541365441, 24673060945, 26242929505, 26602340401, 27405110161, 28553256865, 33203881585, 38059298641, ...}

8-Carmichael numbers related sequences

A112431 Carmichael numbers equal to the product of 8 primes.

{232250619601, 306177962545, 432207073585, 576480525985, 658567396081, 689702851201, 747941832001, 1013666981041, 1110495895201, 1111586883121, 1286317859905, 1292652236161, ...}

9-Carmichael numbers related sequences

A112432 Carmichael numbers equal to the product of 9 primes.

{9746347772161, 11537919313921, 11985185775745, 14292786468961, 23239986511105, 24465723528961, 26491881502801, 27607174936705, 30614445878401, 30912473358481, 34830684315505, ...}

Carmichael numbers prime factorization

**Carmichael numbers prime factorization**
$n \,$	$C(n) \,$	Prime factorization	$\omega(C(n)) \,$	Chernick numbers (extended) $\scriptstyle M_k(m) \,=\, \,$ $\scriptstyle (6m+1) (12m+1) \prod_{i=1}^{k-2} (9 \cdot 2^i m + 1), \,$ $\scriptstyle m \ge 1. \,$
1	561	$3 \cdot 11 \cdot 17 \,$	3
2	1105	$5 \cdot 13 \cdot 17 \,$	3
3	1729	$7 \cdot 13 \cdot 19 \,$	3	$M_3(1)\,$
4	2465	$5 \cdot 17 \cdot 29 \,$	3
5	2821	$7 \cdot 13 \cdot 31 \,$	3
6	6601	$7 \cdot 23 \cdot 41 \,$	3
7	8911	$7 \cdot 19 \cdot 67 \,$	3
8	10585	$5 \cdot 29 \cdot 73 \,$	3
9	15841	$7 \cdot 31 \cdot 73 \,$	3
10	29341	$13 \cdot 37 \cdot 61 \,$	3
11	41041	$7 \cdot 11 \cdot 13 \cdot 41 \,$	4
12	46657	$13 \cdot 37 \cdot 97 \,$	3
13	52633	$7 \cdot 73 \cdot 103 \,$	3
14	62745	$3 \cdot 5 \cdot 47 \cdot 89 \,$	4
15	63973	$7 \cdot 13 \cdot 19 \cdot 37 \,$	4	$M_4(1)\,$
16	75361	$11 \cdot 13 \cdot 17 \cdot 31 \,$	4
17	101101	$7 \cdot 11 \cdot 13 \cdot 101 \,$	4
18	115921	$13 \cdot 37 \cdot 241 \,$	3
19	126217	$7 \cdot 13 \cdot 19 \cdot 73 \,$	4
20	162401	$17 \cdot 41 \cdot 233 \,$	3
21	172081	$7 \cdot 13 \cdot 31 \cdot 61 \,$	4
22	188461	$7 \cdot 13 \cdot 19 \cdot 109 \,$	4
23	252601	$41 \cdot 61 \cdot 101 \,$	3
24	278545	$5 \cdot 17 \cdot 29 \cdot 113 \,$	4
25	294409	$37 \cdot 73 \cdot 109 \,$	3	$M_3(6)\,$
26	314821	$13 \cdot 61 \cdot 397 \,$	3
27	334153	$19 \cdot 43 \cdot 409 \,$	3
28	340561	$13 \cdot 17 \cdot 23 \cdot 67 \,$	4
29	399001	$31 \cdot 61 \cdot 211 \,$	3
30	410041	$41 \cdot 73 \cdot 137 \,$	3
31	449065	$5 \cdot 19 \cdot 29 \cdot 163 \,$	4
32	488881	$37 \cdot 73 \cdot 181 \,$	3

References

↑ Richard Pinch, The Carmichael numbers up to 10²¹, May 2007.
↑ Paulo Ribenboim, The new book of prime number records, Springer-Verlag (1996) ISBN 0-387-94457-5, p. 120.

[Pinch2007-0] Richard Pinch, The Carmichael numbers up to 10²¹, May 2007.

[1] Paulo Ribenboim, The new book of prime number records, Springer-Verlag (1996) ISBN 0-387-94457-5, p. 120.

[1]

[2]

Carmichael numbers

From OeisWiki

Contents