4.II.7E

State and prove Fermat's Little Theorem.

An odd number $n$ is called a Carmichael number if it is not prime, but every positive integer $a$ satisfies $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, r$ is a Carmichael number if and only if $p-1$ divides $q r-1, q-1$ divides $p r-1$ and $r-1$ divides $p q-1$. Deduce that 1729 is a Carmichael number.

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

*Typos? Please submit corrections to this page on GitHub.*