Carmichael numbers are counterexamples to the converse of this result for all bases, and numbers which are counterexamples to its converse for some base are called pseudoprimes.
Golomb constructed a combinatorial proof of this result which used the count- ing of necklaces. The converse of this result is false, but it is strengthened by Lehmer's theorem, which is true. This result generalizes the Chinese hypothesis and is itself a generalization of Euler's totient theorem.   Carmichael numbers are counterexamples to the converse of this result for all bases, and numbers which are counterexamples to its converse for some base are called pseudoprimes. For ten points, identify this result stating that for a natural number a and a prime number p, then ap is congruent to a mod p; it is contrasted with its namesake's  last  theorem.
Golomb constructed a combinatorial proof of this result which used the count- ing of necklaces.
Fermat's little theorem