Fermat's little theorem

This is just to write down my original proof.

For any integer $a$ and prime $p$, $a^p-a$ is divisible by $p$.

Proof:

The only non-trivial part is when $a$ is not a multiple of $p$, for which the statement is equivalent to $p$ divides $a^{p-1}-1$.

Everything below is modulo $p$. We write down a finite sequence

$$
x_1=(1, a, \ldots, a^n)
$$
such that $a^{n+1}=1$, which is guaranteed for some $n$ because multiplicative inverse is unique.

We then pick $b\in[p-1]$ such that $b\notin x_1$, and write down another sequence

$$
x_2=(b, ba, \ldots, ba^m)
$$
such that $ba^{m+1}=b$. This is also guaranteed: in addition of unique multiplicative inverse, if $ba^{m+1}\in x_1$ then $b\in x_1$, a contradiction. Moreover $m=n$.

We then pick $c\in[p-1]$ such that $c\notin x_1\cup x_2$, and write down another sequence

$$
x_3=(c, ca, \ldots, ca^q)
$$

such that $ca^{q+1}=c$. This is similarly guaranteed, and $q=n$.

So we continue with the process until running through all elements in $[p-1]$. All sequences have the same length, and these lengths sum up to $p-1$, so $n$ divides $p-1$. Therefore $a^{p-1}=a^n=1$.

Q.E.D.