1
Divisibility is exact
b | a means the division leaves no remainder. It is a statement about integers, not an operation.
Lesson · Number Theory and Cryptography · Divisibility
Divisibility and the Division Algorithm
a = qb + r with 0 ≤ r < b, and both q and r are unique. That single theorem is the foundation of everything else in this course.
b | a means a = bk for some integer k
a = qb + r with 0 ≤ r < b q, r UNIQUE
the remainder is never negative
−7 = (−3)(3) + 2, so −7 mod 3 = 2
One theorem, used everywhere
Core ideas
What this lesson establishes
Divisibility is a relation on the integers, and the division algorithm is what makes it computable.
2
The remainder is unique and non-negative
That convention is what makes mod a function. −7 mod 3 is 2, not −1.
3
Divisibility is transitive and additive
d | a and d | b imply d | (ax + by) for any integers x, y. Almost every proof in this course uses that one line.
The material
Divisibility and division
The definition, the theorem, and the properties everything else rests on.
Definition · Divisibility
For integers a and b with b ≠ 0, b | a ("b divides a") means there is an integer k with a = bk. Then b is a divisor or factor of a.
Theorem · Basic properties
For integers a, b, c, d: if d | a and d | b then d | (ax + by) for all integers x, y; if a | b and b | c then a | c; and d | a with a ≠ 0 implies |d| ≤ |a|.
For the first: a = dm and b = dn, so ax + by = d(mx + ny), and mx + ny is an integer.
For the second: b = am and c = bn, so c = a(mn).
For the third: a = dk with a ≠ 0 forces k ≠ 0, so |k| ≥ 1 and |a| = |d||k| ≥ |d|.
□
The first property is the workhorse. It is what lets the Euclidean algorithm work, what proves Euclid's theorem on primes, and what makes Bézout's identity useful — and it is one line.
Theorem · Division algorithm
For any integer a and any positive integer b, there are unique integers q and r with a = qb + r and 0 ≤ r < b.
Existence. Let S = {a − qb : q ∈ ℤ, a − qb ≥ 0}. It is nonempty (take q very negative) and consists of non-negative integers, so by well-ordering (“The Well-Ordering Principle” in Induction and Recursion) it has a least element r = a − qb.
If r ≥ b then r − b = a − (q+1)b is in S and smaller than r, contradicting minimality. So 0 ≤ r < b.
Uniqueness. If a = qb + r = q'b + r' with both remainders in [0, b), then b(q − q') = r' − r. The right side has absolute value less than b, and the left is a multiple of b, so both are 0. Hence r = r' and q = q'.
□
Uniqueness is what makes the notation legitimate: a div b and a mod b name specific integers rather than one of several possibilities.
Negative dividends
Example · −7 divided by 3
−7 = (−3)(3) + 2, so q = −3 and r = 2. Not (−2)(3) + (−1), because the theorem requires 0 ≤ r < b. The quotient rounds toward negative infinity, not toward zero.
Many programming languages disagree with the theorem here: C-style % returns −1 for −7 % 3, while Python returns 2. The mathematical convention is Python's, and it is the one that makes modular arithmetic work — classes should not depend on the sign of a representative.
Definition · The mod operator
a mod b denotes the unique remainder r from the division algorithm, so 0 ≤ a mod b < b always.
Interactive
Number theory workbench
Algorithms with their traces
Method
Working with divisibility
Replace the statement by the equation it abbreviates.
1
Translate b | a into a = bk
Divisibility claims are unusable until unfolded. Almost every proof in this course starts here.
2
Use the linear-combination property
d | a and d | b give d | (ax + by). This is the step that appears in nearly every argument.
3
Apply the division algorithm when a remainder is needed
a = qb + r with 0 ≤ r < b, and both are unique.
4
Watch the sign
The remainder is never negative. If a computation produces one, add b.
Divisibility
Score 0 / 0Choose the answer you can justify.
Divisibility by 3, from the digits
Why the digit-sum test works, using nothing but this lesson's property.
Write n in base 10: n = d_k·10^k + … + d₁·10 + d₀
Each 10ⁱ − 1 is a string of nines: 9, 99, 999, … = 9·1, 9·11, 9·111, …
so 3 | (10ⁱ − 1) for every i ≥ 1 (and 10⁰ − 1 = 0)
n − (d_k + … + d₀) = Σ dᵢ · (10ⁱ − 1)
= a linear combination of multiples of 3
⟹ 3 | (n − digit sum)
So 3 | n ⟺ 3 | digit sum, by d | a and d | b ⟹ d | (a ± b)
Example: 4 728 → 4+7+2+8 = 21 → 3 | 21 ⟹ 3 | 4728
Check: 4728 = 3 × 1576 ✓
The whole argument is the linear-combination property used twice: once to see that Σ dᵢ(10ⁱ − 1) is a multiple of 3, and once to pass divisibility between n and its digit sum, whose difference that sum is. Nine divides every 10ⁱ − 1 too, so the same test works for 9. “Modular Arithmetic” will give the argument a notation — 10ⁱ ≡ 1 (mod 3) — that makes it one line, and will handle 11, where 10ⁱ − (−1)ⁱ is the multiple.
Common mistakes
1
Allowing a negative remainder−7 mod 3 = 2. Some programming languages disagree with the mathematical convention, and mixing the two silently breaks modular arithmetic.
2
Confusing b | a with b/aThe first is a statement (true or false); the second is a number. 3 | 12 is true and 3/12 is a quarter.
3
Forgetting b ≠ 0Divisibility by zero is undefined, and the division algorithm requires b > 0 as stated.
Check your understanding
✓
Finish when the linear-combination property is automatic.
Prove that if d | (a + b) and d | a then d | b. It is one application of the property, and it is the shape of argument that every lesson from “Primes and Unique Factorisation” to “Bézout's Identity and Modular Inverses” repeats.
Note: Everything in this course is a consequence of the division algorithm. The Euclidean algorithm is it applied repeatedly, modular arithmetic is its remainder, and RSA is modular arithmetic with large primes.