Carmichael number

A positive integer N is called a Carmichael number if and only if N is composite and for all integers a satisfying gcd(a,N) = 1, a^N-1 is congruent to 1 modulo N (see modular arithmetic). Fermat's little theorem says that all prime numbers have this latter property. In this sense, Carmichael numbers are similar to prime numbers. They are called pseudo primes.

An alternative definition of Carmichael numbers is that a positive integer N is a Carmichael number if and only if N is squarefree and for all prime divisors p of N, p-1 divides N-1. If number n devides m, we write n | m, thus p-1| N-1.

The first known Carmichael number is 561. (Indeed, 561 = 3 · 11 · 17 is squarefree and 2|560, 10|560 and 16|560.)

In 1994 it was shown by William Alford, Andrew Granville and Carl Pomerance that there exist infinitely many Carmichael numbers.