Let \(m\) be a positive integer. For an integer \(a\), the residue class (or, congruence class) of
\(a\) modulo \(m\) is the set
\[\overline{a}:=\{x\in \mathbb Z\;|\;x\equiv a \:\left(\mathrm{mod}\: m\right) \}.\]
It easy to check for any two integers \(a\) and \(b\) that \(\overline{a}=\overline{b}\) if and only if \(a\equiv b\:\left(\mathrm{mod}\: m \right)\).
Also either \(\overline{a}=\overline{b}\) or \(\overline{a}\cap \overline{b}=\varnothing\). Since the congruence is an
equivalence relation (why?), it partitions \(\mathbb Z\) into residue classes.
Proposition.
For any positive integer \(m\), \(\mathbb Z\) is partitioned into \(m\) residue classes modulo \(m\), viz.,
\(\overline{0},\overline{1},\cdots,\overline{m-1}\).
Proof.
It easy to check that \(\overline{0},\overline{1},\cdots,\overline{m-1}\) are disjoint. Now we show that \(\mathbb Z=\overline{0}\cup\overline{1}\cup\cdots\cup\overline{m-1}\).
Let \(x\in \mathbb Z\). By the division algorithm, we have \(x=qm+r\) for some integers \(q\) and \(r\) where \(0\leq r\leq m-1\). Then \(x\equiv r \:\left(\mathrm{mod}\: m \right)\)
which implies \(x\in \overline{r}\) for some \(r\), \(0\leq r\leq m-1\). So \(x\in \overline{0}\cup\overline{1}\cup\cdots\cup\overline{m-1}\)
and thus \(\mathbb Z=\overline{0}\cup\overline{1}\cup\cdots\cup\overline{m-1}\).
◼
A complete set of residues modulo \(m\) is a set of integers \(\{a_1,a_2,\ldots,a_m\}\) such that each \(a_i\)
belongs to exactly one of the residue classes \(\overline{0},\overline{1},\ldots,\overline{m-1}\). We write
\(\mathbb Z_m:=\{\overline{0},\overline{1},\ldots,\overline{m-1}\}\).
Example.
For \(m=3\), \(\{0,1,2\}\), \(\{-1,0,1\}\), \(\{-6,7,11\}\), and \(\{n,n+1,n+2\}\) for any integer \(n\) are complete sets of
residues modulo \(3\). So \(\mathbb Z_3=\{\overline{0},\overline{1},\overline{2}\}\).
We define addition and multiplication on residue classes as follows:
\[\overline{a}+\overline{b}=\overline{a+b},\; \overline{a}\overline{b}=\overline{ab}\]
Example.
Modulo \(5\), \(\overline{2}+\overline{3}=\overline{2+3}=\overline{0}\) and \(\overline{2}\;\overline{3}=\overline{2\cdot 3}=\overline{1}\).
A residue class \(\overline{a}\) modulo \(m\) is relatively prime to \(m\) if \(\gcd(a,m)=1\). There are exactly
\(\phi(m)\) integers among \(0,1,\ldots,m-1\) that are relatively prime to \(m\) forming a reduced set of residues modulo \(m\) .
So there are \(\phi(m)\) residue classes modulo \(m\) relatively prime to \(m\).
Definition.
The set of residue classes relatively prime to \(m\) under multiplication modulo \(m\) forms an abelian (commutative)
group called the multiplicative group modulo \(m\) denoted by \(\mathbb Z_m^*\) (or, \(\mathbb Z_m^{\times}\), \(U_m\) ).
It is also called the unit group of \(\mathbb Z_m\) as it consists of invertible elements (or units) of \(\mathbb Z_m\).
Closure: \(\overline{a},\overline{b}\in \mathbb Z_m^* \implies \gcd(a, m) = 1=\gcd(b, m) \implies gcd(ab, m) = 1\implies \overline{a}\overline{b}=\overline{ab}\in \mathbb Z_m^*\).
Associativity: For \(\overline{a},\overline{b},\overline{c}\in \mathbb Z_m^*\), \((\overline{a}\overline{b})\overline{c}=\overline{abc}=\overline{a}(\overline{b}\overline{c})\).
Identity: \(\overline{1}\) as \(\overline{1}\overline{a}=\overline{a}\overline{1}=\overline{a}\) for all \(\overline{a}\in \mathbb Z_m^*\).
Inverse: For \(\overline{a}\in \mathbb Z_m^*\), \(\overline{a}\cdot \overline{x}=\overline{x}\cdot \overline{a}=\overline{1}\) where \(\overline{x}\)
is the unique solution to \(ax\equiv 1\:\left(\mathrm{mod}\: m \right)\) (why?). We denote this \(\overline{x}\) by
\((\overline{a})^{-1}\). So \(\overline{a}\cdot (\overline{a})^{-1}=(\overline{a})^{-1}\cdot \overline{a}=\overline{1}\).
Commutativity: For \(\overline{a},\overline{b}\in \mathbb Z_m^*\), \(\overline{a}\overline{b}=\overline{ab}=\overline{ba}=\overline{b}\overline{a}\).
Order: \(|\mathbb Z_m^*|=\phi(m)\) as discussed above. So for prime \(p\), \(|\mathbb Z_p^*|=p-1\) and
\(\mathbb Z_p^*=\{\overline{1},\overline{2},\ldots,\overline{p-1}\}\).
Example.
\(|\mathbb Z_8^*|=\phi(8)=4\). Since \(1,3,5,7\) are relatively prime to \(8\) (i.e., \(\{1,3,5,7\}\) is a reduced set of residue
s modulo \(8\) ), \(\mathbb Z_8^*=\{\overline{1},\overline{3},\overline{5},\overline{7}\}\). Note that
\(\overline{3}\;\overline{3}=\overline{3\cdot 3}=\overline{1}\). So \((\overline{3})^{-1}=\overline{3}\), inverse of itself.
Lemma.
Let \(p\) be a prime. If \((\overline{a})^{-1}=\overline{a}\) for some \(\overline{a}\in \mathbb Z_p^*\),
then \(\overline{a}=\overline{1}\) or \(\overline{p-1}\).
Proof.
Suppose \((\overline{a})^{-1}=\overline{a}\) for some \(\overline{a}\in \mathbb Z_p^*\). Then
\(\overline{a^2}=\overline{a}^2=\overline{1}\), i.e., \(a^2\equiv 1\:\left(\mathrm{mod}\: p \right)\). So \(a^2-1\equiv 0\:\left(\mathrm{mod}\: p \right)\)
which implies \((a+1)(a-1)\equiv 0\:\left(\mathrm{mod}\: p \right)\), i.e., \((\overline{a+1})(\overline{a-1})=\overline{0}\notin \mathbb Z_p^*\).
Since \(\mathbb Z_p^*\) is closed under multiplication modulo \(p\), \(\overline{a+1}=\overline{0}\) or
\(\overline{a-1}=\overline{0}\), i.e., \((a+1)\equiv 0\:\left(\mathrm{mod}\: p \right)\) or \((a-1)\equiv 0\:\left(\mathrm{mod}\: p \right)\).
Thus \(\overline{a}=\overline{-1}=\overline{p-1}\) or \(\overline{a}=\overline{1}\).
◼
Using the above lemma we prove the following famous result.
Theorem.(Wilson's Theorem, 1770)
For a prime \(p\), \((p-1)!\equiv -1\:\left(\mathrm{mod}\: p \right)\).
Proof.
It suffices to prove \(\overline{(p-1)!}=\overline{-1}\), i.e., \(\overline{1}\; \overline{2}\cdots \overline{p-1}=\overline{p-1}\)
which means \(\overline{2}\cdots \overline{p-2}=\overline{1}\). By the preceding lemma, the only elements of \( \mathbb Z_p^*\)
that are inverse of themselves are \(\overline{1}\) and \(\overline{p-1}\). So in the product \(\overline{2}\cdots \overline{p-2}\),
each element gets multiplied by its inverse on rearrangement. Thus \(\overline{2}\cdots \overline{p-2}=\overline{1}\).
◼
Example.
\(10!+1\) is divisible by \(11\). Use \(p=11\) in Wilson's Theorem.
Theorem.(Converse of Wilson's Theorem)
If \((n-1)!\equiv -1\:\left(\mathrm{mod}\: n \right)\) for a positive integer \(n>1\), then \(n\) is prime.
Proof.
Suppose \((n-1)!\equiv -1\:\left(\mathrm{mod}\: n \right)\) for a positive integer \(n>1\). Let \(n\) be a composite number.
Then \(n\) has a divisor \(d\), \(2\leq d\leq n-1\). Since \(n\vert (n-1)!+1\), \(d\vert (n-1)!+1\). Note that
\(d\vert (n-1)!\) as \(d\leq n-1\). Since \(d\vert (n-1)!+1\) and \(d\vert (n-1)!\), \(d\vert 1=[(n-1)!+1]-(n-1)!\),
a contradiction.
◼