The Central Idea
Fix a positive integer \(n\). The residue class of \(a\) modulo \(n\) is the set of all integers congruent to \(a\) modulo \(n\).
\[ \boxed{ [a]_n=\{x\in\mathbb Z:x\equiv a\pmod n\} }. \]Because congruence means divisibility of a difference,
\[ [a]_n = \{x\in\mathbb Z:n\mid(x-a)\}. \]A First Example
Consider the residue class of \(1\) modulo \(5\).
Every integer congruent to \(1\pmod5\) belongs to this class:
\[ [1]_5 = \{\ldots,-9,-4,1,6,11,16,21,\ldots\}. \]Each member differs from \(1\) by a multiple of \(5\).
An Equivalent Set Description
The integers congruent to \(a\) modulo \(n\) are exactly the integers of the form
\[ a+kn, \qquad k\in\mathbb Z. \]Therefore,
\[ \boxed{ [a]_n=\{a+kn:k\in\mathbb Z\} }. \]This form makes the repeating spacing of a residue class visible.
Example: Writing a Class in Parametric Form
Modulo \(7\),
\[ [3]_7 = \{3+7k:k\in\mathbb Z\}. \]Expanding several values of \(k\) gives
\[ \ldots,-11,-4,3,10,17,24,\ldots \]Every member has remainder \(3\) when divided by \(7\).
The Canonical Residue Classes Modulo \(n\)
Every integer has exactly one remainder in
\[ 0,1,2,\ldots,n-1. \]Therefore the distinct residue classes modulo \(n\) are
\[ \boxed{ [0]_n,[1]_n,[2]_n,\ldots,[n-1]_n }. \]There are exactly \(n\) distinct residue classes modulo \(n\).
Example: Residue Classes Modulo \(4\)
There are four distinct residue classes modulo \(4\):
\[ [0]_4,\qquad[1]_4,\qquad[2]_4,\qquad[3]_4. \]They can be written
\[ [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 Belongs to Exactly One Class
By the division algorithm, every integer \(a\) can be written
\[ a=nq+r, \qquad 0\le rand hence
\[ a\in[r]_n. \]The remainder \(r\) determines the unique canonical residue class containing \(a\).
Residue Classes Partition the Integers
The residue classes modulo \(n\) divide \(\mathbb Z\) into nonoverlapping pieces.
Together, the classes contain every integer:
\[ \mathbb Z = [0]_n\cup[1]_n\cup\cdots\cup[n-1]_n. \]Distinct residue classes do not overlap.
This kind of decomposition is called a partition of the integers.
Why Distinct Classes Cannot Overlap
Suppose two residue classes modulo \(n\) share an element \(x\):
\[ x\in[a]_n \qquad\text{and}\qquad x\in[b]_n. \]Then
\[ x\equiv a\pmod n \]and
\[ x\equiv b\pmod n. \]By symmetry and transitivity,
\[ a\equiv b\pmod n. \]Thus the two classes are actually the same class.
Equal Residue Classes
Two residue classes are equal exactly when their representatives are congruent:
\[ \boxed{ [a]_n=[b]_n \iff a\equiv b\pmod n }. \]For example,
\[ 17\equiv5\pmod{12}, \]so
\[ \boxed{[17]_{12}=[5]_{12}}. \]A Class Has Many Representatives
The symbols
\[ [1]_5,\qquad[6]_5,\qquad[11]_5,\qquad[-4]_5 \]all name the same set because
\[ 1\equiv6\equiv11\equiv-4\pmod5. \]A residue class therefore has infinitely many possible representatives.
Canonical Representatives
Although a residue class has infinitely many representatives, one of
\[ 0,1,\ldots,n-1 \]is usually chosen as its canonical representative.
For example,
\[ [23]_7=[2]_7, \]and \(2\) is the standard nonnegative representative.
Example: Finding the Canonical Class
Determine the canonical residue class containing \(-17\) modulo \(6\).
Since
\[ -17+18=1, \]we have
\[ -17\equiv1\pmod6. \]Therefore,
\[ \boxed{[-17]_6=[1]_6}. \]Residue Classes Modulo \(2\)
Modulo \(2\), there are exactly two classes:
\[ [0]_2 \]and
\[ [1]_2. \]The class \([0]_2\) contains all even integers, while \([1]_2\) contains all odd integers.
Thus parity is precisely the partition of \(\mathbb Z\) into residue classes modulo \(2\).
Residue Classes Modulo \(3\)
Modulo \(3\), every integer belongs to one of
\[ [0]_3,\qquad[1]_3,\qquad[2]_3. \]These classes correspond to integers of the forms
\[ 3k,\qquad3k+1,\qquad3k+2. \]Every integer has exactly one of these three forms.
Residue Classes as Equivalence Classes
Congruence modulo \(n\) is reflexive, symmetric, and transitive. Therefore it is an equivalence relation on \(\mathbb Z\).
A residue class is precisely an equivalence class under that relation.
The class \([a]_n\) contains every integer equivalent to \(a\) under congruence modulo \(n\).
The Quotient Set \(\mathbb Z/n\mathbb Z\)
The collection of all residue classes modulo \(n\) is commonly written
\[ \boxed{ \mathbb Z/n\mathbb Z = \{[0]_n,[1]_n,\ldots,[n-1]_n\} }. \]This notation describes a new finite set built from the infinite set of integers by identifying congruent integers.
Example: \(\mathbb Z/5\mathbb Z\)
The residue-class system modulo \(5\) is
\[ \boxed{ \mathbb Z/5\mathbb Z = \{[0]_5,[1]_5,[2]_5,[3]_5,[4]_5\} }. \]Although each class contains infinitely many integers, there are only five distinct classes.
Addition of Residue Classes
Residue classes can be added by adding representatives:
\[ \boxed{ [a]_n+[b]_n=[a+b]_n }. \]For example,
\[ [3]_5+[4]_5=[7]_5. \]Since
\[ 7\equiv2\pmod5, \]we obtain
\[ \boxed{[3]_5+[4]_5=[2]_5}. \]Why Class Addition Is Well Defined
A residue class has many representatives, so arithmetic must give the same result no matter which representatives are chosen.
If
\[ a\equiv a'\pmod n \]and
\[ b\equiv b'\pmod n, \]then
\[ a+b\equiv a'+b'\pmod n. \]Therefore,
\[ [a+b]_n=[a'+b']_n. \]The sum depends only on the classes, not on the chosen representatives.
Multiplication of Residue Classes
Multiplication is defined similarly:
\[ \boxed{ [a]_n[b]_n=[ab]_n }. \]For example,
\[ [3]_5[4]_5=[12]_5. \]Since
\[ 12\equiv2\pmod5, \]we have
\[ \boxed{[3]_5[4]_5=[2]_5}. \]Subtraction of Residue Classes
Subtraction is defined by
\[ \boxed{ [a]_n-[b]_n=[a-b]_n }. \]For example,
\[ [2]_7-[5]_7=[-3]_7. \]Since
\[ -3\equiv4\pmod7, \]the result is
\[ \boxed{[4]_7}. \]Additive Identity
The class
\[ [0]_n \]acts as the additive identity:
\[ \boxed{ [a]_n+[0]_n=[a]_n }. \]This mirrors the role of \(0\) in ordinary integer arithmetic.
Additive Inverses
Every residue class has an additive inverse.
The inverse of \([a]_n\) is
\[ [-a]_n \]because
\[ [a]_n+[-a]_n=[0]_n. \]For example, modulo \(7\),
\[ [3]_7+[4]_7=[7]_7=[0]_7. \]Thus \([4]_7\) is the additive inverse of \([3]_7\).
Multiplicative Identity
The class
\[ [1]_n \]acts as the multiplicative identity:
\[ \boxed{ [a]_n[1]_n=[a]_n }. \]Not Every Nonzero Class Has a Multiplicative Inverse
In ordinary rational or real arithmetic, every nonzero number has a multiplicative inverse. In residue-class arithmetic, this need not happen.
Modulo \(6\), consider \([2]_6\). We would need some class \([x]_6\) with
\[ [2]_6[x]_6=[1]_6. \]But no integer \(x\) satisfies
\[ 2x\equiv1\pmod6. \]Therefore \([2]_6\) has no multiplicative inverse modulo \(6\).
When a Multiplicative Inverse Exists
A class \([a]_n\) has a multiplicative inverse modulo \(n\) exactly when
\[ \boxed{\gcd(a,n)=1}. \]For example,
\[ \gcd(5,8)=1, \]and
\[ 5\cdot5=25\equiv1\pmod8. \]Therefore,
\[ \boxed{[5]_8^{-1}=[5]_8}. \]Units Modulo \(n\)
A residue class that has a multiplicative inverse is called a unit modulo \(n\).
Modulo \(8\), the units are
\[ [1]_8,\qquad[3]_8,\qquad[5]_8,\qquad[7]_8, \]because each representative is relatively prime to \(8\).
This idea becomes important in linear congruences and cryptography.
Zero Divisors Can Appear
Residue-class arithmetic can behave differently from ordinary integer arithmetic.
Modulo \(6\),
\[ [2]_6[3]_6=[6]_6=[0]_6. \]Neither \([2]_6\) nor \([3]_6\) is the zero class, yet their product is zero.
Such nonzero classes are called zero divisors.
Prime Moduli Behave Differently
When the modulus \(p\) is prime, every nonzero residue class
\[ [1]_p,[2]_p,\ldots,[p-1]_p \]is relatively prime to \(p\).
Therefore every nonzero class has a multiplicative inverse.
This gives arithmetic modulo a prime especially strong structure.
Example: Inverses Modulo \(5\)
In \(\mathbb Z/5\mathbb Z\),
\[ [1]_5[1]_5=[1]_5, \] \[ [2]_5[3]_5=[6]_5=[1]_5, \] \[ [4]_5[4]_5=[16]_5=[1]_5. \]Thus the multiplicative inverse pairs are
\[ [1]_5\leftrightarrow[1]_5, \qquad [2]_5\leftrightarrow[3]_5, \qquad [4]_5\leftrightarrow[4]_5. \]Residue-Class Arithmetic Tables
Because there are only finitely many residue classes modulo \(n\), addition and multiplication can be organized into finite tables.
For example, modulo \(3\),
\[ [2]_3+[2]_3=[4]_3=[1]_3 \]and
\[ [2]_3[2]_3=[4]_3=[1]_3. \]Such tables display the complete arithmetic behavior of the system.
Residue Classes and Cyclic Patterns
Each residue class represents a recurring position in a cycle.
Modulo \(7\), all integers in
\[ [2]_7 \]occupy the same location in a seven-step cycle:
\[ \ldots,-12,-5,2,9,16,23,\ldots \]The arithmetic value changes, but the modular position stays fixed.
Residue Classes and Divisibility
The zero residue class has a direct divisibility interpretation:
\[ [0]_n = \{x\in\mathbb Z:n\mid x\}. \]Thus \([0]_n\) is exactly the set of integer multiples of \(n\).
For example,
\[ [0]_4 = \{\ldots,-8,-4,0,4,8,\ldots\}. \]Residue Classes and Linear Forms
Membership in a residue class can be expressed algebraically.
Saying
\[ x\in[3]_5 \]means precisely that
\[ x=5k+3 \]for some integer \(k\).
This representation is useful when translating modular information into ordinary integer equations.
Example: Proving a Property by Residue Classes
Every integer is congruent to \(0\) or \(1\) modulo \(2\).
If
\[ n\in[0]_2, \]then \(n\) is even.
If
\[ n\in[1]_2, \]then \(n\) is odd.
These two classes exhaust all possibilities, so every integer is either even or odd.
Common Error: Confusing a Representative with the Class
The integer \(2\) and the residue class
\[ [2]_5 \]are different kinds of objects.
The integer \(2\) is one number. The class \([2]_5\) is an infinite set:
\[ [2]_5 = \{\ldots,-8,-3,2,7,12,\ldots\}. \]Common Error: Treating Equivalent Representatives as Different Classes
Since
\[ 8\equiv3\pmod5, \]the symbols
\[ [8]_5 \]and
\[ [3]_5 \]name the same class.
They are not two separate elements of \(\mathbb Z/5\mathbb Z\).
Common Error: Assuming Different Representatives Mean Different Sets
Residue-class equality depends on congruence, not ordinary equality.
For example,
\[ 14\neq2, \]but
\[ 14\equiv2\pmod6. \]Therefore,
\[ \boxed{[14]_6=[2]_6}. \]Common Error: Including Too Many Canonical Classes
Modulo \(5\), the canonical classes are
\[ [0]_5,[1]_5,[2]_5,[3]_5,[4]_5. \]The symbol
\[ [5]_5 \]does not create a sixth class because
\[ [5]_5=[0]_5. \]Common Error: Assuming Every Nonzero Class Is Invertible
Modulo \(8\), \([2]_8\) is nonzero, but
\[ \gcd(2,8)=2. \]Therefore \([2]_8\) has no multiplicative inverse.
Invertibility depends on being relatively prime to the modulus.
A Reliable Procedure for Identifying a Residue Class
- Identify the positive modulus \(n\).
- Reduce the integer modulo \(n\).
- Find the unique remainder \(r\) with \(0\le r
- Write the canonical class as \([r]_n\).
- Remember that every integer congruent to \(r\) names the same class.
A Reliable Procedure for Class Arithmetic
- Choose convenient representatives of the residue classes.
- Perform the required integer operation.
- Reduce the result modulo \(n\).
- Write the answer as a residue class.
- For multiplication or division questions, check whether inverses actually exist.
Example: Full Class-Arithmetic Workflow
Compute
\[ [17]_6[11]_6+[8]_6. \]Reduce representatives:
\[ [17]_6=[5]_6, \qquad [11]_6=[5]_6, \qquad [8]_6=[2]_6. \]Then
\[ [5]_6[5]_6+[2]_6 = [25]_6+[2]_6. \]Since
\[ [25]_6=[1]_6, \]we obtain
\[ [1]_6+[2]_6=[3]_6. \]Therefore,
\[ \boxed{[17]_6[11]_6+[8]_6=[3]_6}. \]Practice 1: List a Residue Class
Write five integers belonging to
\[ [2]_5. \]Practice 2: Canonical Representative
Find the canonical representative of
\[ [29]_8. \]Practice 3: Negative Representative
Rewrite
\[ [-11]_7 \]using a canonical representative.
Practice 4: Class Equality
Determine whether
\[ [14]_5=[4]_5. \]Practice 5: Addition of Classes
Compute
\[ [4]_7+[6]_7. \]Practice 6: Multiplication of Classes
Compute
\[ [5]_8[7]_8. \]Practice 7: Additive Inverse
Find the additive inverse of
\[ [3]_8. \]Practice 8: Multiplicative Inverse
Determine whether
\[ [3]_{10} \]has a multiplicative inverse. If it does, find it.
Practice 9: Identify the Partition
List all distinct residue classes modulo \(4\).
Practice 10: Identify the Error
A student says that
\[ [1]_6,[7]_6,[13]_6 \]are three different residue classes because their representatives are different integers.
Explain the error.
Practice Answers
Practice 1
Any integers of the form
\[ 2+5k \]work. For example,
\[ \boxed{-8,-3,2,7,12}. \]Practice 2
\[ 29=8(3)+5. \]Therefore,
\[ \boxed{[29]_8=[5]_8}. \]Practice 3
\[ -11+14=3. \]Therefore,
\[ \boxed{[-11]_7=[3]_7}. \]Practice 4
Since
\[ 14-4=10 \]and
\[ 5\mid10, \]we have
\[ \boxed{[14]_5=[4]_5}. \]Practice 5
\[ [4]_7+[6]_7=[10]_7=[3]_7. \]Therefore,
\[ \boxed{[3]_7}. \]Practice 6
\[ [5]_8[7]_8=[35]_8. \]Since
\[ 35\equiv3\pmod8, \]the result is
\[ \boxed{[3]_8}. \]Practice 7
We need a class whose sum with \([3]_8\) is \([0]_8\).
\[ 3+5=8. \]Therefore,
\[ \boxed{-[3]_8=[5]_8}. \]Practice 8
Since
\[ \gcd(3,10)=1, \]the class is invertible. Because
\[ 3\cdot7=21\equiv1\pmod{10}, \]we have
\[ \boxed{[3]_{10}^{-1}=[7]_{10}}. \]Practice 9
There are exactly four:
\[ \boxed{ [0]_4,[1]_4,[2]_4,[3]_4 }. \]Practice 10
The representatives differ by multiples of \(6\):
\[ 7-1=6 \]and
\[ 13-1=12. \]Therefore,
\[ 1\equiv7\equiv13\pmod6, \]so
\[ \boxed{ [1]_6=[7]_6=[13]_6 }. \]What to Remember
- A residue class \([a]_n\) is the set of all integers congruent to \(a\) modulo \(n\).
- The class can be written \([a]_n=\{a+kn:k\in\mathbb Z\}\).
- There are exactly \(n\) distinct residue classes modulo \(n\).
- The canonical representatives are \(0,1,\ldots,n-1\).
- Two classes are equal exactly when their representatives are congruent modulo \(n\).
- The residue classes partition \(\mathbb Z\).
- Addition, subtraction, and multiplication of classes are defined using representatives and reduction modulo \(n\).
- A class \([a]_n\) is multiplicatively invertible exactly when \(\gcd(a,n)=1\).
The central structural idea is: modular arithmetic replaces infinitely many integers by finitely many equivalence classes determined by their remainders.
Where We Go Next
Residue classes turn congruence into arithmetic on a finite collection of equivalence classes. The next lesson, Linear Congruences, asks when equations such as \(ax\equiv b\pmod n\) have solutions and develops systematic methods for finding those solutions.