# Proving Fermat's little theorem directly

I'm trying to prove Fermat's little theorem directly with only the definition of congruence.

Fermat's theorem: If $p$ prime and $a$ is an integer such that $(a,p)=1$, then $a^{p-1}\equiv 1\ (mod\ p)$.

Proof:

Each element of $1,2,\ldots,p-1$ is congruent modulo $p$ to one and only one element of these $a,2a,\ldots,(p-1)a$ and vice-versa.

Let $n_1a$ with $0\le n_1\le p-1$. By Division Algorithm there exist $q$ and $r$ integers such that $0\le r\le p-1$ and $n_1a=pq+r$ ($r\neq 0$ because $(a,p)=1$). Thus $n_1a\equiv r\ (mod\ p)$ with $1\le r\le p-1$.

Suppose now $n_1a\equiv n_2\ (mod\ p)$ and $n_1a\equiv n_3\ (mod\ p)$ with $1\le n_1,n_2,n_3\le p-1$, then is easy to see $n_2=n_3$.

On the other hand, if $n_1a\equiv n_3\ (mod\ p)$ and $n_2a\equiv n_3\ (mod\ p)$ with $1\le n_1,n_2,n_3\le p-1$, then $n_1\equiv n_2\ (mod\ p)$ (since (a,p)=1, we can cancel the $a$'s). Therefore, $p|(n_1-n_2)$ which implies $n_1-n_2=0$ and $n_1=n_2$.

Thus, $a\cdot 2a\cdot\ldots\cdot(p-1)a\equiv 1\cdot2\cdot\ldots\cdot p-1\ (mod\ p)$ implies $a^{p-1}\equiv 1\ (mod\ p)$.

Does it miss something?

• This is more or less it. The crux of the proof is to note that the map $n \mapsto a n$ is injective mod $p$. – darko Sep 12 '16 at 8:50

• the part beginning with "suppose now" is useless. It is clear that $n_1a$ has only one rest in the division by $p$
• the part beginning with "on the other hand" is where you would need more details. If $n_1a \equiv n_2a \mod{p}$, then $a(n_1-n_2) \equiv 0 \mod{p}$, which is impossible since $n_1-n_2 \in [2-p,p-2]$ is prime with $p$ and so is $a$. Whether it is "easy to see" or not depends on your audience, and it is the subtle point of this proof, so you might as well write it