Arithmetic
Divisibility
How to quickly check whether 123456 is divisible by 3? Column division takes time. But there's a trick: add the digits. 1+2+3+4+5+6 = 21, and 21 is divisible by 3. So the whole number is too! Divisibility rules are fast checks without any computation.
- **Verification:** checksums in bank account numbers
- **Cryptography:** searching for large prime numbers
- **Programming:** optimizing algorithms
What Is Divisibility
Can 12 candies be shared equally among 4 people? Yes, 3 each. What about 5 people? No - there would be a remainder. **Divisibility** is the ability to divide evenly, with no remainder.
**a is divisible by b** (written a ⋮ b) if there exists an integer k such that a = b × k. 12 ⋮ 4, because 12 = 4 × 3 12 is not divisible by 5 (remainder 2)
Divisibility is the foundation of number theory. It links division, multiplication, and the structure of the integers.
Which statement is true?
Divisibility Rules for 2, 5, 10
Dividing large numbers takes time. But there are quick **divisibility rules** - ways to check without actually dividing. Let's start with the simplest.
**Connection between the rules:** • Divisible by 10 → divisible by 2 AND by 5 • Divisible by 2 and by 5 → divisible by 10 10 = 2 × 5, so the rules are linked!
These rules follow directly from the decimal system. In other number systems the rules would be different!
The number 4782. Which of the following does it divide by?
Divisibility Rules for 3 and 9
Divisibility by 3 and 9 is checked not by the last digit, but by the **sum of all digits**. This elegant rule works because of the properties of the number 10.
**Recursive trick:** Is the digit sum of a large number still large? Sum its digits again! 123456789: 1+2+3+4+5+6+7+8+9 = 45 45: 4+5 = 9 → divisible by 9!
If a number is divisible by 9, it is automatically divisible by 3 (because 9 = 3 × 3). The converse is not true: 12 is divisible by 3 but not by 9.
Is 2718 divisible by 9?
Divisibility Rules for 4, 8, 11
The rules for 4, 8, and 11 are more involved, but follow the same logic: we use the properties of powers of 10.
**Why the rule for 11 works:** 10 = 11 - 1 100 = 99 + 1 = 11 × 9 + 1 1000 = 1001 - 1 = 11 × 91 - 1 Powers of 10 alternate: +1, -1, +1, -1... relative to multiples of 11.
For larger divisors the rules become unwieldy. In practice, for 7 or 13 it is easier to just divide in columns than to apply a rule.
Divisibility rules are just memory tricks
Divisibility rules follow from the properties of the decimal system
Every rule has a mathematical explanation. For example, the rule for 3 works because 10 ≡ 1 (mod 3), meaning 10 leaves remainder 1 when divided by 3. This turns any number into its digit sum modulo 3.
Is 1848 divisible by 4?
Key Ideas
- For 2, 5, 10 - check the last digit
- For 3, 9 - check the sum of all digits
- For 4 - check the last two digits; for 8 - three digits
- For 11 - alternating digit sum (odd positions minus even positions)
Related Topics
Divisibility is the foundation of number theory:
- Prime Numbers — Numbers with exactly two divisors
- GCD — Greatest Common Divisor
- Modular Arithmetic — Arithmetic of remainders
Вопросы для размышления
- Why is the divisibility rule for 7 not as simple as the one for 3?
- What would divisibility rules look like in the binary number system?
- Why do we need divisibility rules when we have calculators?