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 carmichale, 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.