Modular Arithmetic and Congruences

⚡ Key Takeaways

Modular arithmetic is the arithmetic of remainders: integers are considered equal when they differ by a multiple of a fixed modulus $n$ . Key result: the integers modulo $n$ form a commutative ring $\mathbb{Z}/n\mathbb{Z}$ , and the nonzero residues form a group under multiplication exactly when $n$ is prime. It applies wherever cyclic or periodic structure appears — cryptography, hashing, calendars, error correction, number theory. Formalized by Carl Friedrich Gauss in Disquisitiones Arithmeticae (1801).

💡 The Core Insight

Fix a modulus $n$ . Declare two integers equivalent when they leave the same remainder upon division by $n$ . Because this equivalence is compatible with $+$ and $\times$ — equal inputs give equal outputs — the entire arithmetic of $\mathbb{Z}$ descends to a self-contained arithmetic on just $n$ symbols $\{0,1,\dots,n-1\}$ . Everything else (units, inverses, the Chinese Remainder Theorem, Fermat's and Euler's theorems) is a consequence of this compatibility.

DefinitionCongruence Modulo n

Let $n \in \mathbb{Z}_{>0}$ be the modulus. For $a, b \in \mathbb{Z}$ , we say $a$ is congruent to $b$ modulo $n$ , written $a \equiv b \pmod{n}$ , precisely when $n \mid (a - b)$ :

1

\quad a \equiv b \pmod{n} \;\iff\; \exists\, k \in \mathbb{Z}\ \text{such that}\ a - b = kn.

Derivation hint: " $n$ divides $a-b$ " unwinds by the definition of divisibility into the existence of an integer multiplier $k$ . Here $a,b$ are integers, $n$ is the positive modulus, and $k$ is the integer witnessing divisibility.

DefinitionResidue Classes and the Ring

\mathbb{Z}/n\mathbb{Z}

The residue class (or congruence class) of $a$ is the set

2

\quad [a]_n = \{\, x \in \mathbb{Z} : x \equiv a \pmod{n}\,\} = \{\, a + kn : k \in \mathbb{Z}\,\}.

Derivation hint: collect every integer congruent to $a$ ; by [1] these are exactly the integers $a + kn$ . The set of all $n$ distinct classes is $\mathbb{Z}/n\mathbb{Z} = \{[0],[1],\dots,[n-1]\}$ , equipped with the operations

3

\quad [a] + [b] = [a+b], \qquad [a]\cdot[b] = [a\,b].

Derivation hint: define operations on representatives; well-definedness (independence of choice of representative) is proved below.

TheoremStructure of

\mathbb{Z}/n\mathbb{Z}

$(\mathbb{Z}/n\mathbb{Z}, +, \cdot)$ is a commutative ring with identity $[1]$ . An element $[a]$ has a multiplicative inverse if and only if $\gcd(a,n)=1$ . Consequently:

4

\quad \mathbb{Z}/n\mathbb{Z}\ \text{is a field} \iff n\ \text{is prime}.

Derivation hint: a finite commutative ring is a field iff every nonzero element is a unit; units are exactly the coprime residues (Bézout), and all nonzero residues are coprime to $n$ exactly when $n$ is prime. The group of units is

5

\quad (\mathbb{Z}/n\mathbb{Z})^{\times} = \{\,[a] : \gcd(a,n)=1\,\}, \qquad \bigl|(\mathbb{Z}/n\mathbb{Z})^{\times}\bigr| = \varphi(n),

Derivation hint: collect the invertible classes; counting the coprime residues in $\{1,\dots,n\}$ is the definition of Euler's totient $\varphi(n)$ . where $\varphi$ is Euler's totient function.

TheoremChinese Remainder Theorem

If $n = n_1 n_2 \cdots n_r$ with the $n_i$ pairwise coprime, then there is a ring isomorphism

6

\quad \mathbb{Z}/n\mathbb{Z} \;\cong\; \mathbb{Z}/n_1\mathbb{Z} \times \mathbb{Z}/n_2\mathbb{Z} \times \cdots \times \mathbb{Z}/n_r\mathbb{Z}.

Derivation hint: the map $[x]\mapsto([x]_{n_1},\dots,[x]_{n_r})$ is a ring homomorphism; injectivity follows from pairwise coprimality and surjectivity from equal finite cardinalities.

ProofWell-Definedness and the Unit Criterion

Step 1 — Congruence is an equivalence relation. Reflexivity: $n\mid 0=a-a$ . Symmetry: if $n\mid(a-b)$ then $n\mid(b-a)$ . Transitivity: if $n\mid(a-b)$ and $n\mid(b-c)$ , then $n\mid(a-b)+(b-c)=a-c$ . Hence $\mathbb{Z}$ partitions into the classes $[a]_n$ .

Step 2 — Operations are well-defined. Suppose $a\equiv a'$ and $b\equiv b'\pmod n$ , so $a-a'=kn$ , $b-b'=\ell n$ . Then $(a+b)-(a'+b') = (k+\ell)n$ , giving $a+b\equiv a'+b'$ . For multiplication,

ab - a'b' = ab - a'b + a'b - a'b' = (a-a')b + a'(b-b') = (kb + a'\ell)n,

so $ab\equiv a'b'$ . Thus [3] does not depend on representatives.

Step 3 — Ring axioms. Associativity, commutativity, and distributivity for $+,\cdot$ are inherited directly from $\mathbb{Z}$ via the representatives. The class $[0]$ is the additive identity, $[-a]$ the additive inverse, and $[1]$ the multiplicative identity.

Step 4 — Units are coprime residues. $[a]$ is a unit iff $\exists x$ with $ax\equiv 1\pmod n$ , i.e. $ax + ny = 1$ for some $y\in\mathbb{Z}$ . By Bézout's identity this is solvable iff $\gcd(a,n)=1$ . This proves [5], and since every nonzero residue is coprime to $n$ exactly when $n$ is prime, [4] follows. $\blacksquare$

∎

mathematician · Carl Friedrich Gauss | 1777–1855

Gauss introduced the congruence symbol " $\equiv$ " and the systematic theory of residues in his 1801 masterwork Disquisitiones Arithmeticae, written when he was in his early twenties. He recognized that treating integers "up to multiples of $n$ " turned scattered number-theoretic observations — quadratic reciprocity, primitive roots, sums of squares — into a unified algebraic discipline. His notation and viewpoint are still exactly what every student learns today.

🧠 Intuition

Think of a clock. After 12 hours the hour hand returns home: $13 \equiv 1 \pmod{12}$ . The set of "clock positions" is finite, yet you can still add ("3 hours after 11 o'clock is 2 o'clock") and the arithmetic is consistent. Modular arithmetic generalizes this to any modulus: you are doing ordinary arithmetic but wrapping around a circle of $n$ slots. The deep payoff is that this wrapping is compatible with $+$ and $\times$ , so you never have to "leave the circle" to compute. Division is the subtle part — you can only undo multiplication by a number that shares no common factor with $n$ , because otherwise multiplying collapses distinct slots together (e.g. mod 6, $2\cdot 0 = 2\cdot 3 = 0$ ).

Figure

The clock model: integers wrapping around a circle of n = 12 residues

ExampleSolving a Linear Congruence

Given: Solve $14x \equiv 30 \pmod{100}$ .

Step 1 — Check solvability. $d=\gcd(14,100)=2$ . Since $2 \mid 30$ , solutions exist, and there are exactly $d=2$ of them mod 100.

Step 2 — Reduce by $d$ . Divide through (including the modulus) by 2:

7x \equiv 15 \pmod{50}.

Step 3 — Invert $7$ mod $50$ . Run the extended Euclidean algorithm: $50 = 7\cdot 7 + 1$ , so $1 = 50 - 7\cdot 7$ , giving $7^{-1} \equiv -7 \equiv 43 \pmod{50}$ .

Step 4 — Solve. $x \equiv 43 \cdot 15 = 645 \equiv 645 - 12\cdot 50 = 45 \pmod{50}$ .

Step 5 — Lift to mod 100. The two solutions mod 100 are $45$ and $45 + 50 = 95$ .

\boxed{x \equiv 45 \ \text{or}\ 95 \pmod{100}}

ExampleChinese Remainder Theorem in Action

Given: Find $x$ with $x \equiv 2 \pmod 3$ , $x \equiv 3 \pmod 5$ , $x \equiv 2 \pmod 7$ .

Step 1 — Modulus. $n = 3\cdot 5\cdot 7 = 105$ . Set $N_1 = 35$ , $N_2 = 21$ , $N_3 = 15$ .

Step 2 — Partial inverses. $35 \equiv 2 \pmod 3 \Rightarrow 35^{-1}\equiv 2$ . $21 \equiv 1 \pmod 5 \Rightarrow 21^{-1}\equiv 1$ . $15 \equiv 1 \pmod 7 \Rightarrow 15^{-1}\equiv 1$ .

Step 3 — Combine.

x \equiv 2\cdot 35\cdot 2 + 3\cdot 21\cdot 1 + 2\cdot 15\cdot 1 = 140 + 63 + 30 = 233 \pmod{105}.

Step 4 — Reduce. $233 - 2\cdot 105 = 23$ . Check: $23\equiv 2\,(3)$ , $23\equiv 3\,(5)$ , $23\equiv 2\,(7)$ . ✓

\boxed{x \equiv 23 \pmod{105}}

⚠️ Common mistake

You cannot always cancel. From $ac \equiv bc \pmod n$ you may not conclude $a\equiv b\pmod n$ . The correct cancellation law is

ac\equiv bc \pmod n \implies a\equiv b \pmod{n/\gcd(c,n)}.

Cancellation is unrestricted only when $\gcd(c,n)=1$ . Likewise, do not reduce exponents mod $n$ : to simplify $a^k \pmod n$ you reduce $k$ modulo $\varphi(n)$ (when $\gcd(a,n)=1$ ), not modulo $n$ .

Counterexample

Mod 6: take $a=1$ , $b=4$ , $c=2$ . Then $ac = 2$ and $bc = 8 \equiv 2 \pmod 6$ , so $ac\equiv bc$ . But $a=1 \not\equiv 4 = b \pmod 6$ . Cancellation fails because $\gcd(2,6)=2\neq 1$ — indeed the correct conclusion is only $1\equiv 4 \pmod{6/2=3}$ , which is true. This also shows $\mathbb{Z}/6\mathbb{Z}$ has zero divisors: $[2]\cdot[3]=[0]$ with neither factor zero, so it is not a field.

connection

Modular arithmetic is the gateway to Group Theory: $(\mathbb{Z}/n\mathbb{Z},+)$ is the prototypical finite cyclic group, and $(\mathbb{Z}/n\mathbb{Z})^\times$ is a finite abelian group whose order is $\varphi(n)$ . The field criterion [4] connects it to Finite Fields, since $\mathbb{Z}/p\mathbb{Z}$ is the field $\mathbb{F}_p$ . The CRT [6] is the arithmetic shadow of the ring-theoretic Direct Product of Rings. Through Fermat's Little Theorem and Euler's Theorem it powers exponentiation results, and via Quadratic Reciprocity it controls when residues are squares. The whole construction $\mathbb{Z}/n\mathbb{Z} = \mathbb{Z}/(n)$ is the quotient of $\mathbb{Z}$ by an ideal, linking it to Ideals and Quotient Rings.

🔬 Where this appears

⏳ History

- c. 300 BCE — Euclid gives the algorithm for

\gcd

in Elements Book VII, the computational backbone of inverses.

- c. 3rd century CE — Sun Zi poses the prototype "Chinese Remainder" problem in Sunzi Suanjing.

- 1247 — Qin Jiushao gives a general method (Da Yan Shu) for simultaneous remainder problems.

- 1640 — Pierre de Fermat states what is now Fermat's Little Theorem in a letter to Frénicle.

- 1736 — Leonhard Euler publishes the first proof of Fermat's theorem and later (1763) generalizes it via the totient

\varphi

.

- 1801 — Carl Friedrich Gauss introduces the "

\equiv

" notation and the systematic theory of congruences in Disquisitiones Arithmeticae.

- 1832 — Gauss extends congruences to the Gaussian integers, foreshadowing congruences in general rings.

- 1801–1900s — Dirichlet, Dedekind, and Kronecker recast congruences in the language of ideals and quotient rings.

- 1977 — Rivest, Shamir, Adleman publish RSA, making modular exponentiation the foundation of modern public-key cryptography.

open-problem

While modular arithmetic itself is fully understood, the computational questions it raises sit at the frontier. Finding discrete logarithms in $(\mathbb{Z}/p\mathbb{Z})^\times$ and factoring a modulus $n=pq$ are believed hard for classical computers but have no proven super-polynomial lower bound — their difficulty is assumed, not established. Shor's quantum algorithm solves both in polynomial time, so the security of nearly all deployed public-key systems hinges on the unresolved status of large-scale quantum computing. Separately, the distribution of primitive roots and the smallest quadratic non-residue mod $p$ are tied to deep conjectures (Artin's conjecture, the Generalized Riemann Hypothesis) that remain open.

Formal Statement

Why It Holds

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also