User Rating 0.0 ★★★★★

Total Usage 0 times

Category Number Generators

Search Mode

How Many to Find

Upper Bound

Show Prime Factorization

Presets:

Searching...

#	Carmichael Number	Prime Factorization	Digits

Is this tool helpful?

Your feedback helps us improve.

★ ★ ★ ★ ★

About

Carmichael numbers are composite integers n that satisfy aⁿ⁻¹ ≡ 1 (mod n) for every integer a coprime to n. They are the absolute Fermat pseudoprimes and represent a direct threat to any primality test relying solely on Fermat's little theorem. The smallest is 561 = 3 × 11 × 17, discovered by Robert Carmichael in 1910. Alford, Granville, and Pomerance proved in 1994 that infinitely many exist. Their density up to x is approximately x^2⁄7, making them sparse but never absent.

This generator applies Korselt's criterion: n is Carmichael if and only if n is square-free and for every prime factor p of n, (p − 1) divides (n − 1). This algebraic test avoids the exponential cost of checking all coprime bases. Note: computation time grows substantially beyond 10⁸ due to the factorization step required for each odd composite candidate.

Formulas

A composite integer n is a Carmichael number if it passes the Fermat primality test for all bases coprime to it. The direct definition states:

a^{n − 1} ≡ 1 (mod n) for all a with gcd(a, n) = 1

Testing every base is computationally infeasible. Instead, this generator uses Korselt's criterion (1899), which provides an equivalent algebraic characterization:

n is Carmichael ⇔ n is square-free ∧ for every prime p | n, (p − 1) | (n − 1)

The algorithm proceeds in three stages for each candidate n:

1. Factorize n via trial division up to √n
2. Check square-free: all prime exponents = 1
3. Check divisibility: (n − 1) mod (p_i − 1) = 0 for all i

Where n is the candidate composite number, p represents each distinct prime factor of n, and the notation (p − 1) | (n − 1) means "p − 1 divides n − 1". Candidates are restricted to odd numbers with at least 3 prime factors, since all Carmichael numbers are odd and have ≥ 3 prime factors.

Reference Data

#	Carmichael Number	Prime Factorization	Number of Factors	Digits
1	561	3 × 11 × 17	3	3
2	1105	5 × 13 × 17	3	4
3	1729	7 × 13 × 19	3	4
4	2465	5 × 17 × 29	3	4
5	2821	7 × 13 × 31	3	4
6	6601	7 × 23 × 41	3	4
7	8911	7 × 19 × 67	3	4
8	10585	5 × 29 × 73	3	5
9	15841	7 × 31 × 73	3	5
10	29341	13 × 37 × 61	3	5
11	41041	7 × 11 × 13 × 41	4	5
12	46657	13 × 37 × 97	3	5
13	52633	7 × 73 × 103	3	5
14	62745	3 × 5 × 47 × 89	4	5
15	63973	7 × 13 × 19 × 37	4	5
16	75361	11 × 13 × 17 × 31	4	5
17	101101	7 × 11 × 13 × 101	4	6
18	115921	13 × 37 × 241	3	6
19	126217	7 × 13 × 19 × 73	4	6
20	162401	17 × 41 × 233	3	6
21	172081	7 × 13 × 31 × 61	4	6
22	188461	7 × 13 × 19 × 109	4	6
23	252601	41 × 61 × 101	3	6
24	278545	5 × 17 × 29 × 113	4	6
25	294409	37 × 73 × 109	3	6

Frequently Asked Questions

Korselt's criterion requires n to be square-free and composite, with (p − 1) | (n − 1) for every prime factor p. If n = p × q (two factors), then (p − 1) must divide pq − 1, which simplifies to (p − 1) | (q − 1) and symmetrically (q − 1) | (p − 1). This forces p = q, violating the square-free condition. Therefore the minimum is 3 distinct prime factors.

Each odd composite candidate n requires trial division up to √n, giving per-candidate cost of O(√n). Since roughly n⁄2 odd candidates exist below n, total cost is approximately O(n^3⁄2). Searching up to 10⁶ completes in under a second. Reaching 10⁸ may take several seconds. The generator runs in a Web Worker to keep the interface responsive.

Yes. If n were even, then 2 would be a prime factor, requiring (2 − 1) = 1 to divide (n − 1), which is trivially true. However, Fermat's theorem applied to base a = n − 1 yields (n − 1)^{n − 1} ≡ 1 (mod n). For even n, the left side is 1 (since n − 1 is odd, so (−1)^odd = −1), requiring −1 ≡ 1 (mod n), meaning n | 2, so n = 1 or 2. Neither is composite with ≥ 3 factors.

The Carmichael function λ(n) gives the smallest positive integer m such that a^m ≡ 1 (mod n) for all a coprime to n. A Carmichael number satisfies λ(n) | (n − 1). For square-free n = p₁p₂…p_k, λ(n) = lcm(p₁ − 1, …, p_k − 1). So Korselt's divisibility condition is exactly the statement that λ(n) divides n − 1.

No. The Miller-Rabin test is strictly stronger than the Fermat test. It decomposes n − 1 = 2^s × d and checks intermediate square roots. A Carmichael number will always be detected as composite by at least 75% of randomly chosen bases in Miller-Rabin. With k independent rounds, the false positive probability is at most 4^−k. Deterministic variants using specific base sets can conclusively identify all composites below 3.317 × 10²⁴.

Higher-order Carmichael numbers generalize the concept to polynomial rings. A k-th order Carmichael number n satisfies (a + 1)ⁿ ≡ aⁿ + 1 (mod n) in a degree-k extension. Order-1 Carmichael numbers are the classical ones. Higher orders are significantly rarer. This generator handles only the classical (order-1) case.