THE CARMICHAEL NUMBERS UP TO 1021
RICHARD G.E. PINCH

Abstract. We extend our previous computations to show that there are 20138200
Carmichael numbers up to 1021 . As before, the numbers were generated
by a back-tracking search for possible prime factorisations together with a“large prime variation”. We present further statistics on the distribution ofCarmichael numbers.

1. Introduction
A Carmichael number N is a composite number N with the property that forevery b prime to N we have bN −1 ≡ 1 mod N . It follows that a Carmichael number
N must be square-free, with at least three prime factors, and that p − 1|N − 1 forevery prime p dividing N : conversely, any such N must be a Carmichael number.
For background on Carmichael numbers and details of previous computations werefer to our previous paper [1]: in that paper we described the computation of theCarmichael numbers up to 1015 and presented some statistics. These computations
have since been extended to 1016 [2], 1017 [3], 1018 [4] and now to 1021 , using similar
techniques, and we present further statistics.
2. Organisation of the search
We used improved versions of strategies first described in [1].
The principal search was a depth-first back-tracking search over possible seQr
Qd
quences of primes factors p1 , . . . , pd . Put Pr =i=1 pi , Qr =i=r+1 pi and
Lr = lcm {pi − 1 : i = 1, . . . , r}. We find that Qr must satisfy the congruence
N = Pr Qr ≡ 1 mod Lr and so in particular Qd = pd must satisfy a congruence
modulo Ld−1 : further pd − 1 must be a factor of Pd−1 − 1. We modified this toterminate the search early at some level r if the modulus Lr is large enough to limit
the possible values of Qr , which may then be factorised directly.
We also employed the variant based on proposition 2 of [1] which determines thefinitely many possible pairs (pd−1 , pd ) from Pd−2 . In practice this was useful only
when d = 3 allowing us to determine the complete list of Carmichael numbers withthree prime factors up to 1021 .
2.1. A large prime variation. Finally we employed a different search over largevalues of pd , in the range 2.106 < pd < 1010.5 , using the property that Pd−1 ≡1 mod (pd − 1).
If q is a prime in this range, we let P run through the arithmetic progression
P ≡ 1 mod q −1 in the range q < P < X/q where X = 1021 . We first check whether
N = P q satisfies 2N ≡ 2 mod N : it is sufficient to test whether 2N ≡ 2 mod P
since the congruence modulo q is necessarily satisfied. If this condition is satisfied
we factorise P and test whether N ≡ 1 mod λ(N ).
The approximate time taken for X t ≤ q < X 1/2 isXX≈ X 1−t .
2q1/2t
X <q<X

Date: 15 May 2007.
1

2

RICHARD G.E. PINCH

3. Statistics
nC (10n )
3
1
4
7
5
16
6
43
7
105
8
255
9646
101547113605128241
13
19279
1444706
15105212
16246683
17585355
181401644
193381806
208220777
21 20138200
Table 1. Distribution of Carmichael numbers up to 1021 .

X
345
6
7
8
9
101112
13
1415
16
17
18
1920
21

3
17122347
84
172
335590100018583284
6083
10816
19539
35586
65309
1206252247634004
1955144
314
619
1179
2102
3639
6042
9938
16202
25758
40685
63343
98253
15156650001327146
492
1336
3156
7082
14938
29282
55012
100707178063306310514381
8466276000000
1499
459
1714
5270
14401
36907
86696
194306
4146608495641681744
3230120700000002
41262
1340
5359
19210
60150
172234460553115916727747026363475

80000000007896553622
16348
63635
22399772040621480176015901

90000000000127
170
1436
8835
44993
1963917629632714473

100000000000000
23340
3058
20738
1142325475281100000000000000
1
49
576
5804
42764

Table 2. Values of C(X) and C(d, X) for d ≤ 10 and X in powersof 10 up to 1021 .

We have shown that there are 20138200 Carmichael numbers up to 1021 , all withat most 12 prime factors. We let C(X) denote the number of Carmichael numbers
less than X and C(d, X) denote the number with exactly d prime factors. Table 1gives the values of C(X) and Table 2 the values of C(d, X) for X in powers of 10up to 1021 .

120000000000
000000
2
56
983

total
1
716
43
105
255
646
1547
3605
8241
19279
44706
10521224668358535514016443381806
8220777
20138200

THE CARMICHAEL NUMBERS UP TO 1021

3References[1] Richard G.E. Pinch, The Carmichael numbers up to 1015 , Math. Comp. 61 (1993), 381–391,
Lehmer memorial issue.
, The Carmichael numbers up to 1016 , March 1998, arXiv:math.NT/9803082.
[2][3], The Carmichael numbers up to 1017 , April 2005, arXiv:math.NT/0504119.
, The Carmichael numbers up to 1018 , April 2006, arXiv:math.NT/0604376.
[4]
2 Eldon Road, Cheltenham, Glos GL52 6TU, U.K.
E-mail address: rgep@chalcedon.demon.co.uk