2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – darko Sep 12 '16 at 8:50
1
$\begingroup$

It doesn't miss anything.

However, I have two quick comments :

  • 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

$\endgroup$
  • $\begingroup$ Please see my edit after "on the other hand", thanks! $\endgroup$ – user42912 Sep 12 '16 at 13:30
  • 1
    $\begingroup$ Yes, that is clearer $\endgroup$ – Vincent Sep 12 '16 at 13:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.