Divisibility & the Division Algorithm

Number Theory & Cryptographic Math

Chapter 2 · Divisibility & the Division Algorithm

Everything in this course — modular arithmetic, the Euclidean algorithm, RSA itself — is ultimately built from one small idea: what does it actually mean for one whole number to divide another, and what can be guaranteed about the leftover when it doesn't divide evenly?

Divisibility, Defined Precisely

An integer a divides an integer b — written a | b — if there exists some integer k such that b = a × k. Read a | b as "a divides b," never as a fraction. 3 | 12 because 12 = 3 × 4; 5 ∤ 12 (5 does not divide 12) because no integer k makes 5k = 12.

The Division Algorithm: A Guarantee, Not Just an Operation

For any integer a (the dividend) and any positive integer d (the divisor), there exist unique integers q (quotient) and r (remainder) such that:

The division algorithm

a = d × q + r, where 0 ≤ r < d. Both existence and uniqueness are guaranteed — there is exactly one (q, r) pair satisfying this for any given a and d, never more than one and never none.

The uniqueness is what makes this a genuine theorem rather than just a description of long division — r is pinned down precisely by the requirement 0 ≤ r < d, ruling out every other way of splitting a into a multiple of d plus a leftover.

Verified directly, including the negative-dividend case

17 = 5×3 + 2 → q=3, r=2. 20 = 6×3 + 2 → q=3, r=2. And for a negative dividend: −7 = 3×(−3) + 2 → q=−3, r=2 — not q=−2, r=−1, since the rule 0 ≤ r < d rules that pairing out even though 3×(−2)+(−1)=−7 is also arithmetically true. −20 = 6×(−4) + 4 → q=−4, r=4.

A quiet win for Python, and a preview of Chapter 3

Python's own // and % already implement exactly this convention: -7 // 3 gives -3 and -7 % 3 gives 2, matching the mathematical division algorithm precisely. Not every language agrees — several truncate toward zero instead, giving a negative remainder for the same inputs. That difference matters enormously once remainders are used for anything beyond a leftover value, and Chapter 3 covers it directly.

Classic Divisibility Rules

Quick tests for divisibility by small numbers, without doing a full division — genuinely useful shortcuts, and a nice warm-up before the heavier machinery in later chapters:

Divisor	Rule
2	Last digit is even
3	Digit sum is divisible by 3
5	Last digit is 0 or 5
9	Digit sum is divisible by 9
10	Last digit is 0
11	Alternating digit sum (from the right) is divisible by 11

Verified directly, on n = 1,458

Last digit 8 (even) → divisible by 2. Digit sum 1+4+5+8=18, itself divisible by both 3 and 9 → divisible by 3 and 9. Last digit not 0 or 5 → not divisible by 5. Last digit not 0 → not divisible by 10. Alternating sum from the right (8−5+4−1=6) not divisible by 11 → not divisible by 11. Every rule matches the actual remainder computed directly.

Properties of Divisibility (Needed Later)

Three properties, each provable directly from the definition above (exactly the direct-proof style Discrete Mathematics Fundamentals built), that later chapters lean on without re-deriving:

If a | b and a | c, then a | (b + c) and a | (b − c)
If a | b, then a | (bc) for any integer c
If a | b and b | c, then a | c (transitivity)

Verified directly

Why these matter this early

Chapter 4's Euclidean algorithm proof and Chapter 8's Fermat's Little Theorem proof both lean directly on the transitivity property above — it's introduced here, plainly, so it's already familiar when it does real work later.

Why This Is the Foundation Everything Else Builds On

Chapter 3's entire subject — modular arithmetic — is literally "take the division algorithm's own remainder, and build an entire arithmetic system that only ever tracks that remainder." Chapter 4's Euclidean algorithm is nothing more than the division algorithm, applied over and over. Every % operator in every programming language is a direct, real-world implementation of the guarantee stated in this chapter.

The Division Algorithm in Code

def division_algorithm(a, d):
    # Python's own // and % already satisfy 0 <= r < d for d > 0
    q = a // d
    r = a - d * q
    assert 0 <= r < d
    return q, r

print(division_algorithm(17, 5))    # (3, 2)
print(division_algorithm(-7, 3))    # (-3, 2) -- NOT (-2, -1)
print(division_algorithm(-20, 6))   # (-4, 4)

Hands-On Exercises

Exercise 1

Using the division algorithm's own convention (0 ≤ r < d), find the unique q and r for a = −29, d = 4. Show that a = d×q + r holds, and explain why q=−7, r=−1 is not a valid answer even though 4×(−7)+(−1)=−29 is arithmetically true.

📄 View solution

Exercise 2

Using this chapter's own divisibility rules, determine whether n = 3,168 is divisible by 2, 3, 5, 9, 10, and 11 — show the specific rule check for each, then confirm every result against the actual remainder.

📄 View solution

Exercise 3

📄 View solution

Chapter 2 Quick Reference

Divisibility: a | b means b = a×k for some integer k
Division algorithm: for any integer a and positive d, unique q, r exist with a = dq + r, 0 ≤ r < d
Python's ///% already match this convention for negative dividends — not every language does (Chapter 3)
Divisibility rules for 2/3/5/9/10/11 — quick shortcuts, all verified against real remainders
Key properties: sum/difference rule, multiple rule, transitivity — used directly in Chapters 4 and 8
Next chapter: Modular arithmetic