Modular Arithmetic Basics: Clock Math for CS Students

Number theory · Updated July 2026

You already do modular arithmetic every day. If it is 9:00 and a meeting is in 5 hours, you say 2:00, not 14:00 — you wrapped around a 12-hour clock. Modular arithmetic is the formal version of that wrap-around, and it turns out to be one of the most practically important ideas in a discrete math course: it underlies hash tables, checksums, random number generators, and essentially all modern cryptography. This guide covers the notation, the rules you may use freely, the Euclidean algorithm, and the one operation that trips everyone up: division.

Congruence: the notation that scares people for no reason

We write a ≡ b (mod n) — read "a is congruent to b modulo n" — to mean that a and b leave the same remainder when divided by n. Equivalently, n divides a − b. So 17 ≡ 5 (mod 12) because both leave remainder 5, and 23 ≡ 3 (mod 10).

The power of congruence is that it behaves like equality for addition, subtraction, and multiplication. If a ≡ b (mod n) and c ≡ d (mod n), then:

• a + c ≡ b + d (mod n)
• a − c ≡ b − d (mod n)
• ac ≡ bd (mod n)

Practically, this means you may reduce early and often. Asked for the last digit of 7¹⁰⁰, you never compute 7¹⁰⁰; you work mod 10 and reduce at every step: 7² = 49 ≡ 9, 7⁴ ≡ 9² = 81 ≡ 1, so 7¹⁰⁰ = (7⁴)²⁵ ≡ 1²⁵ = 1. Last digit: 1. Reducing early keeps every intermediate number small — the same trick that makes modular exponentiation feasible for the enormous numbers used in cryptography.

GCD and the Euclidean algorithm

The greatest common divisor gcd(a, b) is the largest integer dividing both a and b. Computing it by factoring is hopeless for large numbers, but a 2,300-year-old method makes it fast. The Euclidean algorithm rests on one fact: gcd(a, b) = gcd(b, a mod b). Replace the pair with the smaller pair, repeat, and when the remainder hits 0, the other number is the gcd.

gcd(252, 198): 252 = 1·198 + 54 → 198 = 3·54 + 36 → 54 = 1·36 + 18 → 36 = 2·18 + 0. So gcd = 18.

Four quick steps, no factoring. The extended Euclidean algorithm runs the same computation while tracking the quotients, producing integers x and y with ax + by = gcd(a, b) (Bézout's identity). That bookkeeping looks like an exam-only ritual, but it is exactly how modular inverses are computed — see below. Related facts worth keeping at hand: lcm(a, b) = ab / gcd(a, b), and two numbers are coprime when their gcd is 1.

Division is the trap

Here is where modular arithmetic diverges from ordinary algebra. You may not freely divide both sides of a congruence. From 6 ≡ 36 (mod 10) you cannot cancel 6 to get 1 ≡ 6 (mod 10) — that is false. Division must be replaced by multiplication by a modular inverse: a number a⁻¹ with a·a⁻¹ ≡ 1 (mod n).

And inverses do not always exist: a has an inverse mod n exactly when gcd(a, n) = 1. That is the deep reason the extended Euclidean algorithm matters — when gcd(a, n) = 1, Bézout gives ax + ny = 1, so ax ≡ 1 (mod n), and x is the inverse. For example, the inverse of 7 mod 26 is 15, since 7 × 15 = 105 = 4 × 26 + 1. This exact computation is how affine ciphers are decrypted and it sits at the heart of RSA key generation.

Where CS actually uses this

• Hash tables: index = hash(key) mod table_size — the wrap-around maps arbitrary integers into a fixed range.
• Checksums and ID validation: ISBN and credit-card (Luhn) checks are congruence conditions designed to catch typos.
• Cryptography: RSA and Diffie–Hellman are modular exponentiation with numbers hundreds of digits long; their security leans on how hard certain mod-n problems are to reverse.
• Systems programming: fixed-width integers overflow by wrapping — unsigned 32-bit arithmetic is arithmetic mod 2³².
• Scheduling and cycles: anything periodic — days of the week, round-robin turns, circular buffers — is naturally indexed mod the cycle length.

Habits that prevent lost points

• Normalize your final answer to the range 0 … n−1. Writing −3 mod 7 when the grader expects 4 invites trouble; −3 and 4 are congruent, but conventions matter. Be especially careful with negative numbers in programming languages, where % may return negatives.
• Reduce before you multiply, not after. Small numbers, fewer arithmetic slips.
• Check gcd before dividing or inverting. No coprimality, no inverse.
• Verify with a tool. Modular exponentiation and extended Euclidean runs are long chains of small steps — one slip early poisons everything after it, so instant checking is unusually valuable here.