Chinese congruence

The hypothesis that an integer n is prime iff it satisfies the condition that 2^n - 2 is divisible by n. Dickson stated that Leibniz believe to have proved that this congruence implies that n is prime. In actuality, this condition is necessary but not sufficient for n to be prime since, for example, 2^341 - 2 is divisible by 341, but 341 = 11·31 is composite. Composite numbers n (such as 341) for which 2^n - 2 is divisible by n are called Poulet numbers, and are a special class of Fermat pseudoprimes. The Chinese hypothesis is a special case of Fermat's little theorem.

Carmichael number | Euler's theorem | Fermat pseudoprime | Fermat's little theorem | Poulet number | pseudoprime