6. Fermat's Little Theorem and Wilson's Theorem

Lemma: Suppose that $(a,m)=1$, then the least residues of $ka$ for $k=1, \ldots, m-1$ are a permutation of $0,1, \ldots, m-1$. 
Proof) There are $m-1$ numbers in $\mathbb{Z}/m\mathbb{Z}$ that is not congruent to $0$. Let $ka$ and $k'a$ be two numbers with $1 \leq k, k' \leq m-1$, then we have $(k-k')a \equiv 0$ implies that $(k-k') \equiv 0$ as $(a, m)=1$, however because $-m < k-k' < m$, we see that $k=k'$. Hence there cannot be two different $k, k'$ with different least residue.

Thoerem (Fermat's Little Theorem): If $p$ is prime and $(a,p)=1$, then

$a^{p-1} \equiv 1 ~(\bmod{~p})$

Proof) Given any $p$, a prime, we know that $(a,p) = 1$. Hence 

$a, 2a, \ldots, (p-1)a$

all have different least residues which would be $1, \ldots, p-1$. If we multiply them together,

$(p-1)!  \equiv a^{p-1}(p-1)!$

as $(a, l) = 1$ for $l=1, \ldots, p-1$, we may conclude that $a^{p-1} \equiv 1~(\bmod{~p})$.

Easy application of Fermat's Little Theorem would be,

Corollary: If $p$ is a prime, then

$a^p \equiv a ~(\bmod{~p})$

Proof) If $(a,p) =1$, then multiply $a$ on both side from Fermat's little theorem. If $(a,p) = p$, then this shouls that $0 \equiv 0$.

Lemma:  $x^2 \equiv 1 ~(\bmod{~p})$ has exactly two solutions: $1$ and $p-1$.

Proof) We want to find least residues satisfying the above equation. Then we have $p|x^2 -1$, i.e. $p| x-1$ for $p|x+1$ for $0 \leq x \leq p-1$. we can clearly see that $1$ and $p-1$ are the only solutions.

Lemma: Let $p$ be an odd prime and $r$ be the solution of $ax \equiv 1~(\bmod{~p})$ for $a=1, \ldots, p-1$, (respectively, $s$ a solution to $bx \equiv 1~(\bmod{~p})$ then $r' \equiv s'~(\bmod{~p})$ if and only if $a \equiv b ~(\bmod{~p})$. Furthermore, $a \equiv a'$ if and only if $a =1$ or $p-1$.

Proof) $a \equiv bb'a \equiv ba'a \equiv b$. Converse works the same way. The rest follows from lemma above.

Theorem (Wilson's Theorem):  $p$ is a prime if and only if 

$(p-1)! \equiv -1 (~\bmod{~p})$

Proof) We have $ (p-3)/2$ pairs such that when multiplied together, they become $1$ modulo $p$. Hence $(p-2)! \equiv 1$, hence $(p-1)! \equiv p-1 \equiv -1~(\bmod{~p})$. Conversely, if we assume $n$ is composite, then $n=ab$ for $1< a,b<n$, then we have

$a| n | (n-1)! +1$

But clearly, we know that $a|(n-1)!$, hence it follows that $a| 1$, giving a contradiction.

Equivalence relation: Let $R$ be a set, then an equivalence relation is a subset $E$ of $R \times R$, where $a \sim b$ if $(a,b) \in E$ satisfying the following property:

1) $a \sim a$ (Reflexive)

2) $a \sim b$, then $b \sim a$ (Symmetry)

3) $a \sim b$ and $b \sim c$, then $a \sim c$ (Transitive)

Partition: A partition of set $R$ is subsets $\{ P_i \}_{i \in I}$ such that

1) $\bigcup_{i \in I} P_i = R$

2) $P_i \cap P_j = \varnothing$

For any equivalence relationship, we can define a subset of $R$ $[a]_\sim$ to be the equivalence class defined as

$[a]_\sim := \{ b \in R ~|~ a \sim b \}$

Then we have the following relationship between equivalence relationship,

Theorem: Given a partition $\{ P_i \}_{i \in I}$ of $R$, define a relation $\sim$ by $a \sim b$ if $a, b \in P_i$ for some $i \in I$, then $\sim$ is an equivalence relationship with $P_i$ as the equivalence classes. Conversely, distinct equivalence classes of $\sim$ of $R$ defines a partition of $R$.

Lagrange's Theorem: Let $G$ be a group and $H$ a subgroup of $G$. Let $x \sim y$ be defined if $x-y \in H$, then this defines an equivalence relation on $G$. Let $\{x_\alpha \}$ be one element from each equivalence classes, then we have the following

$G = \bigvee_{i \in I} x_iH$

If $G$ is finite, and $[G:H]$ denote the index of $G$ and $H$, then we have $[G:\{e\}] = [G:H][H:\{e\}]$, hence $[G:H] \mid  |G|$.

By Lagrange's theorem, the order of an element divides the order of the group, the multiplicative group of $\mathbb{Z}/p\mathbb{Z}$ which has $p-1$ elements, gives $a^{p-1} =1$ in the group, hence the Fermat's little theorem.