Difficulty: Intermediate | Prerequisites: Basic algebra, Chapter 3 (algorithm analysis)
Tags: divisibility, modular arithmetic, congruence, division algorithm, mod, primes, composite, GCD, greatest common divisor, fundamental theorem of arithmetic, Sieve of Eratosthenes, Mersenne primes, number theory, integer representations, binary, octal, hexadecimal, CS182, discrete math, Purdue
Number theory is the mathematical foundation for cryptography, hashing, error detection, and computer arithmetic. This chapter covers divisibility (who divides whom), modular arithmetic (clock arithmetic), and primes (the building blocks of all integers). If you have ever wondered why RSA encryption works, or how a hash function distributes keys, or why your computer uses binary, this chapter supplies the underlying theory. You should already be comfortable with basic algebra and the concept of proof.
Divisibility tells you when one integer evenly divides another. The division algorithm guarantees a unique quotient and remainder. Modular arithmetic lets you work with remainders as a self-contained number system. Every integer greater than 1 factors uniquely into primes, and there are infinitely many primes.
Divides (a | b)
For integers a and b with a ≠ 0, a divides b if there exists an integer c such that b = ac. We write a | b. If a does not divide b, we write a ∤ b. In simple terms, "a divides b" means b / a is a whole number with no remainder.
Factor / Divisor
If a | b, then a is called a factor (or divisor) of b, and b is called a multiple of a.
Division algorithm
For every integer a and positive integer d, there exist unique integers q (quotient) and r (remainder) with 0 <= r < d such that a = dq + r. Think of it as: divide a by d, and you always get a clean quotient plus a leftover that is between 0 and d - 1.
Quotient (q = a div d)
The integer part when a is divided by d.
Remainder (r = a mod d)
The leftover when a is divided by d. Always satisfies 0 <= r < d.
Congruence (a ≡ b (mod m))
For integers a, b and positive integer m, a is congruent to b modulo m if m divides a - b. Equivalently, a and b have the same remainder when divided by m. In simple terms, a and b land on the same spot on a clock with m hours.
mod m vs (mod m)
Two different uses of "mod." In "a mod m = b," mod is a function that returns the remainder. In "a ≡ b (mod m)," (mod m) describes a relation between a and b.
Arithmetic modulo m (Z_m)
The set {0, 1, 2, ..., m-1} with addition and multiplication defined by taking the result mod m. For example, 7 +₁₁ 9 = (7 + 9) mod 11 = 5.
Prime
A positive integer p greater than 1 whose only positive factors are 1 and p. In simple terms, a prime cannot be broken into smaller whole-number factors.
Composite
A positive integer greater than 1 that is not prime (it has factors other than 1 and itself).
Fundamental Theorem of Arithmetic
Every positive integer greater than 1 can be written uniquely as a prime or as a product of primes in non-decreasing order.
Sieve of Eratosthenes
An ancient algorithm for finding all primes up to a given integer n by iteratively crossing out multiples.
Mersenne primes
Primes of the form 2ᵖ - 1, where p itself is prime. The largest known primes tend to be of this form.
For integers a and b with a ≠ 0, a divides b (written a | b) means there exists an integer c with b = ac.
3 | 12 is true (12 = 3 × 4)
3 | 7 is false (7/3 is not an integer)
Properties of Divisibility (Theorem 1): Let a, b, c be integers with a ≠ 0.
If a | b and a | c, then a | (b + c)
If a | b, then a | bc for all integers c
If a | b and b | c, then a | c (transitivity)
Proof sketch for the first property: if b = as and c = at, then b + c = a(s + t), so a | (b + c).
Corollary: If a | b and a | c, then a | (mb + nc) for all integers m and n.
For every integer a and positive integer d, there exist unique integers q and r with 0 <= r < d such that a = dq + r.
d is the divisor, a is the dividend, q is the quotient, r is the remainder
q = a div d
r = a mod d
Examples:
101 divided by 11: q = 9, r = 2 (since 101 = 11 × 9 + 2)
-11 divided by 3: q = -4, r = 1 (since -11 = 3 × (-4) + 1). Note the remainder must be non-negative.
a ≡ b (mod m) means m | (a - b). Equivalently, a mod m = b mod m.
17 ≡ 5 (mod 6) because 6 | (17 - 5) = 12. True.
24 ≢ 14 (mod 6) because 24 - 14 = 10, which is not divisible by 6.
Theorem 3: a ≡ b (mod m) if and only if a mod m = b mod m.
Theorem 4: a ≡ b (mod m) if and only if there is an integer k such that a = b + km.
Theorem 5: If a ≡ b (mod m) and c ≡ d (mod m), then:
a + c ≡ b + d (mod m)
ac ≡ bd (mod m)
Example: since 7 ≡ 2 (mod 5) and 11 ≡ 1 (mod 5), we get 18 = 7 + 11 ≡ 3 (mod 5) and 77 = 7 × 11 ≡ 2 (mod 5).
Multiplying both sides by an integer preserves the congruence: if a ≡ b (mod m), then ca ≡ cb (mod m).
Adding an integer to both sides preserves the congruence: c + a ≡ c + b (mod m).
Dividing both sides does NOT always preserve the congruence. Example: 14 ≡ 8 (mod 6), but 7 ≢ 4 (mod 6).
Z_m = {0, 1, 2, ..., m - 1} with operations:
a +_m b = (a + b) mod m
a ×_m b = (a × b) mod m
Properties: closure, identity elements (0 for addition, 1 for multiplication), additive inverses (the inverse of a is m - a), associativity, commutativity, distributivity.
Corollary 2: a + b (mod m) = ((a mod m) + (b mod m)) mod m, and ab (mod m) = ((a mod m)(b mod m)) mod m. This is useful for computing with large numbers.
Theorem 1: Let b > 1 be a positive integer. Any positive integer n can be expressed uniquely as n = a_k × bᵏ + a_{k-1} × bᵏ⁻¹ + ... + a₁ × b + a₀, where each a_i satisfies 0 <= a_i < b.
Common bases: decimal (b = 10), binary (b = 2), octal (b = 8), hexadecimal (b = 16).
A prime p > 1 has only 1 and p as positive factors. A composite number has additional factors.
Infinitude of primes: proven by contradiction (Euclid's argument).
Fundamental Theorem of Arithmetic: every integer > 1 has a unique prime factorisation (up to ordering).
100 = 2² × 5²
641 = 641 (prime)
999 = 3³ × 37
Sieve of Eratosthenes: to find all primes up to n, list integers from 2 to n. Starting with 2, cross out all its multiples. Move to the next uncrossed number and repeat. Only need to check up to √n.
Mersenne Primes: primes of the form 2ᵖ - 1, where p is prime. Not every such value is prime, but the largest known primes are Mersenne primes.
Prime Number Theorem: the number of primes not exceeding x is approximately x / ln x. The probability that a randomly selected positive integer less than n is prime is roughly 1 / ln n.
Division algorithm: a = dq + r, where 0 <= r < d
Congruence: a ≡ b (mod m) ⟺ m | (a - b)
Modular arithmetic shortcut: (a + b) mod m = ((a mod m) + (b mod m)) mod m
Prime counting: π(x) ≈ x / ln x
Modular arithmetic is the mathematical engine behind RSA encryption, digital signatures, and hash functions. Every time you use HTTPS, modular exponentiation is happening behind the scenes. Binary representation is how every computer stores data. The Sieve of Eratosthenes is used in practice to generate prime tables for cryptographic key generation.
"Division of congruences always works." It does not. Dividing both sides of a congruence by an integer can produce an invalid result. Example: 14 ≡ 8 (mod 6) but 7 ≢ 4 (mod 6).
"mod is always a function." The word "mod" has two uses. In "a mod m = r" it is a function returning the remainder. In "a ≡ b (mod m)" it describes a relation.
"Negative numbers have no remainder." They do; the remainder is always non-negative. For -11 divided by 3, the quotient is -4 and the remainder is 1 (not -2).
"2ᵖ - 1 is always prime when p is prime." Not true. For example, 2¹¹ - 1 = 2047 = 23 × 89. The primality of p is necessary but not sufficient.
⚠️ Be able to compute quotient and remainder, including for negative dividends.
⚠️ Know both uses of "mod" and be able to distinguish them in context.
⚠️ Be able to prove divisibility properties using the formal definition (b = ac).
⚠️ Understand that division of congruences is not always valid.
⚠️ Know the Fundamental Theorem of Arithmetic and be able to find prime factorisations.
⚠️ Be comfortable with modular arithmetic operations in Z_m.
True or False: 5 | 35.
Fill in the blank: -17 divided by 5 gives quotient ______ and remainder ______.
True or False: If a ≡ b (mod m), then 2a ≡ 2b (mod m).
Fill in the blank: The Fundamental Theorem of Arithmetic says every integer greater than 1 can be written uniquely as a product of ______.
True or False: There are finitely many prime numbers.
Answers: 1. True. 2. q = -4, r = 3. 3. True. 4. primes. 5. False (there are infinitely many).
Q: Show that 17 ≡ 5 (mod 6).
A: 17 - 5 = 12, and 6 | 12 (since 12 = 6 × 2). So 17 ≡ 5 (mod 6).
Q: Compute 7 +₁₁ 9 and 7 ×₁₁ 9.
A: 7 +₁₁ 9 = (7 + 9) mod 11 = 16 mod 11 = 5. 7 ×₁₁ 9 = (7 × 9) mod 11 = 63 mod 11 = 8.
Q: Find the prime factorisation of 999.
A: 999 = 3 × 333 = 3 × 3 × 111 = 3 × 3 × 3 × 37 = 3³ × 37.
Q: Why can you not divide both sides of 14 ≡ 8 (mod 6) by 2?
A: Dividing gives 7 and 4. But 7 - 4 = 3, and 6 does not divide 3, so 7 ≢ 4 (mod 6). Division by a number that shares a common factor with the modulus can break the congruence.
Modular arithmetic connects to cryptography applications covered in more advanced courses. The division algorithm and congruence are used in hashing (Chapter 3 algorithms). Primes connect to the counting material in Chapter 6 (how many primes are there below n?) and to induction proofs in Chapter 5 (proving the infinitude of primes by contradiction).
divisibility, divides, factor, divisor, multiple, division algorithm, quotient, remainder, mod, modulo, congruence, congruent modulo m, Z_m, modular arithmetic, additive inverse, prime, composite, prime factorisation, Fundamental Theorem of Arithmetic, Sieve of Eratosthenes, Mersenne prime, Prime Number Theorem, binary, octal, hexadecimal, base conversion, integer representation, CS 182, Purdue, discrete math