Complete Reference Guide: Modular Arithmetic & Equivalence Classes
A comprehensive mathematical reference guide covering modular arithmetic principles, congruence relations, equivalence classes modulo 8, algebraic consistency, representative invariance proofs, and modular multiplicative inverses.
1. Core Principles & Definitions
Modular arithmetic operates on the remainders of division by a fixed positive integer called the modulus ($m \in \mathbb{Z}^+$).
- Divisibility Notation ($x \mid y$): Read as “$x$ divides $y$,” meaning there exists an integer $k \in \mathbb{Z}$ such that $y = kx$ (with $x \neq 0$).
- Congruence Relation: Two integers $a$ and $b$ are congruent modulo $m$, written as:
Congruence Relation $$a \equiv b \pmod m \iff m \mid (a - b)$$Two integers are congruent modulo $m$ if and only if their difference $(a - b)$ is an exact integer multiple of $m$ (i.e., there exists $k \in \mathbb{Z}$ such that $a - b = km$).
- Equivalence Class (Congruence Class): For a given modulus $m$, the set of all integers that leave the identical remainder $r \in \{0, 1, \dots, m-1\}$ upon Euclidean division by $m$. A modulus $m$ partitions the entire set of integers $\mathbb{Z}$ into exactly $m$ pairwise disjoint, non-overlapping equivalence classes: $$\mathbb{Z} = [0]_m \cup [1]_m \cup [2]_m \cup \dots \cup [m-1]_m$$
- Algebraic Consistency: Addition, subtraction, and multiplication are well-defined under modular equivalence. If $a \equiv a' \pmod m$ and $b \equiv b' \pmod m$, then:
- $(a + b) \equiv (a' + b') \pmod m$
- $(a - b) \equiv (a' - b') \pmod m$
- $(a \times b) \equiv (a' \times b') \pmod m$
2. Equivalence Classes for Modulo 8
For modulus $m = 8$, the set of integers $\mathbb{Z}$ is partitioned into $8$ distinct equivalence classes, uniquely indexed by their canonical remainder $r \in \{0, 1, 2, 3, 4, 5, 6, 7\}$:
Representative Equivalence Classes Modulo 8 ($m = 8$)
Set A ($r \equiv 0 \pmod 8$): $\{\dots, -24, -16, -8, 0, 8, 16, 24, 32, 40, \dots\}$
Set B ($r \equiv 1 \pmod 8$): $\{\dots, -23, -15, -7, 1, 9, 17, 25, 33, 41, \dots\}$
Set C ($r \equiv 2 \pmod 8$): $\{\dots, -22, -14, -6, 2, 10, 18, 26, 34, 42, \dots\}$
Set D ($r \equiv 3 \pmod 8$): $\{\dots, -21, -13, -5, 3, 11, 19, 27, 35, 43, \dots\}$
Set E ($r \equiv 4 \pmod 8$): $\{\dots, -20, -12, -4, 4, 12, 20, 28, 36, 44, \dots\}$
(Note: The remaining classes for remainders $r = 5, 6, 7$ follow the identical arithmetic progression $\{8k + r \mid k \in \mathbb{Z}\}$).
3. Worked Proofs: Algebraic Invariance of Class Representatives
To demonstrate that modular evaluation is strictly invariant under the choice of class representative, we examine two worked evaluations.
Example 1: Multi-Class Mixed Evaluation — $19 \times 26 - 11 \pmod 8$
We map each input term to its residue class modulo 8:
- $19 = 8 \times 2 + 3 \implies 19 \in \mathbf{\text{Set D}} \quad (r = 3)$
- $26 = 8 \times 3 + 2 \implies 26 \in \mathbf{\text{Set C}} \quad (r = 2)$
- $11 = 8 \times 1 + 3 \implies 11 \in \mathbf{\text{Set D}} \quad (r = 3)$
Method 1 — Canonical Representatives (Smallest Non-Negative Remainders)
Substitute each term with its canonical remainder from $\{0, 1, \dots, 7\}$:
Method 2 — Alternative Small Class Elements (Signed / Offset Representatives)
Substitute distinct, small alternative members belonging to the same classes:
- For $19 \in \text{Set D}$, select small negative representative $-5$ (since $-5 = 8(-1) + 3$)
- For $26 \in \text{Set C}$, select small negative representative $-6$ (since $-6 = 8(-1) + 2$)
- For $11 \in \text{Set D}$, select canonical representative $3$
Reduce $27$ modulo 8:
Method 3 — Direct Raw Integer Arithmetic Verification
Calculate the entire expression in standard integer arithmetic without intermediate reductions:
Example 2: Zero-Residue Evaluation — $16 \times 32 - 8 \pmod 8$
We analyze the terms in the expression $(16 \times 32) - 8$:
- $16 = 8 \times 2 + 0 \implies 16 \in \mathbf{\text{Set A}} \quad ([0]_8)$
- $32 = 8 \times 4 + 0 \implies 32 \in \mathbf{\text{Set A}} \quad ([0]_8)$
- Subtracted term $8 = 8 \times 1 + 0 \implies 8 \in \mathbf{\text{Set A}} \quad ([0]_8)$
All terms reside in Set A ($[0]_8$).
Method 1 — Canonical Representatives ($0, 0, 0$)
Method 2 — Distinct Small Non-Zero Representatives ($8, -8, 16$)
Substitute distinct small elements from $\text{Set A}$ into the expression $(16 \times 32) - (8)$:
- Replace first factor: $16 \to 8 \in \text{Set A}$
- Replace second factor: $32 \to -8 \in \text{Set A}$
- Replace subtracted term: $8 \to 16 \in \text{Set A}$
Sign Bookkeeping & Operator Isolation
In $(16 \times 32) - 8$, the subtraction operator is external to the term. Replacing the subtracted positive integer $8 \in [0]_8$ with $16 \in [0]_8$ yields $- (16) = -16$.
Equivalently, viewing the expression as addition of a negative value $(16 \times 32) + (-8)$ and replacing the term $-8 \in [0]_8$ with $-16 \in [0]_8$ gives $((8) \times (-8)) + (-16) = -80 \equiv \mathbf{0} \pmod 8$.
4. Summary Table of Operations
| Expression | Approach | Chosen Representatives | Computed Value | Final Residue Class |
|---|---|---|---|---|
| $19 \times 26 - 11$ | Canonical Remainders | $3, 2, 3$ | $3 \times 2 - 3 = \mathbf{3}$ | $\text{Set D} \equiv 3 \pmod 8$ |
| Alternative Small Elements | $-5, -6, 3$ | $(-5) \times (-6) - 3 = \mathbf{27}$ | $27 = 8(3) + 3 \implies \mathbf{3} \pmod 8$ | |
| Raw Integer Evaluation | Full integers | $494 - 11 = \mathbf{483}$ | $483 = 8(60) + 3 \implies \mathbf{3} \pmod 8$ | |
| $16 \times 32 - 8$ | Canonical Remainders | $0, 0, 0$ | $0 \times 0 - 0 = \mathbf{0}$ | $\text{Set A} \equiv 0 \pmod 8$ |
| Distinct Small Elements | $8, -8, 16$ | $8 \times (-8) - (16) = \mathbf{-80}$ | $-80 = 8(-10) + 0 \implies \mathbf{0} \pmod 8$ |
5. Modular Multiplicative Inverses & Division
In standard arithmetic, division by $b$ is multiplication by the reciprocal $b^{-1} = \frac{1}{b}$. In modular arithmetic over $\mathbb{Z}$, fractions do not exist. Instead, division is defined through the modular multiplicative inverse.
Definition
The multiplicative inverse of an integer $a$ modulo $m$ is an integer $x$ such that:
We denote this element as $a^{-1} \pmod m$.
The Invertibility Condition (Coprimality)
Unlike addition and multiplication, a modular inverse does not always exist.
Theorem: Existence of Modular Inverses
An integer $a$ possesses a multiplicative inverse modulo $m$ if and only if $a$ and $m$ are coprime:
$$\gcd(a, m) = 1$$- If $\gcd(a, m) = 1$: The inverse exists and is uniquely determined within the canonical range $\{1, 2, \dots, m-1\}$.
- If $\gcd(a, m) > 1$: $a$ is a zero divisor (shares a non-trivial factor with $m$). No integer $x$ can satisfy $a \cdot x \equiv 1 \pmod m$.
Invertibility in Modulo 8 ($\mathbb{Z}_8$)
Since $m = 8 = 2^3$, any even integer shares a common factor with 8:
| Residue Class $[a]_8$ | $\gcd(a, 8)$ | Invertible? | Inverse $a^{-1} \pmod 8$ | Verification |
|---|---|---|---|---|
| $[0]$ | 8 | No | — | $0 \cdot x \equiv 0 \neq 1$ |
| $[1]$ | 1 | Yes | 1 | $1 \cdot 1 = 1 \equiv 1 \pmod 8$ |
| $[2]$ | 2 | No | — | $2 \cdot x \in \{0, 2, 4, 6\} \pmod 8$ |
| $[3]$ | 1 | Yes | 3 | $3 \cdot 3 = 9 \equiv 1 \pmod 8$ (self-inverse) |
| $[4]$ | 4 | No | — | $4 \cdot x \in \{0, 4\} \pmod 8$ |
| $[5]$ | 1 | Yes | 5 | $5 \cdot 5 = 25 \equiv 1 \pmod 8$ (self-inverse) |
| $[6]$ | 2 | No | — | $6 \cdot x \in \{0, 2, 4, 6\} \pmod 8$ |
| $[7]$ | 1 | Yes | 7 | $7 \cdot 7 = 49 \equiv 1 \pmod 8$ (self-inverse) |
The set of invertible elements forms the group of units, denoted $\mathbb{Z}_8^\times = \{1, 3, 5, 7\}$. In $\mathbb{Z}_8$, every unit is its own inverse ($a^2 \equiv 1 \pmod 8$).
Computing Inverses: The Extended Euclidean Algorithm
To systematically find $a^{-1} \pmod m$ for large integers, we apply Bézout’s Identity:
When $\gcd(a, m) = 1$:
$$a \cdot x + m \cdot y = 1 \implies a \cdot x \equiv 1 \pmod m$$The integer coefficient $x$ computed by the Extended Euclidean Algorithm is the modular multiplicative inverse of $a$.
Worked Example: Find $17^{-1} \pmod{43}$
Step 1 — Standard Euclidean Algorithm (Find GCD):
- $43 = 2 \times 17 + 9$
- $17 = 1 \times 9 + 8$
- $9 = 1 \times 8 + 1 \implies \gcd(43, 17) = 1$
Step 2 — Back-Substitution (Bézout Coefficients):
Isolate remainders working backwards from 1:
$$1 = 9 - 1 \times 8$$Substitute $8 = 17 - 1 \times 9$:
$$1 = 9 - 1 \times (17 - 9) = 2 \times 9 - 1 \times 17$$Substitute $9 = 43 - 2 \times 17$:
$$1 = 2 \times (43 - 2 \times 17) - 1 \times 17 = 2 \times 43 - 5 \times 17$$Step 3 — Reduction to Modulo 43:
$$-5 \times 17 \equiv 1 \pmod{43}$$Since $-5$ is negative, reduce it into the canonical range $[0, 42]$:
$$x = -5 + 43 = \mathbf{38}$$Thus, $17^{-1} \equiv \mathbf{38} \pmod{43}$.
Solving Congruence Equations (Modular Division)
To solve a linear congruence equation of the form:
Multiply both sides by the modular inverse $a^{-1} \pmod m$ (provided $\gcd(a, m) = 1$):
$$x \equiv b \cdot a^{-1} \pmod m$$Example: Solve $3x \equiv 5 \pmod 8$
- From the units table for $\mathbb{Z}_8$, $3^{-1} \equiv 3 \pmod 8$.
- Multiply both sides by $3$: $$x \equiv 5 \times 3 \pmod 8$$ $$x \equiv 15 \equiv \mathbf{7} \pmod 8$$
- Verification: $3(7) = 21 = 8(2) + 5 \equiv \mathbf{5} \pmod 8$.
Final Conclusion & Mathematical Principles
The calculations rigorously confirm that modular arithmetic operations are independent of the representative chosen from any equivalence class.
Core Takeaways:
- Class Invariance: Any integer $a$ in a given equivalence class $[a]_m$ behaves identically under addition, subtraction, and multiplication modulo $m$.
- Computational Efficiency: Replacing large or negative numbers with their smallest non-negative canonical remainders ($0 \le r < m$) dramatically reduces computational overhead while preserving exact mathematical correctness.
- Consistency Across Operations: Whether evaluating expressions with homogeneous class membership ($16 \times 32 - 8$) or heterogeneous multi-class interactions ($19 \times 26 - 11$), intermediate reductions never distort the final residue class.
- Inverses & Division: Modular division by $a$ is valid if and only if $\gcd(a, m) = 1$, achieved via multiplication by the modular multiplicative inverse $a^{-1} \pmod m$ computed via the Extended Euclidean Algorithm.
6. Related References & Further Reading
- Extended Euclidean Algorithm, Euler's Theorem & Cryptological Applications — Bézout's identity, modular inverses, and RSA cryptography.
- Public-Key Cryptosystems Based on the Discrete Logarithm Problem — Diffie-Hellman Key Exchange and ElGamal encryption.
- Galois Fields in AES: GF(2^8), Irreducible Polynomials, and the Extended Euclidean Algorithm
- Overview of Cryptology: Taxonomy, Primitives, and Cryptanalysis