Difficulty: Introductory to Intermediate
Prerequisites: Basic integer arithmetic; comfort with proofs (direct proof by substitution). Chapter 3 notes on proof techniques are helpful.
Number theory is the mathematical backbone of computer science topics like cryptography (RSA, Diffie-Hellman), hashing, and error-correcting codes. This set of notes covers the first half of KR Chapter 4.1: how divisibility works, what the division algorithm guarantees, and how modular arithmetic lets you work with remainders systematically. If you have not seen formal definitions of "divides" or the mod operator before, start here. If you are already comfortable with those, you can skip ahead to the modular arithmetic or fast exponentiation sections.
Divisibility is a relationship between integers: a divides b means b is a whole-number multiple of a. The division algorithm formalises the idea of dividing with a remainder, guaranteeing a unique quotient and remainder for any integer divided by a positive integer. Modular arithmetic extends this into a system where you can add and multiply remainders and the results stay consistent, which is exactly what makes public-key cryptography possible.
Divides (a | b)
Let a and b be integers with a ≠ 0. We say a divides b if there exists an integer k such that b = ka. Written a | b.
In simple terms, b is a whole-number multiple of a, with nothing left over.
Factor / Divisor
If a | b, then a is called a factor (or divisor) of b.
Think of it as: the number you divide by, which goes in evenly.
Multiple
If a | b, then b is called a multiple of a.
In simple terms, b is what you get when you multiply a by some integer.
Does not divide (a ∤ b)
Written a ∤ b. Means there is no integer k satisfying b = ka.
Think of it as: dividing b by a leaves a remainder.
Dividend
In the expression a = dq + r, the integer a is the dividend, the number being divided.
Divisor (in the division algorithm)
The positive integer d in a = dq + r. The number you divide by.
Quotient (q)
The integer q in a = dq + r. Written q = a div d.
Think of it as: how many whole times d fits into a.
Remainder (r)
The integer r in a = dq + r, where 0 ≤ r < d. Written r = a mod d.
Think of it as: what is left over after dividing.
Congruent modulo M (a ≡ b (mod M))
Let a and b be integers and M a positive integer. a is congruent to b modulo M if M divides (a − b). Written a ≡ b (mod M).
In simple terms, a and b have the same remainder when divided by M.
If a and b are integers and a ≠ 0, then a divides b (written a | b) when there exists an integer k such that b = ka.
Example: 3 | 21 because 21 = 7 × 3. Here 3 is a factor of 21, and 21 is a multiple of 3.
Example: 3 ∤ 20 because no integer k satisfies 20 = k × 3.
Let a, b, and c be integers where a ≠ 0. Then:
Part (a): Divisibility distributes over addition
If a | b and a | c, then a | (b + c).
Proof: a | b means b = ma for some integer m. a | c means c = na for some integer n. Then b + c = (m + n)a, so a | (b + c).
Part (b): Divisibility scales under multiplication
If a | b, then a | bc for all integers c.
Proof: a | b means b = ma. Then bc = (mc)a, and mc is an integer, so a | bc.
Part (c): Divisibility is transitive
If a | b and b | c, then a | c.
Proof: a | b means b = ma. b | c means c = nb. Then c = nb = n(ma) = (nm)a, so a | c.
Let a be an integer and d be a positive integer. Then there exist unique integers q (quotient) and r (remainder) with 0 ≤ r < d, such that:
a = dq + r
Notation: q = a div d, and r = a mod d.
The key constraint is that the remainder r is always non-negative, even when a is negative. This catches many students out.
101 div 11 and 101 mod 11
101 = 11 × 9 + 2, so 101 div 11 = 9 and 101 mod 11 = 2.
−11 div 3 and −11 mod 3
−11 = 3 × (−4) + 1, so −11 div 3 = −4 and −11 mod 3 = 1.
Notice: the quotient is −4 (not −3), because the remainder must satisfy 0 ≤ r < 3. If you tried q = −3, you would get r = −11 − 3(−3) = −2, which is negative and violates the constraint.
Division Algorithm
a = dq + r, where 0 ≤ r < d
q = a div d
r = a mod d
Divisibility definition
a | b ⟺ b = ka for some integer k
Divisibility and the division algorithm underpin how computers handle clock arithmetic, memory addressing, and hash-table indexing. Every time a program uses the % (modulo) operator to wrap an array index or check whether a number is even, it is applying the division algorithm. These concepts are also the foundation for RSA encryption, where very large numbers are divided and remainders are computed to generate and verify keys.
Students often confuse the notation a | b ("a divides b") with ordinary division a / b. The vertical bar is a statement about a relationship (true or false), not an arithmetic operation that produces a decimal.
When computing (−11) mod 3, many students answer −2 instead of 1. The remainder in the division algorithm is always non-negative (0 ≤ r < d). You must choose the quotient so that the remainder lands in that range.
Students sometimes think "a divides b" means a is the larger number. In fact, if a | b, then |a| ≤ |b| (assuming b ≠ 0). The divisor is the smaller-or-equal number.
Transitivity of divisibility (if a | b and b | c then a | c) is sometimes confused with the additive property (part a of Theorem 1). They are separate results with different proofs.
⚠️ The three parts of Theorem 1 (additive closure, multiplicative closure, transitivity) are frequently tested as short proof exercises. Be ready to reproduce them from the definition of divisibility.
⚠️ Division algorithm problems with negative dividends (like −11 div 3) appear regularly because they test whether you understand the non-negative remainder constraint.
⚠️ Know the difference between the notation a | b (a divides b, a statement) and a mod b (the remainder, a number). Exams may ask you to evaluate one or prove the other.
True or false: 7 | 49.
True or false: If a | b, then b | a.
Fill in the blank: −17 mod 5 = ___.
True or false: If 4 | 12 and 4 | 8, then 4 | 20.
Fill in the blank: 200 div 13 = ___.
Answers: 1. True (49 = 7 × 7). 2. False (e.g. 3 | 12 but 12 ∤ 3). 3. 3 (because −17 = 5 × (−4) + 3). 4. True (by Theorem 1a). 5. 15 (because 200 = 13 × 15 + 5).
Q: Prove that if a | b and a | c, then a | (b − c).
A: Since a | b, we have b = ma for some integer m. Since a | c, we have c = na for some integer n. Then b − c = (m − n)a. Since m − n is an integer, a | (b − c).
Q: Compute 253 div 17 and 253 mod 17.
A: 17 × 14 = 238 and 253 − 238 = 15. So 253 div 17 = 14 and 253 mod 17 = 15.
Q: Compute −23 div 7 and −23 mod 7.
A: We need q such that 0 ≤ r < 7. −23 = 7 × (−4) + 5 (check: 7 × (−4) = −28, and −23 − (−28) = 5). So −23 div 7 = −4 and −23 mod 7 = 5.
Q: If 6 | n and 6 | m, does 6 | (3n + 2m)? Prove or give a counterexample.
A: Yes. By Theorem 1b, 6 | n implies 6 | 3n, and 6 | m implies 6 | 2m. By Theorem 1a, 6 | (3n + 2m).
Divisibility feeds directly into the GCD and Euclidean Algorithm material in KR 4.3. The division algorithm is the single step inside the Euclidean Algorithm, applied repeatedly. Modular arithmetic (covered in the companion notes) builds on the remainder concept here and is the basis for RSA encryption, which this course covers later.
divisibility, divides, factor, divisor, multiple, a divides b, a | b, does not divide, a ∤ b, division algorithm, dividend, quotient, remainder, div operator, mod operator, integer division, Theorem 1 divisibility properties, transitive divisibility, KR 4.1, Purdue CS Foundations, number theory, discrete mathematics