Modular Arithmetic

If it is 10 o'clock now and you wait 5 hours, the clock reads 3, not 15. You just did modular arithmetic — you divided by 12 and kept only the remainder. Modular arithmetic is the mathematics of remainders, and it turns out that this simple idea of "wrapping around" a fixed cycle is one of the most powerful tools in all of number theory. It is the machinery behind the check digit on every barcode and credit card, the RSA encryption that protects your online banking, the hash tables inside your programs, and the day-of-the-week calculations in every calendar.

The genius of modular arithmetic is that it lets you do ordinary addition, subtraction, and multiplication inside a finite world of just $n$ numbers, and everything stays consistent. Once you learn to think in "clock time" instead of the infinite number line, whole classes of problems that look terrifying — like the last digit of $7^{100}$ — become almost trivial.

Learning Objectives

• Understand what it means for two integers to be congruent modulo $n$ and read the notation fluently.
• Compute sums, differences, and products in arithmetic mod $n$, and know which operations are safe.
• Find modular inverses and understand when they exist.
• Use fast exponentiation to evaluate large powers modulo $n$.
• Explain how check-digit schemes (ISBN, UPC, Luhn) and public-key cryptography rely on modular arithmetic.
• Distinguish congruence from equality and avoid the classic cancellation trap.

Quick Answer

Two integers $a$ and $b$ are congruent modulo $n$, written $a \equiv b \pmod{n}$, when they leave the same remainder on division by $n$ — equivalently, when $n$ divides $a - b$. The number $n$ is the modulus. Congruence respects addition, subtraction, and multiplication: if $a \equiv b$ and $c \equiv d$, then $a + c \equiv b + d$ and $ac \equiv bd$. This lets you replace any number by its remainder at any stage of a calculation. Division is the tricky part — you can only "divide" by multiplying by a modular inverse, which exists exactly when the divisor is coprime to $n$. These rules power check digits, hashing, and modern cryptography.

Where It Came From

People had informally reasoned about remainders and cycles for millennia — Chinese mathematicians solved simultaneous remainder problems in the third century (the Chinese Remainder Theorem), and calendar-makers everywhere juggled 7-day weeks and 12-month years. But this was all ad hoc. There was no unified language, no algebra of remainders, and no theorems you could reuse.

That changed in 1801 when a 24-year-old Carl Friedrich Gauss published Disquisitiones Arithmeticae ("Investigations in Arithmetic"). The very first section introduces the congruence notation $a \equiv b \pmod{n}$ that we still use today — Gauss deliberately chose the symbol $\equiv$ because congruence behaves so much like equality. This was the crucial conceptual leap. By making "having the same remainder" into a relation you could manipulate with its own algebra, Gauss transformed a pile of scattered tricks into a systematic theory.

The need was real. Gauss and his predecessors (Fermat, Euler, Lagrange) were wrestling with deep questions: When does $x^2 \equiv a \pmod{p}$ have a solution? How do primes distribute? What are the solutions to polynomial equations in integers? These problems demanded a way to reason about integers "up to a remainder" cleanly and rigorously. The congruence notation made proofs shorter, patterns visible, and results composable. Disquisitiones went on to prove quadratic reciprocity and lay the foundations of algebraic number theory, and it is no exaggeration to say modern number theory begins on its first page. Two centuries later, when cryptographers needed hard mathematical problems to secure the internet, they reached straight for Gauss's arithmetic of remainders.

Congruence: The Core Idea

The formal definition is beautifully simple. For a positive integer $n$:

$a \equiv b \pmod{n} \quad\text{means}\quad n \mid (a - b)$

Read "$n \mid (a-b)$" as "$n$ divides $a - b$ evenly." Equivalently, $a$ and $b$ have the same remainder when divided by $n$.

Worked example. Is $38 \equiv 14 \pmod{12}$? Compute $38 - 14 = 24$, and $24 = 12 \times 2$, so $12$ divides $24$. Yes, they are congruent. Check the remainders directly: $38 = 12 \times 3 + 2$ (remainder 2) and $14 = 12 \times 1 + 2$ (remainder 2). Same remainder, confirming the congruence.

Every integer is congruent mod $n$ to exactly one of the values $0, 1, 2, \dots, n-1$. These are the residues, and the whole set is written $\mathbb{Z}_n = \{0, 1, \dots, n-1\}$. When we "reduce mod $n$," we replace a number by its residue. For example, $100 \bmod 7 = 2$ because $100 = 7 \times 14 + 2$.

Congruence is an equivalence relation — it is reflexive ($a \equiv a$), symmetric (if $a \equiv b$ then $b \equiv a$), and transitive (if $a \equiv b$ and $b \equiv c$ then $a \equiv c$). This is exactly why Gauss's $\equiv$ symbol behaves like $=$.

Arithmetic Mod n

The reason modular arithmetic is so useful is that congruence is compatible with the basic operations. If $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$, then:

• $a + c \equiv b + d \pmod{n}$
• $a - c \equiv b - d \pmod{n}$
• $a \times c \equiv b \times d \pmod{n}$

In practice this means you can reduce numbers whenever you like — before, during, or after a calculation — and the answer stays correct. This keeps numbers small.

Worked example (multiplication). Find $47 \times 58 \bmod 9$. Rather than computing $47 \times 58 = 2726$ and then dividing, reduce first: $47 \equiv 2 \pmod 9$ (since $47 = 45 + 2$) and $58 \equiv 4 \pmod 9$ (since $58 = 54 + 4$). So $47 \times 58 \equiv 2 \times 4 = 8 \pmod 9$. Check: $2726 = 9 \times 302 + 8$. Remainder 8. Correct.

Worked example (last digit of a big power). What is the last digit of $7^{100}$? The last digit is the value mod 10. Powers of 7 mod 10 cycle: $7^1 \equiv 7$, $7^2 \equiv 9$, $7^3 \equiv 3$, $7^4 \equiv 1$, then it repeats every 4. Since $100 = 4 \times 25$, we have $7^{100} = (7^4)^{25} \equiv 1^{25} = 1 \pmod{10}$. The last digit is 1.

Fast Modular Exponentiation

For genuinely large exponents, we use repeated squaring. To compute $a^k \bmod n$, square repeatedly and reduce at each step.

Worked example. Compute $3^{13} \bmod 7$. Write $13 = 8 + 4 + 1$ in binary ($1101_2$).

• $3^1 \equiv 3 \pmod 7$
• $3^2 \equiv 9 \equiv 2 \pmod 7$
• $3^4 \equiv 2^2 = 4 \pmod 7$
• $3^8 \equiv 4^2 = 16 \equiv 2 \pmod 7$

Then $3^{13} = 3^8 \cdot 3^4 \cdot 3^1 \equiv 2 \times 4 \times 3 = 24 \equiv 3 \pmod 7$. This method needs only about $\log_2 k$ multiplications, which is what makes cryptography with 2048-bit numbers computationally feasible.

Division and Modular Inverses

Here is the crucial catch: division does not always work in modular arithmetic. You cannot naively cancel. The correct notion of division is multiplying by a modular inverse.

The inverse of $a$ mod $n$ is a number $a^{-1}$ with $a \cdot a^{-1} \equiv 1 \pmod{n}$. It exists if and only if $\gcd(a, n) = 1$ (that is, $a$ and $n$ are coprime).

Worked example. Find the inverse of $3$ mod $7$. We want $3x \equiv 1 \pmod 7$. Testing: $3 \times 5 = 15 = 14 + 1 \equiv 1 \pmod 7$. So $3^{-1} \equiv 5 \pmod 7$. To "divide by 3" mod 7, multiply by 5.

Why coprimality matters. Consider mod 6. There is no inverse of 2, because $2x$ mod 6 only ever hits $0, 2, 4$ — never 1. And $\gcd(2,6) = 2 \neq 1$. But when $n = p$ is prime, every nonzero residue has an inverse, which is why prime moduli are so beloved in cryptography.

Real-World Applications

• Check digits (ISBN, UPC, IBAN). The 13-digit ISBN on every book ends in a check digit chosen so a weighted sum is $\equiv 0 \pmod{10}$. If you mistype a digit, the sum breaks the congruence and the error is caught instantly.
• Credit-card validation (Luhn algorithm). Every card number satisfies a mod-10 checksum. Before a payment form even contacts the bank, it uses modular arithmetic to reject typos.
• Cryptography (RSA). RSA encrypts a message $m$ as $c \equiv m^e \pmod n$, where $n$ is a product of two enormous primes. Decryption uses the inverse exponent mod $\varphi(n)$. Security rests on the difficulty of factoring $n$ — pure Gaussian arithmetic scaled to hundreds of digits.
• Hashing and data structures. Hash tables map a key $k$ to a bucket $k \bmod n$, spreading data evenly across memory.
• Calendars and scheduling. Day-of-week is a mod-7 calculation; recurring events cycle through mod arithmetic.
• Random number generators. Linear congruential generators produce pseudo-random sequences via $x_{n+1} \equiv (a x_n + c) \pmod m$.

Worked ISBN example. An ISBN-13 uses weights $1, 3, 1, 3, \dots$. Take a number starting $978030640615$ with unknown check digit $d$. The weighted sum of the first 12 digits (weights alternating 1 and 3) plus $d$ must be $\equiv 0 \pmod{10}$. Computing $9\cdot1 + 7\cdot3 + 8\cdot1 + 0\cdot3 + 3\cdot1 + 0\cdot3 + 6\cdot1 + 4\cdot3 + 0\cdot1 + 6\cdot3 + 1\cdot1 + 5\cdot3 = 9+21+8+0+3+0+6+12+0+18+1+15 = 93$. We need $93 + d \equiv 0 \pmod{10}$, so $d \equiv -93 \equiv 7 \pmod{10}$. The check digit is 7.

Common Mistakes

1. Confusing congruence with equality. Writing $17 \equiv 5 \pmod{12}$ does not mean $17 = 5$. It means they share a remainder. Congruence is a relation between numbers, not a claim that they are the same number. Always carry the "$\pmod n$" label.

2. Cancelling illegally. From $2 \times 3 \equiv 2 \times 0 \pmod 6$ (both sides are 0) you might try to cancel the 2 to get $3 \equiv 0 \pmod 6$, which is false. You may only cancel a factor that is coprime to the modulus. Since $\gcd(2,6) = 2$, cancelling 2 is illegal here.

3. Assuming division always works. Students write "$x \equiv 4/2 \pmod n$" as if fractions exist. There are no fractions mod $n$; you must use a modular inverse, which only exists when the divisor is coprime to $n$. Check the gcd first.

4. Mishandling negatives. $-1 \bmod 5$ is $4$, not $-1$ or $1$. A residue should be taken in the range $0$ to $n-1$. Add the modulus until you land in range: $-1 + 5 = 4$.

Comparison and Connections

Modular arithmetic sits at the crossroads of division, group theory, and cryptography. It helps to see how the related ideas line up.

Concept	What it captures	Key condition
Divisibility ($n \mid a$)	$a$ leaves remainder 0	remainder is exactly 0
Congruence ($a \equiv b$)	$a, b$ share a remainder	$n \mid (a - b)$
Modular inverse	"division" mod $n$	$\gcd(a,n) = 1$
Chinese Remainder Theorem	combining several moduli	moduli pairwise coprime
Fermat's Little Theorem	$a^{p-1} \equiv 1 \pmod p$	$p$ prime, $p \nmid a$

The set $\mathbb{Z}_n$ with addition forms a group, and the coprime residues under multiplication form a group too — modular arithmetic is many students' first encounter with abstract algebra. Fermat's Little Theorem and its generalization Euler's theorem are what make RSA's key math work, and both are statements about modular exponentiation.

Practice Questions

Recall

State the definition of $a \equiv b \pmod n$ in two equivalent ways.

Answer: (1) $n$ divides $a - b$; (2) $a$ and $b$ have the same remainder when divided by $n$.

Understanding

Compute $85 \bmod 7$ and $-13 \bmod 7$.

Answer: $85 = 7 \times 12 + 1$, so $85 \equiv 1 \pmod 7$. For $-13$: add 14 to get 1, so $-13 \equiv 1 \pmod 7$. (Both equal 1.)

Application

Find the last two digits of $3^{20}$.

Guidance: Work mod 100. $3^{10} = 59049 \equiv 49 \pmod{100}$. Then $3^{20} = (3^{10})^2 \equiv 49^2 = 2401 \equiv 1 \pmod{100}$. The last two digits are 01.

Analysis

Explain why $4x \equiv 2 \pmod 6$ has solutions but $4x \equiv 3 \pmod 6$ has none.

Guidance: $\gcd(4,6) = 2$. A congruence $ax \equiv b \pmod n$ is solvable iff $\gcd(a,n)$ divides $b$. Since $2 \mid 2$, the first has solutions ($x = 2$ and $x = 5$). Since $2 \nmid 3$, the second is unsolvable — $4x$ mod 6 is always even, never 3.

FAQ

Is "mod" an operation or a relation? Both, and it confuses everyone at first. "$a \bmod n$" (the operation) returns the remainder, a single number in $0$ to $n-1$. "$a \equiv b \pmod n$" (the relation) says two numbers share that remainder. Context and notation tell them apart.

Why does the clock use mod 12 but the military uses mod 24? They are just different moduli for the same idea. A 12-hour clock wraps every 12 hours; a 24-hour clock every 24. Both are modular arithmetic on the hours.

Can the modulus be negative or zero? By convention the modulus is a positive integer (at least 1, and usually at least 2 to be interesting). Mod 0 would mean no wrapping — ordinary equality. Negative moduli add nothing new since $\bmod (-n)$ behaves like $\bmod\, n$.

Do calculators do modular arithmetic? Most have a "mod" function or you can compute $a - n \lfloor a/n \rfloor$. Programming languages have a % operator, though be careful: some languages return negative results for negative inputs, unlike the standard math convention.

Why is prime modulus special in cryptography? When $n$ is prime, every nonzero residue has a multiplicative inverse, so $\mathbb{Z}_p$ behaves like a "field" — you can divide freely. This clean structure supports Fermat's Little Theorem, Diffie-Hellman key exchange, and much of modern cryptography.

Quick Revision

• $a \equiv b \pmod n$ means $n \mid (a - b)$ — same remainder.
• Congruence respects $+$, $-$, $\times$; reduce mod $n$ anytime to keep numbers small.
• Residues: every integer $\equiv$ exactly one of $0, \dots, n-1$.
• Inverse $a^{-1}$ exists iff $\gcd(a, n) = 1$; division = multiply by inverse.
• $ax \equiv b \pmod n$ solvable iff $\gcd(a,n) \mid b$.
• Fast powers: repeated squaring, reduce each step.
• Negatives: add the modulus to land in $0$ to $n-1$.
• Applications: check digits (mod 10), RSA (mod $n$), hashing (mod table size).

Related Topics

Prerequisites

• Number Theory overview

Related Topics

• Divisibility and the Euclidean algorithm (finds gcd and inverses)
• Prime numbers and factorization (the basis of RSA security)

Next Topics

• Fermat's Little Theorem and Euler's theorem
• The Chinese Remainder Theorem
• Introduction to cryptography and RSA