Skip to content
Tutorials Center
My learning

Topics

Lesson 6 of 37 ยท Divisibility and Primes

Divisibility Tests and Why They Work

Learn the divisibility rules for 2, 3, 4, 5, 8, 9, 11 and 7 or 13, see the place-value proofs behind them, and build a general test in Python.

You probably know that a number is divisible by 5 if it ends in 0 or 5, and by 3 if its digits add up to a multiple of 3. These shortcuts are not magic. Each one comes from how our decimal place-value system works, and once you see the reason you can invent a rule for any divisor.

This lesson explains the common rules, proves them, and then builds a program that checks every rule against direct division.

Place value is a sum of powers of ten

A number with digits dโ‚– ... dโ‚ dโ‚€ equals dโ‚€ + 10ยทdโ‚ + 100ยทdโ‚‚ + ... + 10แตยทdโ‚–. Every divisibility rule studies how the powers 1, 10, 100, 1000, ... behave with respect to a divisor m.

Rules for 2, 4, 5, 8 and 10

The powers of ten are multiples of 2 and 5 from 10 onward: 10 = 2ยท5. So for divisors that are powers of 2 or 5 only the last few digits matter.

  • 2, 5, 10: look at the last digit. 10, 100, ... are multiples of 10, so they cannot change divisibility by 2, 5 or 10.
  • 4 and 25: 100 is a multiple of 4 and 25, so look at the last two digits.
  • 8 and 125: 1000 is a multiple of both, so look at the last three digits.

For example, 7,312 is divisible by 8 because 312 = 8 ยท 39.

Rules for 3 and 9: add the digits

Since 10 = 9 + 1, we get 10 = 1 + 9, 100 = 1 + 99, 1000 = 1 + 999 and so on. Each power of ten is 1 more than a multiple of 9. Therefore a number equals its digit sum plus a multiple of 9:

n = (dโ‚€ + dโ‚ + ... + dโ‚–) + 9ยท(something)

So n is divisible by 9 exactly when its digit sum is, and since 3 divides 9 the same reasoning works for 3. This also gives the old trick of "casting out nines" for checking arithmetic.

The rule for 11: alternate the signs

Because 10 = 11 โˆ’ 1, we have 10 โ‰ก โˆ’1, 100 โ‰ก +1, 1000 โ‰ก โˆ’1 and so on, in the sense that each power of ten is within a multiple of 11 of ยฑ1. So n is divisible by 11 exactly when the alternating digit sum dโ‚€ โˆ’ dโ‚ + dโ‚‚ โˆ’ ... is divisible by 11. For 918,082: 2 โˆ’ 8 + 0 โˆ’ 8 + 1 โˆ’ 9 = โˆ’22, a multiple of 11, so 11 divides it.

Python Digit-based tests versus real division

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

7 and 13: a rule built from 1001

Here is a rule the tables often skip. Since 1001 = 7 ยท 11 ยท 13, the number 1000 is one less than a multiple of 7, 11 and 13, that is 1000 โ‰ก โˆ’1 for each of them. Split the number into groups of three digits from the right, and alternately add and subtract the groups. The result is divisible by 7, 11 or 13 exactly when the original number is.

Take 2,358,014. Groups: 2, 358, 014. Alternating sum: 14 โˆ’ 358 + 2 = โˆ’342. Now 342 leaves remainder 6 when divided by 7, remainder 1 by 11 and remainder 4 by 13, so 2,358,014 is divisible by none of them. The short number โˆ’342 is much easier to test than the original.

Python The 1001 rule

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each pair of Booleans agrees, as the proof says it must.

Inventing a rule for any divisor

The pattern is always the same: find how powers of 10 behave with respect to m. If 10สฒ is a multiple of m for some j, only the last j digits matter (m = 2, 4, 5, 8, 16, 20, 25 ...). If 10 โ‰ก 1 mod m (m divides 9) you add digits. If 10 โ‰ก โˆ’1 mod m (m divides 11) you alternate. For 6 combine the rules for 2 and 3: a number is divisible by 6 exactly when it is divisible by both, because 2 and 3 are coprime. The same trick builds 12 (3 and 4), 15 (3 and 5) and so on, but it does not work for 4 and 6 to give 24, because 4 and 6 share the factor 2.

Python Which composite rules are valid?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The test says (4, 6) is invalid because "divisible by 4 and 6" only gives divisibility by 12 (their lcm), not 24. A combined rule for m = aยทb needs gcd(a, b) = 1.

Divisibility rules at a glance

2, 5, 10 Check the last digit.
4, 8 Last two or three digits.
3, 9 Add the digits.
11 Alternate the signs.

Every rule comes from how 10 behaves modulo the divisor.

1 / 2

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does the digit sum decide divisibility by 9?

    10, 100, 1000... each leave remainder 1 when divided by 9, so n has the same remainder as its digit sum.
  2. 2. Is 918082 divisible by 11?

    2 - 8 + 0 - 8 + 1 - 9 = -22, which is a multiple of 11.
  3. 3. Which pair can safely be combined into a test for their product?

    The two factors must be coprime. gcd(3, 8) = 1, but the other pairs share a factor.
  4. 4. Why does the 1001 rule work for 7, 11 and 13?

    1000 is congruent to -1 modulo each of them, so alternately adding and subtracting three-digit groups preserves remainders.

Summary

  • Decimal place value is a sum of powers of ten, so every digit rule studies how 10สฒ behaves modulo the divisor.
  • 2, 4, 5, 8 depend on the last one to three digits; 3 and 9 on the digit sum; 11 on the alternating sum.
  • Since 1001 = 7 ยท 11 ยท 13, alternating sums of three-digit groups test 7, 11 and 13.
  • A rule for aยทb is the combination of rules for a and b only when gcd(a, b) = 1.
  • Check any rule against n % m == 0 on a range.

Next: Prime Numbers and the Sieve of Eratosthenes