Modular Arithmetic

⚡ Key Takeaways

Modular arithmetic is arithmetic with remainders: numbers "wrap around" after reaching a fixed value called the modulus. Two integers are equivalent ("congruent") if they leave the same remainder when divided by the modulus $n$ , written $a \equiv b \pmod{n}$ . This system powers cryptography, computer science, calendar calculations, and checksum systems. Formalized by Carl Friedrich Gauss in his 1801 Disquisitiones Arithmeticae.

💡 The Core Insight

Forget the value of a number and remember only its remainder after division by $n$ . Because remainders behave predictably under $+$ , $-$ , and $\times$ , an entire clock-like world of arithmetic emerges in which there are only $n$ distinct numbers. The clock is the perfect mental model: $10 + 5 = 15$ , but on a 12-hour clock $10 + 5 \equiv 3$ .

DefinitionCongruence Modulo n

Let $n$ be a positive integer (the modulus). For integers $a$ and $b$ , we say $a$ is congruent to $b$ modulo $n$ , written

1

\quad a \equiv b \pmod{n} \iff n \mid (a - b),

which means there exists an integer $k$ such that $a - b = kn$ . Here:

$a, b$ are integers,
$n \ge 1$ is the modulus,
$n \mid (a-b)$ means " $n$ divides $a-b$ exactly,"
$k$ is some integer (positive, negative, or zero).

DefinitionResidue Class and Set of Residues

The residue class of $a$ modulo $n$ is the set of all integers congruent to $a$ :

2

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

There are exactly $n$ distinct residue classes, and the standard set of representatives is

3

\quad \mathbb{Z}/n\mathbb{Z} = \{\, [0], [1], [2], \dots, [n-1] \,\}.

TheoremCongruence is an Equivalence Relation

For any fixed modulus $n$ , congruence modulo $n$ satisfies: 1. Reflexive: $a \equiv a \pmod n$ , 2. Symmetric: if $a \equiv b$ then $b \equiv a \pmod n$ , 3. Transitive: if $a \equiv b$ and $b \equiv c$ then $a \equiv c \pmod n$ . Therefore it partitions $\mathbb{Z}$ into disjoint residue classes.

TheoremCompatibility with Arithmetic

If $a \equiv b \pmod n$ and $c \equiv d \pmod n$ , then:

4

\quad a + c \equiv b + d \pmod n,

5

\quad a - c \equiv b - d \pmod n,

6

\quad a c \equiv b d \pmod n,

7

\quad a^m \equiv b^m \pmod n \quad \text{for any integer } m \ge 1.

⚠️ Division Does NOT Always Work

Notice equations [4]–[7] cover $+,-,\times$ and powers — but not division. You cannot simply "cancel" a common factor. For example $6 \equiv 0 \pmod 6$ but you cannot conclude $3 \equiv 0$ by "dividing both sides by 2." Cancellation is valid only when the factor is coprime to the modulus (see the Modular Multiplicative Inverse below).

mathematician · Carl Friedrich Gauss | 1777–1855

Often called the "Prince of Mathematicians," Gauss invented the modern notation and theory of congruences while still in his early twenties. In his 1801 masterpiece Disquisitiones Arithmeticae, written when he was 24, he introduced the symbol " $\equiv$ " and systematically developed congruences as a rigorous tool, proving the Chinese Remainder Theorem in general form and laying the groundwork for quadratic reciprocity. His insight was that treating remainders as first-class objects unified scattered observations of earlier number theorists (Fermat, Euler, Lagrange) into a single elegant algebraic structure that underlies essentially all of Number Theory today.

🧠 The Clock and the Number Line Wrapped into a Circle

Imagine the integer number line stretched out, then wrapped around a circle of circumference $n$ . Every point that lands at the same spot on the circle is congruent. A 12-hour clock is modulus 12: 3 o'clock, 15 o'clock, and 27 o'clock all point at the same place because $3 \equiv 15 \equiv 27 \pmod{12}$ . Adding hours is just rotating around the circle. When you "go off the top" you reappear at the bottom — that's the wrap-around. Because the circle has only $n$ positions, arithmetic stays bounded and finite, no matter how large the original numbers were. This is why modular arithmetic lets a computer multiply enormous numbers and keep only the small remainder.

Figure

A clock modeling arithmetic modulo 12: the integers wrap around a circle of 12 positions

ExampleComputing a Large Power Modulo n

Given: Find $7^{100} \bmod 13$ .

Step 1 — Find a small cycle. Compute powers of 7 modulo 13: $7^1 \equiv 7$ , $7^2 = 49 \equiv 49 - 39 = 10$ , $7^3 \equiv 7 \cdot 10 = 70 \equiv 70 - 65 = 5$ , $7^4 \equiv 7 \cdot 5 = 35 \equiv 35 - 26 = 9$ .

Step 2 — Use Fermat's Little Theorem. Since 13 is prime and $\gcd(7,13)=1$ :

7^{12} \equiv 1 \pmod{13}.

Step 3 — Reduce the exponent modulo 12. Write $100 = 12 \cdot 8 + 4$ , so

7^{100} = (7^{12})^{8}\cdot 7^{4} \equiv 1^8 \cdot 7^4 \equiv 7^4 \pmod{13}.

Step 4 — Evaluate. From Step 1, $7^4 \equiv 9 \pmod{13}$ .

\boxed{\,7^{100} \equiv 9 \pmod{13}\,}

ExampleFinding a Modular Inverse and Solving a Congruence

Given: Solve $5x \equiv 3 \pmod{11}$ .

Step 1 — Find the inverse of 5 modulo 11. We need $5y \equiv 1 \pmod{11}$ . Test values: $5\cdot 9 = 45 = 44 + 1 \equiv 1$ . So $5^{-1} \equiv 9 \pmod{11}$ .

Step 2 — Multiply both sides by the inverse.

9 \cdot 5x \equiv 9 \cdot 3 \pmod{11}.

Step 3 — Simplify the left side. Since $9 \cdot 5 \equiv 1$ :

x \equiv 27 \pmod{11}.

Step 4 — Reduce. $27 = 22 + 5$ , so $27 \equiv 5 \pmod{11}$ .

\boxed{\,x \equiv 5 \pmod{11}\,}

Check: $5 \cdot 5 = 25 \equiv 3 \pmod{11}$ . ✓

⚠️ Common Errors

" $a \bmod n$ is always positive in every language." Mathematically the remainder satisfies $0 \le r < n$ , but some programming languages (e.g., C, Java) return a negative result for negative inputs (e.g., $-7 \bmod 3$ may be $-1$ rather than $2$ ). Always normalize.
Confusing the operator $\bmod$ with the relation $\equiv \pmod n$ . " $17 \bmod 5 = 2$ " is a function returning a number; " $17 \equiv 2 \pmod 5$ " is a true/false statement about congruence.
Assuming inverses always exist. $a^{-1}$ modulo $n$ exists iff $\gcd(a,n)=1$ .
Cancelling carelessly. From $ac \equiv bc \pmod n$ you may conclude $a \equiv b$ only if $\gcd(c,n)=1$ .

CounterexampleCancellation Fails Without Coprimality

Consider $\pmod{12}$ :

3 \cdot 2 = 6 \quad\text{and}\quad 9 \cdot 2 = 18 \equiv 6 \pmod{12}.

So $3 \cdot 2 \equiv 9 \cdot 2 \pmod{12}$ , yet $3 \not\equiv 9 \pmod{12}$ . The cancellation of the factor 2 is illegal because $\gcd(2,12) = 2 \ne 1$ .

connection · How Modular Arithmetic Sits Among Its Neighbours

Congruence is built directly on the Division Algorithm (every integer has a unique remainder) and on the Greatest Common Divisor (which decides when inverses exist). The set $\mathbb{Z}/n\mathbb{Z}$ with $+$ and $\times$ is the introductory student's first real encounter with a finite Ring (Algebra); when $n$ is prime it becomes a Finite Field. The key computational engine is the Extended Euclidean Algorithm, which produces inverses. Deeper structural results — the Chinese Remainder Theorem, Fermat's Little Theorem, and Euler's Theorem — all live inside this framework, and together they form the foundation of Public-Key Cryptography.

🔬 Where Modular Arithmetic Is Used

⏳ History

- c. 300 BCE: Euclid's Elements presents the algorithm for the Greatest Common Divisor, implicitly handling remainders.

- c. 3rd–5th century CE: Chinese mathematician Sun Tzu poses remainder problems in Sunzi Suanjing, the seed of the Chinese Remainder Theorem.

- 1247: Qin Jiushao systematizes the Chinese Remainder Theorem in Mathematical Treatise in Nine Sections.

- 1640: Pierre de Fermat states his "Little Theorem,"

a^{p} \equiv a \pmod p

for prime

p

, in a letter (without proof).

- 1736: Leonhard Euler publishes the first proof of Fermat's Little Theorem and later generalizes it via the totient function

\varphi(n)

.

- 1801: Carl Friedrich Gauss publishes Disquisitiones Arithmeticae, introducing the "

\equiv

" notation and the formal theory of congruences.

- 1801: Gauss proves the law of quadratic reciprocity using congruence machinery.

- 1976: Whitfield Diffie and Martin Hellman publish their key-exchange protocol, igniting modern public-key cryptography.

- 1977: Rivest, Shamir, and Adleman invent RSA, making modular exponentiation a cornerstone of digital security.

open-problem · Computational Hardness and Open Questions

Modular arithmetic is computationally easy in the forward direction — multiplying and exponentiating modulo $n$ is fast. The deep difficulty lies in inverting these operations:

The Discrete Logarithm Problem (given $g$ , $p$ , and $g^x \bmod p$ , find $x$ ) is believed hard but has no proven lower bound — its difficulty underpins Diffie–Hellman and elliptic-curve cryptography.
The Integer Factorization Problem (recovering $p,q$ from $n=pq$ ) similarly has no known efficient classical algorithm, yet Shor's algorithm solves both on a hypothetical large-scale quantum computer in polynomial time, threatening current cryptosystems.
Whether efficient classical algorithms for these problems exist is tied to the broader, unresolved landscape of computational complexity (related to $\mathbf{P}$ vs $\mathbf{NP}$ ). No proof of hardness — only strong empirical confidence — currently exists.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also