Divisibility and the Division Algorithm: Notes and FAQs

We say an integer a divides b when there is some integer c with b = a times c — in other words, b is a multiple of a with no remainder. The division algorithm states that for any integers a and b with b greater than 0, there exist unique integers q (quotient) and r (remainder) such that a = bq + r with 0 ≤ r < b.

This matters because it is the rigorous foundation of remainders, which power modular arithmetic, hashing, cryptography and calendar calculations. "Unique q and r" is what makes the remainder a well-defined function instead of an ambiguous choice.

Key Concepts

• Divides: a divides b exactly when b = a times c for some integer c; e.g. 3 divides 12 but 3 does not divide 10.
• Multiple: b is a multiple of a exactly when a divides b.
• Quotient q: how many whole copies of b fit into a.
• Remainder r: the leftover, always satisfying 0 ≤ r < b.
• Divisor: a positive integer d with d dividing n is a divisor (factor) of n.

Formulas

• Division algorithm: a = bq + r, with 0 ≤ r < b; the pair (q, r) is unique for given a and b > 0.
• Divisibility test: a divides b exactly when the remainder of b divided by a is 0.
• Basic properties: if a divides b and b divides c then a divides c; if a divides b and a divides c then a divides (b times x + c times y) for any integers x, y.
• The remainder is never negative and never reaches b — this is what pins it down uniquely.

Worked Example

Divide a = 37 by b = 5. We need 37 = 5q + r with 0 ≤ r < 5. Since 5 times 7 = 35, take q = 7, giving r = 37 − 35 = 2, which satisfies the bound. For a negative dividend, a = −37, b = 5: q = −7 would give r = −37 + 35 = −2, which violates r ≥ 0, so we take q = −8: −37 = 5 times (−8) + 3, and r = 3 satisfies 0 ≤ 3 < 5. Uniqueness means no other (q, r) pair works.

Common Misconceptions

• "The remainder of −37 ÷ 5 is −2." Under the division algorithm the remainder is always non-negative: it is 3, not −2.
• "Division by zero gives remainder a." The division algorithm requires b > 0; division by zero is undefined.
• "If a divides b then a is smaller than b." Not necessarily: 5 divides 5, and −3 divides 12; divisibility is about multiples, not size.

Real-World Applications

• Euclid's algorithm for greatest common divisors, built entirely on repeated division with remainder.
• Hash tables and checksums, which map data to slots via remainders.
• Calendar arithmetic: "what day is 100 days from Monday?" is a division-algorithm question.

Divisibility (a divides b when b = a times c) and the division algorithm (a = bq + r, 0 ≤ r < b, unique q and r) turn "remainder" from a school procedure into a precise mathematical tool. Everything in modular arithmetic rests on this single theorem.