Modular Arithmetic — Mathematics Knowledge System

Overview

Modular arithmetic is a system of arithmetic for integers where numbers 'wrap around' upon reaching a fixed value called the modulus — much like a clock face wraps from 12 back to 1. Two integers a and b are congruent modulo n (written a ≡ b (mod n)) if they leave the same remainder when divided by n, equivalently if n divides their difference. The modern systematic approach to number theory using modular arithmetic was developed by Carl Friedrich Gauss in his 1801 book Disquisitiones Arithmeticae. Modular arithmetic underlies clock/calendar calculations, checksums, hashing, and modern cryptography.

Intuition

Think of a 12-hour clock. If it's 9 o'clock and 5 hours pass, the clock doesn't show '14' — it wraps around to 2. Modular arithmetic formalizes this wraparound: working 'mod 12' means any answer is replaced by its remainder after dividing by 12. Two numbers are considered 'the same' mod n if they differ by a multiple of n — 9 and 21 are the same mod 12, since 21-9=12 is a multiple of 12.

Formal Definition

Definition

For a modulus n > 0, integers a and b are congruent modulo n if n divides their difference:

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

Definition

38 \equiv 14 \pmod{12} \iff 12 \mid (38-14) = 24

Example: 38 and 14 are congruent mod 12, since 24 = 2·12

a \bmod n = r \text{ where } a = qn + r, \; 0 \le r < n

The 'mod' operation itself returns the unique remainder r in [0, n-1]

Notation

Notation	Meaning
$a \equiv b \pmod{n}$	a and b are congruent modulo n
$\mathbb{Z}/n\mathbb{Z}$	The ring of integers modulo n (the set of residue classes {0,1,...,n-1})
$a \bmod n$	The remainder when a is divided by n

Properties

Congruence is an equivalence relation

\equiv \pmod n \text{ is reflexive, symmetric, and transitive}

Compatible with addition

a \equiv b, \; c \equiv d \pmod n \implies a+c \equiv b+d \pmod n

Compatible with multiplication

a \equiv b, \; c \equiv d \pmod n \implies ac \equiv bd \pmod n

Compatible with exponentiation

a \equiv b \pmod n \implies a^k \equiv b^k \pmod n \text{ for any positive integer } k

Fermat's little theorem

\text{If } p \text{ is prime and } p \nmid a, \text{ then } a^{p-1} \equiv 1 \pmod p

Applications

RSA and other public-key cryptosystems perform all their core operations — key generation, encryption, decryption — as modular exponentiation.

Worked Examples

Divide 23 by 7: 23 = 3·7 + 2.
$23 = 3 \cdot 7 + 2$

Answer: 23 mod 7 = 2.

Practice Problems

Difficulty 2/10

Compute 100 mod 9.

Difficulty 4/10

If today is Wednesday, what day of the week is it in 100 days? (Days of week cycle mod 7; Wed=0.)

Difficulty 5/10

A hash table has 16 buckets. A key with hash value 1000 is stored in bucket (1000 mod 16). Which bucket, and why is modular arithmetic ideal for this?

Difficulty 5/10

A simple check digit d makes the total (sum of data digits + d) ≡ 0 (mod 10). If the data digits sum to 47, what check digit is required?

Common Mistakes

Common Mistake

Thinking a mod n can be negative when computed the mathematical way, e.g. treating -5 mod 3 as -2.

The standard remainder is defined to satisfy 0 ≤ r < n. -5 mod 3 = 1, since -5 = (-2)·3 + 1, not -2 (some programming languages differ, but the mathematical convention keeps the remainder non-negative).

Common Mistake

Assuming you can always 'divide' both sides of a congruence, e.g. 6a ≡ 6b (mod 12) implies a ≡ b (mod 12).

Cancellation in modular arithmetic requires the multiplier to be coprime to the modulus (or dividing the modulus too): 6a≡6b (mod 12) only guarantees a≡b (mod 2), since gcd(6,12)=6 reduces the modulus.

Quiz

Summary

a ≡ b (mod n) means n divides a - b — a and b leave the same remainder when divided by n.
Modular arithmetic 'wraps around' at the modulus n, like a clock face.
Congruence mod n is an equivalence relation compatible with addition, subtraction, and multiplication.
Fermat's little theorem: if p is prime and p∤a, then a^(p-1) ≡ 1 (mod p).
Gauss's Disquisitiones Arithmeticae (1801) formalized the modern theory of congruences.

References

BookGauss, C.F. Disquisitiones Arithmeticae (1801).
WebsiteWikipedia — Modular arithmetic