Number Theory Home

## Residue Classes

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) \}.$

Example. For $$m=3$$, $$\overline{0}=3\mathbb Z$$, $$\overline{1}=\{1,1\pm 3, 1\pm 6, 1\pm 9,\ldots \}$$, $$\overline{2}=\{2,2\pm 3, 2\pm 6, 2\pm 9,\ldots \}$$.

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$$.

1. 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^*$$.
2. 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})$$.
3. Identity: $$\overline{1}$$ as $$\overline{1}\overline{a}=\overline{a}\overline{1}=\overline{a}$$ for all $$\overline{a}\in \mathbb Z_m^*$$.
4. 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}$$.
5. Commutativity: For $$\overline{a},\overline{b}\in \mathbb Z_m^*$$, $$\overline{a}\overline{b}=\overline{ab}=\overline{ba}=\overline{b}\overline{a}$$.
6. 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. ◼

Last edited