Modular Mathematics, The Carmichael Numbers

The Carmichael Numbers

Let n be a Carmichael number. By definition, n is not prime, yet xn-1 mod n is 1 for every x that is coprime to n.

If p2 divides n, then the group of units includes a cycle of length p×(p-1). Use this cycle to find x, a nontrivial pth root of 1. Since p divides n, xn = 1, and xn-1 is the inverse of x. This is a contradiction, hence all Carmichael numbers are square free. (This works even if p = 2; find a square root that is 3 mod 4.)

If p is a factor of n, the group of units mod n has an independent cycle of length p-1. Let x b primitive mod p, and 1 mod every other prime dividing n. This can be realized using the chinese remainder theorem. Now xp-1 = 1, and if xn-1is also 1, then p-1 divides n-1. This relationship holds for every p dividing n. Conversely, if this relationship holds, and we consider any element x, x mod p becomes 1 when raised to the n-1, for every p dividing n, so xn-1 is also 1 mod n. Our simple criteron of p-1 into n-1 is necessary and sufficient.

If n is even then p-1, for some other odd prime, will not divide n-1. Carmichael numbers are odd.

If n = pq, where q is larger, then q-1 divides pq-p, and cannot divide pq-1. Carmichael numbers have at least three prime factors.

Recall the earlier example 3×11×17 = 561, and note that 2, 10, and 16 all divide 560. It requires only algebra to show that the product of 6k+1, 12k+1, and 18k+1 is carmichael, provided all three factors are prime. The same holds for 60k+43, 180k+127, and 300k+211.

There are an infinite number of carmichael numbers. This nontrivial result was proved in 1994 by Alford, Granville, and Pomerance. In fact there are infinitely many carmichael polynomials of the form a1k+b1 × a2k+b2 × a3k+b3. Another example is 30k+13 × 90k+37 × 150k+61. I've been told that only 6k+1 × 12k+1 × 18k+1 has ones as constants.

Extended Criteria

Let n, a carmichael number, be the product of p times q1 through qj. Here p could be any of the prime factors of n. For convenience, let t be the product of q1 through qj.

p-1 divides n-1

p-1 divides pt-1

For some c, pt - 1 = cp - c

cp - tp - c = -1

cp - tp + t - c = t - 1

(c-t) × (p-1) = t - 1

p-1 divides t-1

Verify this for 561: 2 divides 186, 10 divides 50, and 16 divides 32.

Since the algebra can be reversed, this condition is both necessary and sufficient.