Numbers and Sets | Part IA, 2006

State and prove Fermat's Little Theorem.

An odd number nn is called a Carmichael number if it is not prime, but every positive integer aa satisfies ana(modn)a^{n} \equiv a(\bmod n). Show that a Carmichael number cannot be divisible by the square of a prime. Show also that a product of two distinct odd primes cannot be a Carmichael number, and that a product of three distinct odd primes p,q,rp, q, r is a Carmichael number if and only if p1p-1 divides qr1,q1q r-1, q-1 divides pr1p r-1 and r1r-1 divides pq1p q-1. Deduce that 1729 is a Carmichael number.

[You may assume the result that, for any prime pp, there exists a number g prime to pp such that the congruence gd1(modp)g^{d} \equiv 1(\bmod p) holds only when dd is a multiple of p1p-1. The prime factors of 1729 are 7,13 and 19.]

Typos? Please submit corrections to this page on GitHub.