This site is supported by donations to The OEIS Foundation.

Carmichael numbers

From OeisWiki
(Redirected from Absolute Fermat pseudoprimes)
Jump to: navigation, search


This article needs more work.

Please help by expanding it!


The Carmichael numbers (A002997) are composite numbers
n
which divide
bn  −  b
for every integer
b
, or equivalently Carmichael numbers have the property that
bn  − 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).[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
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[2]

Mk (m)  =  (6 m + 1)  (12 m + 1)
k  − 2
i   = 1
  
(9 ⋅  2i m + 1), k ≥ 3,
with the condition that each of the factors are prime and that
m
is divisible by
2k  − 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
10n, 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
pq
is a Carmichael number. Then
pq  −  1
is divisible by
p  −  1
and by
q  −  1
. So
0   ≡   pq  −  1   ≡   pq  −  1  −  q (  p  −  1)   ≡   pq  −  1  −  (  pq  −  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 = pqr
, where
p < q < r
are primes such that
an  − 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 = pqrs
, where
p < q < r < s
are primes such that
an  − 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 ⋅  2i 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


References

  1. Richard G.E. Pinch, The Carmichael numbers up to 10 21, Feb 2008.
  2. Paulo Ribenboim, The new book of prime number records, Springer-Verlag (1996) ISBN 0-387-94457-5, p. 120.