Linear Congruence and Fermat Theorem

Prerequisite

This article assumes basic knowledge of congruence (what it means ect...), if you find this assumption outrageous, please check out UC Berkeley Short Lecture, Khan Academy or Wiki.

Where magic happens

In modular arithmetic, multiplication, addition and subtraction are generally acceptable. That is,

$a \equiv x \pmod{m}$ & $ b \equiv y \pmod{m} $, then:
$a \pm b \equiv x \pm y \pmod{m}$
 $ab \equiv xy \pmod{m}$

However, we have to be more careful with division or cancellation. In general, it's not true that:
$ a$x $\equiv$$ b$x $\pmod{m} \Rightarrow a \equiv b \pmod{m}$. Cancellation like that is only allowed when $(a,m)=1$ (when $a,m$ share no common factor besides $1$).

It's not true that $4 \equiv 4.2 \pmod{4} \Rightarrow 1 \equiv 2 \pmod{4}$. The reason is obvious. If $ax \equiv bx \pmod{m}$ then $x(a-b) \equiv 0 \pmod{m}$. In other words, $x(a-b) \vdots m$ ( The notation $m|x(a-b)$ means the same thing, but is more common ). So if $(x,m)=1$, all the burden will be carried by $(a-b)$. This means $m|(a-b)$ or $a-b \equiv 0 \pmod{m}$ or $a \equiv b \pmod{m}$.

Otherwise, if $(x,m)=d>1$ then $ a-b$ only have to be divisible by $\frac{m}{d}$. That is $ a \equiv b \pmod{\frac{m}{d}}$

We call a list of all "necessary" remainders mod $m$ a complete residue class of $m$. For simplicity, just think of it as $0,1,2,3,...,m-1$. For example, a complete residue class of $7$ is $0,1,2,3,4,5,6$. It should be obvious why this class contains all the "necessary" remainders. Inclusion of $7$ or $8$ would be unnecessary, since $ 7 \equiv 0 \pmod{7}$ and $ 8 = 7+1 \equiv 1 \pmod{7}$. A complete class of $m$ will have $m$ members, none of which is congruent to one another.

We will now prove the Little Fermat Theorem, which claims that $a^{p-1} \equiv 1 \pmod{p}$ with $p$ being a prime and $(a,p)=1$.

Let this complete class excluding $0$ of $p$: $\{1,2,3,...,p-1\}$  be $S$. Consider $aS$, which is $\{a,2a,..,(p-1)a\}$. We claim that $aS$ contains all the elements of $S$, but in random order. This is equivalent to proving that $aS$ is a complete class of $p$, excluding $0$. Since we already have $m-1$ members in $aS$, we only need to prove that no two of them are congruent. Assume $ax \equiv ay \pmod{m}$. Then, direct cancellation is allowed since $(a,m)=1$. This leads to $x \equiv y \pmod{m}$. Since $x,y$ are members of the original complete class, $x,y$ are distinct, and so are $x,y$.

We have $a.2a.3a...(p-1)a \equiv 1.2.3...(p-1) \pmod{p}$. So $a^{p-1} (p-1)! \equiv (p-1)! \pmod{m}$. Again, since $p$ is a prime, it's relatively prime to every single member of $S$. That is $(p,x)=1$ for $x \in \{1,2,3,..,p-1\}$. Cancellation is allowed for every $x$, so why not cancel them all!

This leaves $a^{p-1} \equiv 1 \pmod{m}$ as claimed.

Extra

Fermat is notorious for stating very hard theorems and claiming that he could prove them. The theorem above was not an exception. In a letter to his friend, Fermat wrote: "And this proposition is generally true for all series [sic] and for all prime numbers; I would send you a demonstration of it, if I did not fear going on for too long". 

Exercise

Oxford