Modular Arithmetic

Definition: A system of arithmetic for integers where numbers “wrap around” upon reaching a fixed modulus n, so only the remainder after division by n matters.

How It Works

a ≡ b (mod n) means a - b is evenly divisible by n, equivalently, a and b leave the same remainder when divided by n
Congruence mod n is an equivalence relation, it’s reflexive, symmetric, and transitive, which is what justifies treating “remainder classes” as well-defined objects you can do arithmetic on directly
Modular addition and multiplication both wrap: (a + b) mod n and (a × b) mod n are computed by doing the operation normally, then taking the remainder after dividing by n
Modular exponentiation (a^b mod n) is computed efficiently via repeated squaring, avoiding ever forming the full, astronomically large value of a^b directly, cutting a naive O(b) multiplication chain down to O(log b)
The Euclidean Algorithm computes the greatest common divisor (GCD) of two integers by repeated division with remainder, terminating when the remainder hits 0
Two integers are coprime when their GCD is 1, coprimality is the exact condition that determines whether a modular inverse can exist
Euler’s totient function φ(n) counts how many integers from 1 to n are coprime with n, generalizing Fermat’s Little Theorem to any modulus, not just primes
The Extended Euclidean Algorithm additionally finds integers x, y satisfying ax + ny = gcd(a, n), which is exactly how a modular multiplicative inverse gets computed
A modular multiplicative inverse of a mod n exists if and only if gcd(a, n) = 1 (a and n are coprime), and modular “division” is defined as multiplying by that inverse, direct division isn’t defined
Fermat’s Little Theorem states that if p is prime and a is not divisible by p, then a^(p-1) ≡ 1 (mod p), a shortcut for both fast exponentiation and primality testing
RSA encryption, Diffie-Hellman key exchange, and most hash-based data structures (hash tables, cyclic buffers) all rely directly on these modular operations
Congruence classes partition all integers into exactly n groups mod n, every integer belongs to exactly one class, and arithmetic on class representatives behaves consistently regardless of which representative is chosen

Core Properties Reference

Property	Rule	Note
Addition	`(a + b) mod n = ((a mod n) + (b mod n)) mod n`	Can reduce operands before combining
Multiplication	`(a × b) mod n = ((a mod n) × (b mod n)) mod n`	Same reduce-then-combine principle
Exponentiation	`a^b mod n` via repeated squaring	Runs in `O(log b)` multiplications
Inverse existence	Exists iff `gcd(a, n) = 1`	Found via Extended Euclidean Algorithm
Fermat’s Little Theorem	`a^(p-1) ≡ 1 (mod p)`, `p` prime	Basis for fast exponentiation shortcuts

Under the Hood

This is arithmetic mod 6, six states, 0 through 5, arranged in a cycle. Starting at Zero and repeatedly adding 1 walks around the cycle; reaching Five and adding 1 more lands back on Zero instead of continuing to 6. This is precisely what a mod 6 computes for any integer a: it identifies which of the 6 states a lands on after wrapping around the cycle as many times as needed.

A 12-hour clock is the same structure with 12 states instead of 6. Adding hours works exactly like modular addition: 3 hours past 10 o’clock isn’t “13 o’clock,” it’s (10 + 3) mod 12 = 1, which is why clock arithmetic is the standard first example for teaching modular arithmetic, the wraparound is something everyone has already internalized.

The Euclidean Algorithm’s speed matters as much as its correctness. It terminates in a number of steps proportional to the number of digits in the smaller input, not the input’s raw size, which is why it stays fast even on the enormous numbers used in real cryptographic key generation, where naive factoring-based approaches would be far too slow.

Worked Example 1

Given: Compute 13 mod 12.
Step: 13 = 1 × 12 + 1, so the remainder after dividing 13 by 12 is 1.
Answer: 13 mod 12 = 1, which is exactly why 13:00 on a 24-hour clock reads as 1:00 PM on a 12-hour clock.

Worked Example 2

Given: Find gcd(48, 18) using the Euclidean Algorithm.
Step: 48 = 2 × 18 + 12, then 18 = 1 × 12 + 6, then 12 = 2 × 6 + 0. The remainder just before hitting 0 is the GCD.
Answer: gcd(48, 18) = 6, found in three division steps without factoring either number.

Worked Example 3

Given: Compute the modular multiplicative inverse of 3 mod 7, needed to “divide” by 3 in mod-7 arithmetic.
Step: Since gcd(3, 7) = 1, an inverse exists. Testing values: 3 × 5 = 15 = 2×7 + 1, so 3 × 5 ≡ 1 (mod 7).
Answer: The inverse of 3 mod 7 is 5. To “divide” by 3 mod 7, multiply by 5 instead, 10 ÷ 3 mod 7 becomes 10 × 5 mod 7 = 50 mod 7 = 1.

Worked Example 4

Given: Apply Fermat’s Little Theorem to compute 2^10 mod 11 quickly, where 11 is prime.
Step: Fermat’s Little Theorem says a^(p-1) ≡ 1 (mod p) when p is prime and a isn’t a multiple of p. Here a = 2, p = 11, so 2^10 ≡ 1 (mod 11) directly, no computation of 2^10 = 1024 needed.
Answer: 2^10 mod 11 = 1, confirmed by direct check: 1024 = 93 × 11 + 1.

Worked Example 5

Given: Compute 7^222 mod 5 using the pattern of repeating powers instead of computing the full exponent.
Step: Compute successive powers mod 5: 7^1 ≡ 2, 7^2 ≡ 4, 7^3 ≡ 3, 7^4 ≡ 1, 7^5 ≡ 2 again, the pattern repeats every 4 steps. Since 222 mod 4 = 2, 7^222 mod 5 matches 7^2 mod 5.
Answer: 7^222 mod 5 = 4, found by exploiting the cycle length instead of computing a 222nd power directly.

Why It Matters

Essential for RSA encryption and Diffie-Hellman key exchange, both rely on modular exponentiation being fast to compute forward but computationally infeasible to reverse without the private key
Powers hash tables and cyclic data structures directly, a hash table’s bucket index is almost always computed as hash(key) mod table_size
Enables efficient cyclic buffer and ring buffer implementations in software, wraparound indexing is modular arithmetic applied directly to memory addressing
Gives programmers a correctness guarantee for fixed-width integer overflow, unsigned integer wraparound in languages like C is formally modular arithmetic mod 2^bits
Underlies checksum and error-detection algorithms (like ISBN check digits and CRC checks), which validate data by checking a modular remainder against an expected value
Makes large-number cryptographic computation tractable at all, without fast modular exponentiation, RSA-scale key sizes would be computationally impossible to use in real time
Provides the mathematical basis for calendar and time arithmetic in software, computing “what day of the week” a date falls on is a modular arithmetic calculation over mod 7

Common Pitfalls

Attempting direct division in modular arithmetic, division isn’t defined the way it is in ordinary arithmetic, it requires computing and multiplying by the modular multiplicative inverse via the Extended Euclidean Algorithm
Reducing operands too late in a long computation chain, letting intermediate values grow unnecessarily large instead of reducing mod n after every step
Assuming every number has a modular inverse, an inverse of a mod n only exists when gcd(a, n) = 1, if a and n share a common factor, no inverse exists at all
Choosing a hash table size that shares a common factor with typical key patterns, a poor modulus can cause disproportionate hash collisions instead of an even distribution
Overlooking that congruence classes, not individual integers, are what modular arithmetic actually operates over, treating 7 and 7 mod 5 = 2 as unrelated numbers instead of representatives of the same class
Computing a^b mod n by first fully computing a^b, this overflows or becomes computationally infeasible for large exponents, fast modular exponentiation (repeated squaring) avoids this entirely
Applying Fermat’s Little Theorem when the modulus isn’t actually prime, the theorem’s guarantee only holds for a prime modulus, using it against a composite modulus gives an incorrect result
Forgetting that negative numbers still need proper modular reduction, -3 mod 5 is 2, not -3, since the result must fall within 0 to n-1
Confusing the mathematical definition of mod (always non-negative result) with a programming language’s % operator, many languages (C, Java, JavaScript) return a negative result for a negative operand, which is not the same as the mathematical modulus

Comparison

	Standard Arithmetic	Modular Arithmetic	Floating-Point Arithmetic
Range	Unbounded	Wraps within `0` to `n-1`	Bounded by precision, not exact wraparound
Division always defined	Yes (except by 0)	Only when `gcd(a,n)=1`	Yes, with rounding error
Typical use	General calculation	Cryptography, hashing, cyclic structures	Scientific and graphics computation
Result determinism	Exact	Exact	Subject to rounding
Handles negative numbers	Directly	Requires normalizing into `0` to `n-1`	Directly, with sign preserved
Growth of values	Unbounded	Bounded, always within `0` to `n-1`	Bounded by representable precision

Example

RSA public-key encryption encrypts a message m as c = m^e mod n and decrypts it as m = c^d mod n, where e, d, and n are chosen so that modular exponentiation is fast to compute in either direction but factoring n back into its prime components, needed to derive d from e, is computationally infeasible for large enough n.

ISBN-10 book identifiers use a mod-11 checksum digit specifically to catch common data-entry errors, transposing two adjacent digits or mistyping a single digit both change the weighted sum enough that the checksum digit no longer matches, flagging the error immediately without needing a database lookup.

Referenced by

Dig deeper

Spot an error in this note?