Carmichael numbers

This article needs more work.

Please help by expanding it!

The Carmichael numbers (A002997) are composite numbers

n

which divide

b n  −  b

for every integer

b

, or equivalently Carmichael numbers have the property that

b n  − 1   ≡   1  (mod n)

for all bases

b

coprime to

n

. They are named for Robert Daniel Carmichael. Carmichael numbers are sometimes also called absolute Fermat pseudoprimes. For example, 561 = 3 ⋅  11 ⋅  17, so 561 is a Fermat pseudoprime for all bases

b

coprime to 3, 11, 17.

Every Carmichael number is squarefree and has at least three different prime factors.

Korselt’s criterion (1899). For every Carmichael number

n

it holds that

n  −  1

is divisible by

pi  −  1, 1   ≤   i   ≤   ω (n)

, i.e. by every one of its prime factors

pi

.

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 21 (approximately one in 50 billion numbers).

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

m

, the three numbers

6 m + 1

,

12 m + 1

and

18 m + 1

are prime numbers, the product

M 3 (m) = (6 m + 1)  (12 m + 1)  (18 m + 1)

is a 3-Carmichael number (A033502). This condition can only be satisfied if the number

m

ends with digits 0, 1, 5 or 6 in base 10 (i.e.

m

is congruent to 0 or 1 modulo 5). An equivalent formulation of Chernick’s construction is that if

p

,

2 p  −  1

and

3 p  −  2

are prime numbers congruent to 1 modulo 6, then the product

p  (2p  −  1)  (3p  −  2)

is a 3-Carmichael number.

Incidentally, the Hardy–Ramanujan number, e.g. 1729 = 7 ⋅  13 ⋅  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 to

M k (m)  =  (6 m + 1)  (12 m + 1)   k  − 2 ∏   i   = 1    (9 ⋅  2 i m + 1), k ≥ 3,

with the condition that each of the factors are prime and that

m

is divisible by

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, ...}

A317126 Extended Chernick Carmichael numbers.

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

2-Carmichael numbers related sequences

Corollary C2.

There are no Carmichael numbers with exactly 2 prime factors.

Proof. Suppose

p

and

q

are primes such that

p q

is a Carmichael number. Then

p q  −  1

is divisible by

p  −  1

and by

q  −  1

. So

0   ≡   p q  −  1   ≡   p q  −  1  −  q (  p  −  1)   ≡   p q  −  1  −  (  p q  −  q)   ≡   q  −  1  (mod p  −  1)

and so

(  p  −  1) ∣ (q  −  1)

but also (by symmetry)

(q  −  1) ∣ (  p  −  1)

. So

p = q

which contradicts the fact that Carmichael numbers are squarefree. Thus there are no 2-Carmichael numbers, i.e. with exactly 2 prime factors. □

3-Carmichael numbers related sequences

A087788 3-Carmichael numbers, i.e. Carmichael numbers equal to the product of 3 primes:

n = p q r

, where

p < q < r

are primes such that

a n  − 1   ≡   1  (mod n)

if

a

is prime to

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

6 m + 1

,

12 m + 1

and

18 m + 1

.

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

A046025 Numbers

n

such that

6 n + 1

,

12 n + 1

and

18 n + 1

are all primes (thus

(6 n + 1)  (12 n + 1)  (18 n + 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

n

such that

2 n  −  1

and

3 n  −  2

are prime (except for

n = 3

giving {3, 5, 7} and where 105 = 3 ⋅  5 ⋅  7 is not a 3-Carmichael number, all are congruent to 1 modulo 6 where

n (2 n  −  1)  (3 n  −  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, ...}

n-Carmichael numbers related sequences (n > 3)

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, ...}

A074379 4-Carmichael numbers, i.e. Carmichael numbers equal to the product of 4 primes:

n = p q r s

, where

p < q < r < s

are primes such that

a n  − 1   ≡   1  (mod n)

if

a

is prime to

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, 192739365541, 461574735553, 10028704049893, 84154807001953, 197531244744661, 973694665856161, 3060522900274753, 3183276534603733, 11861640972220321, 26862493078871893, ...}

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, ...}

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, ...}

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, ...}

A112430 Carmichael numbers equal to the product of 7 primes.

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

A112431 Carmichael numbers equal to the product of 8 primes.

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

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	ω (C (n))	Extended Chernick’s Carmichael numbers Mk (m) = (6 m + 1) (12 m + 1) ∏ k  − 2 i   = 1 (9 ⋅  2 i m + 1), m   ≥   1.
1	561	3 ⋅  11 ⋅  17	3
2	1105	5 ⋅  13 ⋅  17	3
3	1729	7 ⋅  13 ⋅  19	3	M 3 (1)
4	2465	5 ⋅  17 ⋅  29	3
5	2821	7 ⋅  13 ⋅  31	3
6	6601	7 ⋅  23 ⋅  41	3
7	8911	7 ⋅  19 ⋅  67	3
8	10585	5 ⋅  29 ⋅  73	3
9	15841	7 ⋅  31 ⋅  73	3
10	29341	13 ⋅  37 ⋅  61	3
11	41041	7 ⋅  11 ⋅  13 ⋅  41	4
12	46657	13 ⋅  37 ⋅  97	3
13	52633	7 ⋅  73 ⋅  103	3
14	62745	3 ⋅  5 ⋅  47 ⋅  89	4
15	63973	7 ⋅  13 ⋅  19 ⋅  37	4	M 4 (1)
16	75361	11 ⋅  13 ⋅  17 ⋅  31	4
17	101101	7 ⋅  11 ⋅  13 ⋅  101	4
18	115921	13 ⋅  37 ⋅  241	3
19	126217	7 ⋅  13 ⋅  19 ⋅  73	4
20	162401	17 ⋅  41 ⋅  233	3
21	172081	7 ⋅  13 ⋅  31 ⋅  61	4
22	188461	7 ⋅  13 ⋅  19 ⋅  109	4
23	252601	41 ⋅  61 ⋅  101	3
24	278545	5 ⋅  17 ⋅  29 ⋅  113	4
25	294409	37 ⋅  73 ⋅  109	3	M 3 (6)
26	314821	13 ⋅  61 ⋅  397	3
27	334153	19 ⋅  43 ⋅  409	3
28	340561	13 ⋅  17 ⋅  23 ⋅  67	4
29	399001	31 ⋅  61 ⋅  211	3
30	410041	41 ⋅  73 ⋅  137	3
31	449065	5 ⋅  19 ⋅  29 ⋅  163	4
32	488881	37 ⋅  73 ⋅  181	3

See also

• Fermat pseudoprimes
• Euler pseudoprimes
• Absolute Euler pseudoprimes

• Tabelle Carmichael-Zahlen
• Tabelle Carmichael-Zahlen nach Chernick