# Residue Classes

## From Congruence to Classes

Congruence modulo $n$ groups integers according to their remainders after division by $n$. If two integers have the same remainder, they are congruent modulo $n$.

For example,

$$
17\equiv2\pmod5
$$

because

$$
17-2=15
$$

and

$$
5\mid15.
$$

The integers congruent to $2$ modulo $5$ form the set

$$
\{\ldots,-8,-3,2,7,12,17,\ldots\}.
$$

This set is called a residue class modulo $5$.

## Definition

Let $n\in\mathbb{N}$. For an integer $a$, the residue class of $a$ modulo $n$ is the set

$$
[a]_n=\{b\in\mathbb{Z}:b\equiv a\pmod n\}.
$$

Equivalently,

$$
[a]_n=\{a+kn:k\in\mathbb{Z}\}.
$$

Thus a residue class contains all integers that differ from $a$ by a multiple of $n$.

For example,

$$
[3]_7=\{\ldots,-11,-4,3,10,17,24,\ldots\}.
$$

Each element of this set leaves remainder $3$ when divided by $7$.

## Representatives

Any integer belonging to a residue class may be used to name it. Such an integer is called a representative of the class.

For example,

$$
[3]_7=[10]_7=[-4]_7.
$$

These are not three different classes. They are three names for the same class.

The division algorithm gives a preferred set of representatives:

$$
0,1,2,\ldots,n-1.
$$

Every integer is congruent modulo $n$ to exactly one of these integers.

Thus modulo $7$, the complete list of residue classes is

$$
[0]_7,[1]_7,[2]_7,[3]_7,[4]_7,[5]_7,[6]_7.
$$

## Partition of the Integers

Residue classes modulo $n$ partition the integers. This means two things.

First, every integer lies in some residue class.

Second, two residue classes are either identical or disjoint.

For example, modulo $4$, the integers split into the four classes

$$
[0]_4=\{\ldots,-8,-4,0,4,8,\ldots\},
$$

$$
[1]_4=\{\ldots,-7,-3,1,5,9,\ldots\},
$$

$$
[2]_4=\{\ldots,-6,-2,2,6,10,\ldots\},
$$

$$
[3]_4=\{\ldots,-5,-1,3,7,11,\ldots\}.
$$

Every integer appears in exactly one of these four sets.

## Equality of Residue Classes

Two residue classes modulo $n$ are equal precisely when their representatives are congruent:

$$
[a]_n=[b]_n
$$

if and only if

$$
a\equiv b\pmod n.
$$

Indeed, if $a\equiv b\pmod n$, then every integer congruent to $a$ is also congruent to $b$, so the classes are equal.

Conversely, if the classes are equal, then $a\in[a]_n=[b]_n$, so

$$
a\equiv b\pmod n.
$$

Thus residue classes are determined by congruence, not by the particular representative chosen.

## Arithmetic of Classes

Addition and multiplication of residue classes are defined by

$$
[a]_n+[b]_n=[a+b]_n
$$

and

$$
[a]_n[b]_n=[ab]_n.
$$

These definitions are meaningful because congruence is compatible with addition and multiplication.

For example, modulo $5$,

$$
[3]_5+[4]_5=[7]_5=[2]_5.
$$

Also,

$$
[3]_5[4]_5=[12]_5=[2]_5.
$$

The result depends only on the residue classes, not on the chosen representatives.

## Well-Definedness

To say that class arithmetic is well defined means that choosing different representatives gives the same answer.

Suppose

$$
a\equiv a'\pmod n
$$

and

$$
b\equiv b'\pmod n.
$$

Then

$$
a+b\equiv a'+b'\pmod n
$$

and

$$
ab\equiv a'b'\pmod n.
$$

Therefore

$$
[a+b]_n=[a'+b']_n
$$

and

$$
[ab]_n=[a'b']_n.
$$

This justifies arithmetic on residue classes.

## The Ring of Residue Classes

The set of all residue classes modulo $n$ is denoted by

$$
\mathbb{Z}/n\mathbb{Z}.
$$

It consists of

$$
[0]_n,[1]_n,\ldots,[n-1]_n.
$$

With addition and multiplication defined by residue classes, this set forms a finite arithmetic system.

For example,

$$
\mathbb{Z}/5\mathbb{Z} =
\{[0]_5,[1]_5,[2]_5,[3]_5,[4]_5\}.
$$

Inside this system,

$$
[4]_5+[3]_5=[2]_5
$$

and

$$
[4]_5[3]_5=[2]_5.
$$

The arithmetic "wraps around" after reaching the modulus.

## Units Modulo $n$

A residue class $[a]_n$ is called a unit if it has a multiplicative inverse modulo $n$. That is, there exists a class $[b]_n$ such that

$$
[a]_n[b]_n=[1]_n.
$$

This is equivalent to

$$
ab\equiv1\pmod n.
$$

Such an inverse exists exactly when

$$
\gcd(a,n)=1.
$$

For example, modulo $10$, the units are

$$
[1]_{10},[3]_{10},[7]_{10},[9]_{10}.
$$

The class $[2]_{10}$ is not a unit because

$$
\gcd(2,10)=2.
$$

## Role in Number Theory

Residue classes turn congruence into algebra. Instead of working with infinitely many integers, one works with finitely many classes modulo $n$.

This finite viewpoint is powerful. It underlies modular arithmetic, linear congruences, the Chinese remainder theorem, Euler's theorem, Fermat's little theorem, quadratic residues, and many cryptographic systems.

Residue classes show that arithmetic can be studied locally modulo a fixed integer, while still retaining information about the original integers.