# E048: Carmichael numbers: Korselt scan + Fermat counterexamples

```{figure} ../_static/experiments/e048_hero.png
:width: 80%
:alt: Preview figure for E048
```

```{figure} ../_static/experiments/e048_hero_2.png
:width: 80%
:alt: Preview figure for E048
```

**Tags:** `number-theory`, `counterexample-search`, `quantitative-exploration`, `visualization`, `carmichael`, `pseudoprime`
See: {doc}`../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)

- {doc}`../background/carmichael-numbers`
- {doc}`../background/prime-numbers`

## 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).

```{include} ../reports/e048.md
:start-after: "<!-- REPORT:BEGIN -->"
:end-before: "<!-- REPORT:END -->"
```

::: {dropdown} params.json (snapshot)
:open:

```{literalinclude} ../params/e048.json
:language: json
```

:::

## References

See {cite:t}`AlfordGranvillePomerance1994InfinitelyManyCarmichaelNumbers`, {cite:t}`Carmichael1912CompositeNumbersSatisfyingFermatTheorem`, {cite:t}`OEISFoundationInc2025A002997CarmichaelNumbers`, {cite:t}`WikipediaContributors2025CarmichaelNumber`.

## Related experiments

- {doc}`e012` (Fermat pseudoprimes and Carmichael numbers (counterexamples))
- {doc}`e013` (Prime-polynomial counterexamples (Euler's $n^2 + n + 41$))
- {doc}`e014` (Primorial ± 1 counterexamples)
- {doc}`e018` (Miller–Rabin base choice counterexamples)
- {doc}`e047` (Fermat numbers: Pépin test + factor witnesses)