# Divisibility and the Division Algorithm

Mathematics I · Arithmetic and Number Theory · https://tryals.app/learn/mathematics-i/divisibility-and-the-division-algorithm

## Divisibility & the Division Algorithm

Number theory begins with **divisibility**. An integer $a$ **divides** $b$ (written $a \mid b$) if $b = ak$ for some integer $k$, meaning $b$ is a multiple of $a$ with no remainder. For example, $3 \mid 12$ because $12 = 3 \cdot 4$, but $3 \nmid 13$.

When $a$ does not divide $b$ exactly, the **division algorithm** governs the outcome. For any integer $b$ and positive integer $a$, there exist unique integers $q$ (**quotient**) and $r$ (**remainder**) such that:

$$b = aq + r, \quad 0 \le r < a$$

Divisibility is simply the special case where $r = 0$.

For $b = 17$ and $a = 5$, we write $17 = 5 \cdot 3 + 2$, yielding quotient $q = 3$ and remainder $r = 2$.

## Rules & Pitfalls

Divisibility relies on algebraic properties that streamline proofs and form the backbone of modular arithmetic:

| Property | Rule |
| --- | --- |
| **Sum/Difference** | If $a \mid b$ and $a \mid c$, then $a \mid (b \pm c)$ |
| **Transitivity** | If $a \mid b$ and $b \mid c$, then $a \mid c$ |
| **Absorption** | If $a \mid b$, then $a \mid bc$ for any integer $c$ |

> **Common Pitfall:** A **remainder** must strictly satisfy $0 \le r < a$. It is never negative and never equals or exceeds the divisor. 

Writing $17 = 5 \cdot 2 + 7$ is **incorrect** even though the arithmetic checks out, because $7 \ge 5$. The correct form is $17 = 5 \cdot 3 + 2$.

## Practice questions

5 of this lesson's 11 practice questions, with answers. The full set is in the app.

### 1. Select every integer below that divides 84.

A. 12
B. 8
C. 16
D. 21
E. 6
F. 14

**Answer:** A. 12; D. 21; E. 6; F. 14

**Why:** 84 = 2 x 2 x 3 x 7. So 6 = 2 x 3, 12 = 2 x 2 x 3, 14 = 2 x 7 and 21 = 3 x 7 all divide it. But 8 needs three 2s and 16 needs four, and 84 only has two, divisibility is decided by the prime supply, not by size.

Page: https://tryals.app/practice/mathematics-i/divisibility-and-the-division-algorithm/select-every-integer-below-that-divides-84

### 2. Order the steps of the proof that if a divides b and a divides c, then a divides b + c.

**Answer:**

1. Assume a divides b and a divides c
2. Write b = a m and c = a n for some integers m and n
3. Add them: b + c = a m + a n = a(m + n)
4. Note that m + n is an integer
5. Conclude that a divides b + c

**Why:** The pattern is: assume, unpack the definition, compute, check the result still fits the definition, conclude. The fourth step is not decoration, a(m + n) only witnesses divisibility because m + n is itself an integer.

Page: https://tryals.app/practice/mathematics-i/divisibility-and-the-division-algorithm/order-the-steps-of-the-proof-that-if-a-divides-b-and-a-divides-c

### 3. Since 47 = 6 x 6 + 11 is a true equation, it gives the quotient and remainder of 47 divided by 6.

**Answer:** False

**Why:** False. The arithmetic is correct (36 + 11 = 47) but 11 is larger than the divisor 6, so it is not a legal remainder. The division algorithm gives 47 = 6(7) + 5. This is exactly the trap the lesson warns about: a true equation is not automatically a valid division.

Page: https://tryals.app/practice/mathematics-i/divisibility-and-the-division-algorithm/since-47-6-x-6-11-is-a-true-equation-it-gives-the-quotient-and

### 4. The division algorithm insists the remainder satisfies 0 ≤ r < a. Both 17 = 5·3 + 2 and 17 = 5·2 + 7 are arithmetically correct. Why does only the first count?

A. Because the constraint is what makes quotient and remainder unique.
B. Because the algorithm requires the quotient to be as large as possible, and 3 exceeds 2.
C. Because 17 = 5·2 + 7 is arithmetically false, since 7 exceeds the divisor.
D. Because remainders must be prime, and 2 is prime while 7 is used in the wrong position.

**Answer:** A. Because the constraint is what makes quotient and remainder unique.

**Why:** Both equations are true arithmetic, and without the range condition you could also write 17 = 5·1 + 12, indefinitely, the constraint buys uniqueness, which is what lets 'the remainder' be spoken of at all. Note the negative case: −17 = 5·(−4) + 3 gives 3, and many languages return −2 instead, which is a frequent source of bugs.

Page: https://tryals.app/practice/mathematics-i/divisibility-and-the-division-algorithm/the-division-algorithm-insists-the-remainder-satisfies-0-r-a

### 5. A hash function reduces a key modulo the table size. Why do implementations favour a **prime** table size?

A. Because a composite size shares factors with patterned keys
B. Because primes guarantee no two keys ever collide
C. Because the table can only be resized correctly if its size is prime
D. Because prime numbers are computed faster by the processor

**Answer:** A. Because a composite size shares factors with patterned keys

**Why:** Keys are rarely random, they are IDs, addresses, timestamps, often sharing a factor. With size 100 every multiple of 10 lands in ten buckets and ninety sit empty; a prime shares no factor with the pattern, so the remainders spread. Number theory earning its keep in a data structure.

Page: https://tryals.app/practice/mathematics-i/divisibility-and-the-division-algorithm/a-hash-function-reduces-a-key-modulo-the-table-size-why-do