E048: Carmichael numbers: Korselt scan + Fermat counterexamples

Preview figure for E048
Preview figure for E048

Tags: number-theory, counterexample-search, quantitative-exploration, visualization, carmichael, pseudoprime See: Valid Tags.

Highlights

  • Enumerates many small Carmichael numbers by scanning squarefree products of three primes.

  • Verifies that these composites pass Fermat’s test for several common bases.

  • Visualizes the distribution of discovered Carmichael numbers on a log scale.

Goal

Show that Fermat’s primality test can fail spectacularly, and produce a dataset of explicit counterexamples.

Background (quick refresher)

Research question

Within a moderate bound \(N\), how many Carmichael numbers can we find by a simple Korselt scan, and how many Fermat bases do they fool?

Experiment design

  • Enumerate candidates \(n=pqr\le N\) with distinct primes \(p<q<r\).

  • Apply Korselt’s criterion: \((p-1)\mid(n-1)\) for each prime factor \(p\mid n\).

  • For each Carmichael \(n\), test Fermat congruence for a small base set (skipping non-coprime bases).

  • Plot index vs. \(n\) and “bases passed” vs. \(n\).

Reproducibility

  • params.json records the run settings.

  • report.md summarizes the key findings.

  • figures/*.png contains the plots for the run.

Interpreting the results

  • All numbers found are composite by construction, yet they pass Fermat congruences for all coprime bases (in theory).

  • The scan is restricted to 3-prime-factor Carmichael numbers; larger-factor Carmichaels exist too.

  • Seeing “all bases passed” in the plot is a strong reminder: Fermat alone is not a reliable primality test.

Published run snapshot

If this experiment is included in the docs gallery, include the published snapshot (report + params).

Parameters

  • n_max: 5000000

  • bases: 2, 3, 5, 7, 11, 13

Smallest Carmichael numbers found (3 prime factors)

n

factorization

Fermat bases passed

561

3·11·17

4

1105

5·13·17

4

1729

7·13·19

4

2465

5·17·29

5

2821

7·13·31

4

6601

7·23·41

5

8911

7·19·67

5

10585

5·29·73

5

15841

7·31·73

5

29341

13·37·61

5

46657

13·37·97

5

52633

7·73·103

5

115921

13·37·241

5

162401

17·41·233

6

252601

41·61·101

6

294409

37·73·109

6

314821

13·61·397

5

334153

19·43·409

6

399001

31·61·211

6

410041

41·73·137

6

Notes

  • These n are composite yet pass Fermat’s congruence for all coprime bases.

  • The scan here is restricted to squarefree products of three primes, which already recovers many classical examples (e.g., 561 = 3·11·17).

params.json (snapshot)
{
  "base_list": [
    2,
    3,
    5,
    7,
    11,
    13
  ],
  "max_results": 5000,
  "n_max": 5000000
}

References

See Alford et al. [1994], Carmichael [1912], The OEIS Foundation Inc. [2025], Wikipedia contributors [2025].