Difficulty: Introductory | Prerequisites: Basic integer arithmetic
This material sits at the very start of the number theory thread in Foundations of Computer Science. Division and modular arithmetic are the building blocks for everything that follows: primes, GCD algorithms, and eventually RSA encryption. If you are comfortable with integer division and remainders from secondary school, you have enough to begin. The concepts here reappear constantly in cryptography, hashing, and algorithm design, so nailing them early saves pain later.
Divisibility is the formal way of saying one integer goes into another with nothing left over. The division algorithm guarantees that for any integer divided by a positive integer, you always get a unique quotient and remainder. Modular arithmetic extends this by grouping integers into equivalence classes based on their remainders, and it is the mathematical engine behind cryptography and hashing.
Divisibility (a | b)
We say integer a divides integer b (written a | b) if there exists an integer k such that b = ka, and a is not zero. In simple terms, b splits evenly into groups of size a with nothing left over.
Dividend
The integer being divided. In the expression a = dq + r, the dividend is a. Think of it as the number you start with before dividing.
Divisor
The positive integer you divide by. In a = dq + r, the divisor is d. Think of it as the size of each group you are splitting into.
Quotient
The integer result of the division, ignoring the remainder. In a = dq + r, the quotient is q. Think of it as how many full groups fit.
Remainder
What is left after dividing. In a = dq + r, the remainder is r, and it always satisfies 0 <= r < d. Think of it as the leftover that did not fill a complete group.
Congruence modulo M (a ≡ b mod M)
Two integers a and b are congruent modulo M if M divides (a - b). In simple terms, a and b leave the same remainder when divided by M. This is the foundation of clock arithmetic: 15 and 3 are congruent mod 12 because they point to the same hour.
For integers a, b, c where a ≠ 0:
Additive closure: If a | b and a | c, then a | (b + c). If a divides two numbers individually, it divides their sum.
Multiplicative closure: If a | b, then a | bc for any integer c. Dividing b means dividing any multiple of b.
Transitivity: If a | b and b | c, then a | c. Divisibility chains together.
For any integer a and any positive integer d, there exist unique integers q (quotient) and r (remainder) such that:
a = dq + r, where 0 ≤ r < d
The word "algorithm" is slightly misleading here. This is a theorem guaranteeing existence and uniqueness, not a step-by-step procedure.
Worked examples:
101 ÷ 11: q = 9, r = 2, because 101 = 11(9) + 2
101 mod 11 = 2
-11 ÷ 3: q = -4, r = 1, because -11 = 3(-4) + 1
-11 mod 3 = 1 (note: the remainder is always non-negative)
If a ≡ b (mod M) and c ≡ d (mod M), then:
Addition preserves congruence: a + c ≡ b + d (mod M)
Multiplication preserves congruence: ac ≡ bd (mod M)
These properties mean you can reduce numbers mod M at any stage of a calculation without changing the final result. This is what makes modular arithmetic computationally practical: you never need to work with numbers larger than M.
Division Algorithm: a = dq + r, where 0 ≤ r < d
Divisibility notation: a | b means "a divides b", i.e. b = ka for some integer k
Congruence: a ≡ b (mod M) means M | (a - b)
Modular addition: If a ≡ b (mod M) and c ≡ d (mod M), then a + c ≡ b + d (mod M)
Modular multiplication: If a ≡ b (mod M) and c ≡ d (mod M), then ac ≡ bd (mod M)
Modular arithmetic is the engine behind hash tables: a hash function like h(k) = k mod 31 maps keys to table slots using remainders. Every time your code does a dictionary lookup, divisibility is doing the work underneath. Clock arithmetic (12-hour and 24-hour) is modular arithmetic in everyday life.
Students often think the remainder can be negative. It cannot: by definition, 0 ≤ r < d. For -11 mod 3, the answer is 1, not -2.
Students confuse "a divides b" (a | b) with "a divided by b" (a ÷ b). The notation a | b means b is a multiple of a, not the other way round.
Students assume the division algorithm is a procedure you run. It is a theorem stating existence and uniqueness. The name is historical.
Students forget that congruence mod M is a relation between two numbers, not a single-number property. Saying "7 is congruent mod 3" is incomplete; you need "7 ≡ 1 (mod 3)".
⚠️ Be ready to compute quotient and remainder for negative dividends. Lecturers test this because students get the sign wrong.
⚠️ Know the three divisibility properties (additive closure, multiplicative closure, transitivity) and be able to apply them in short proofs.
⚠️ Modular arithmetic properties (addition and multiplication preserving congruence) are tested directly and also appear embedded in RSA and hashing problems.
True or false: If 5 | 15 and 5 | 10, then 5 | 25. (True)
Fill in the blank: -17 mod 5 = ___. (3)
True or false: 14 ≡ 2 (mod 6). (True)
True or false: The remainder in the division algorithm can equal the divisor. (False, r < d strictly)
Fill in the blank: If a ≡ b (mod M), then M divides ___. (a - b)
Q: Apply the division algorithm to find the quotient and remainder when a = -23 and d = 7.
A: -23 = 7(-4) + 5, so q = -4 and r = 5.
Q: Prove that if 3 | n and 3 | m, then 3 | (2n + 5m).
A: Since 3 | n and 3 | m, by multiplicative closure 3 | 2n and 3 | 5m. By additive closure, 3 | (2n + 5m).
Q: Compute 47 mod 8 and 47 mod 12.
A: 47 = 8(5) + 7, so 47 mod 8 = 7. 47 = 12(3) + 11, so 47 mod 12 = 11.
Q: If a ≡ 3 (mod 7) and b ≡ 5 (mod 7), what is ab mod 7?
A: ab ≡ 3 × 5 = 15 ≡ 1 (mod 7).
This material feeds directly into primes and the Euclidean algorithm, which rely on repeated application of the division algorithm to compute GCDs. Modular arithmetic is the language of RSA encryption: every step of key generation, encryption, and decryption is a modular operation. Hash functions in data structures use the mod operator to map keys to array indices.
Divisibility, divides, division algorithm, quotient, remainder, modular arithmetic, mod, modulo, congruence, clock arithmetic, equivalence classes, integer division, a divides b, a | b, mod M, number theory, HSK3X, Foundations of Computer Science, Purdue