How to discover the statement and two proofs of Fermat's little theorem

The statement, and sketches of the usual proofs

Fermat's little theorem states that if $p$ is a prime and $x$ is an integer not divisible by $p$, then $x^{p-1}$ is congruent to $1 (mod p)$.

One proof is to note that x can be regarded as an element of the multiplicative group of non-zero residue classes ($mod p$). It generates a cyclic subgroup, and the order of that subgroup is the minimal r such that $x^r=1 (mod p)$. By Lagrange's theorem, this $r$ must divide $p-1$, from which the theorem readily follows.

Another proof is to deal with a modified statement: that $x^p=x (mod p)$ for every $x$.

Read more »