Multiples, divisors and division with remainder
We work with natural numbers ℕ = {0, 1, 2, 3, …} and integers ℤ = {…, −2, −1, 0, 1, 2, …}.
b divides a (written b | a) if a = b × k for some integer k. Then b is a divisor (factor) of a, and a is a multiple of b. Example: 3 | 12 because 12 = 3 × 4.
Division with remainder: for any whole number a and b > 0 there is exactly one pair q, r with a = b × q + r and 0 ≤ r < b. q is the quotient and r the remainder. 14 = 4 × 3 + 2. b divides a exactly when r = 0.
Facts: 1 divides every number; every number divides 0; if b | a and b | c then b | (a + c) and b | (a − c).
Even and odd numbers, with simple proofs
An even number is a multiple of 2: n = 2k. An odd number leaves remainder 1: n = 2k + 1.
Proof that even + even is even: 2a + 2b = 2(a + b), a multiple of 2.
Proof that odd × odd is odd: (2a + 1)(2b + 1) = 4ab + 2a + 2b + 1 = 2(2ab + a + b) + 1, which is odd.
Proof that n(n + 1) is always even: of two numbers in a row, one is even, so the product has a factor 2.
To prove a statement, write the numbers with letters (2k, 2k + 1, 3k …) and rearrange; one example never proves a rule, but one counter-example disproves it.
Divisibility tests for 2, 3, 4, 5, 6, 8, 9, 10 and 11
| By | Test | Example |
|---|---|---|
| 2 | last digit 0, 2, 4, 6, 8 | 358 ✓ |
| 3 | sum of digits divisible by 3 | 471: 4+7+1 = 12 ✓ |
| 4 | last two digits divisible by 4 | 1316: 16 ✓ |
| 5 | last digit 0 or 5 | 945 ✓ |
| 6 | divisible by 2 and by 3 | 714 ✓ |
| 8 | last three digits divisible by 8 | 5120: 120 ✓ |
| 9 | sum of digits divisible by 9 | 3825: 18 ✓ |
| 10 | last digit 0 | 860 ✓ |
| 11 | alternating sum of digits (from the right: + − + …) divisible by 11 | 2728: 8 − 2 + 7 − 2 = 11 ✓ |
Why 3 and 9 work: 10 = 9 + 1, 100 = 99 + 1, 1000 = 999 + 1, and 9, 99, 999 are multiples of 9. So a number and its digit sum leave the same remainder when divided by 9 (or 3).
Why 11 works: 10 = 11 − 1, so powers of 10 leave remainders +1, −1, +1, … on division by 11.
Why 4 and 8 work: 100 is a multiple of 4 and 1000 is a multiple of 8, so only the last two (or three) digits matter.
Primes, GCD, LCM and coprime numbers
A prime has exactly two divisors, 1 and itself (2, 3, 5, 7, 11, 13 …). Every number above 1 is a product of primes in only one way: 360 = 2³ × 3² × 5.
GCD (greatest common divisor, also HCF) of a and b: the biggest number that divides both. Take the common primes with the smaller powers. 72 = 2³ × 3², 60 = 2² × 3 × 5 → GCD = 2² × 3 = 12.
LCM (least common multiple): the smallest number both divide. Take every prime with the bigger power: LCM = 2³ × 3² × 5 = 360.
Always GCD(a, b) × LCM(a, b) = a × b: 12 × 360 = 72 × 60 = 4320.
Coprime numbers have GCD 1, like 8 and 15 (they share no prime). A fraction is in lowest terms when its top and bottom are coprime: divide both by their GCD. 60/72 → ÷12 → 5/6.
Euclid's algorithm and integer equations
Key fact: GCD(a, b) = GCD(b, r), where r is the remainder of a ÷ b. So keep dividing until the remainder is 0; the last non-zero remainder is the GCD.
GCD(252, 198): 252 = 198 × 1 + 54; 198 = 54 × 3 + 36; 54 = 36 × 1 + 18; 36 = 18 × 2 + 0 → GCD = 18.
In the 3D, this is cutting the biggest squares from a rectangle again and again.
Integer (Diophantine) equations ax + by = c have whole-number solutions only if GCD(a, b) divides c. 6x + 9y = 20 has none (3 does not divide 20). 3x + 5y = 1 has x = 2, y = −1; all solutions are x = 2 + 5t, y = −1 − 3t.
Try it
Take 30 small things (beans, coins). Try to share them into equal groups of 2, 3, 4, 5, 6, 7. Which sizes leave nothing over? Those are divisors of 30. Write your phone's last four digits and test them for 3, 4, 9 and 11 using the rules, then check with a calculator.
Key formulas and definitions
- b | a ⇔ a = b × k for an integer k
- Division with remainder: a = b × q + r, 0 ≤ r < b
- Even: 2k; odd: 2k + 1
- GCD(a, b) = GCD(b, a mod b)
- GCD(a, b) × LCM(a, b) = a × b
- ax + by = c has integer solutions ⇔ GCD(a, b) | c
Worked examples
1. Divide 59 by 7 with remainder.
7 × 8 = 56, 59 − 56 = 3. So 59 = 7 × 8 + 3; quotient 8, remainder 3.
2. Is 7 128 divisible by 8? By 9?
Last three digits 128 = 8 × 16, so yes for 8. Digit sum 7 + 1 + 2 + 8 = 18, divisible by 9, so yes for 9.
3. Is 91 916 divisible by 11?
From the right: 6 − 1 + 9 − 1 + 9 = 22, a multiple of 11. Yes.
4. Find the GCD and LCM of 84 and 120 using primes.
84 = 2² × 3 × 7, 120 = 2³ × 3 × 5. GCD = 2² × 3 = 12. LCM = 2³ × 3 × 5 × 7 = 840. Check: 12 × 840 = 10 080 = 84 × 120.
5. Find GCD(391, 299) with Euclid's algorithm.
391 = 299 × 1 + 92; 299 = 92 × 3 + 23; 92 = 23 × 4 + 0. GCD = 23.
6. Prove that the sum of three consecutive integers is divisible by 3.
Call them n, n + 1, n + 2. Sum = 3n + 3 = 3(n + 1), a multiple of 3.
7. Find the digit x so that 4x56 is divisible by 9.
4 + x + 5 + 6 = 15 + x must be a multiple of 9. 15 + x = 18 → x = 3. Number: 4356.
Common mistakes
- Using the digit-sum test for 4 or 8. Digit sums work only for 3 and 9.
- Saying a number divisible by 2 and 4 is divisible by 8. 12 is divisible by 2 and 4 but not by 8 (2 and 4 are not coprime).
- Writing a remainder bigger than the divisor, like 30 = 7 × 3 + 9. The remainder must be less than 7: 30 = 7 × 4 + 2.
- Calling 1 a prime. A prime needs exactly two divisors; 1 has only one.