Divisibility rules: 2 through 13 and beyond

A whole number (up to 60 digits)

 Check it

7412,0135,068123,123918,0821,936

Show all the working

Nothing you type here leaves your browser.

These divisibility rules let you tell whether a number divides another one without doing the division. Type any number above and the checker runs every rule from 2 to 13 on its digits and shows the working. Below that, each rule gets a worked example and a line on why it isn't magic. They're the same tricks the prime number game teaches, and they're the fastest way to rule out a number that only looks prime.

The rules at a glance

2, 5 and 10: the last digit

These three work because 10 = 2 × 5. Every multiple of 10 is divisible by 2 and by 5, so only the last digit can make a difference. An even last digit means divisible by 2, a 0 or a 5 means divisible by 5, and a 0 means divisible by 10. That's the entire rule, and it's why every card in the prime game is odd and none ends in 5: the last digit would give the answer away.

3 and 9: add the digits

Add up the digits. If the sum is in the 3 times table, so is the number, and the same goes for 9. Take 741: 7 + 4 + 1 = 12, and 12 = 3 × 4, so 741 = 3 × 247. The sum 12 isn't in the 9 times table, so 9 doesn't divide it. For 4,527 the sum is 18, which is 9 × 2, and 4,527 = 9 × 503. If the sum is still long, add its digits again.

Here's why. 10 leaves a remainder of 1 when divided by 3, and so do 100, 1,000 and every other power of ten. So each digit contributes just itself to the remainder, and the number leaves the same remainder as its digit sum. The same is true for 9, because 10 leaves 1 there as well.

4 and 8: the last few digits

100 is a multiple of 4 and 1,000 is a multiple of 8, so only the end of the number matters. For 4, look at the last two digits. For 8, look at the last three. Take 1,936. The last two digits are 36 = 4 × 9, so 4 divides it, and the last three are 936 = 8 × 117, so 8 does too. That gives 1,936 = 4 × 484 = 8 × 242.

6 and 12: combine two rules

When a divisor is a product of numbers with nothing in common, the number has to pass both rules. 6 = 2 × 3, so 5,274 works: it's even, and 5 + 2 + 7 + 4 = 18. Therefore 5,274 = 6 × 879. 12 = 3 × 4 (not 2 × 6, which share a factor and don't give a valid test). For 3,252, the digits add up to 12 and the last two digits are 52 = 4 × 13, so 3,252 = 12 × 271.

7: double the last digit and subtract

Cut off the last digit, double it and subtract it from the rest. Repeat until the number is small enough to recognize. If you land on a multiple of 7 (0 counts), the number you started with is one too. For 203: 20 − 2 × 3 = 14, which is 2 × 7, so 203 = 7 × 29. A longer one, 5,068: 506 − 2 × 8 = 490, then 49 − 2 × 0 = 49 = 7 × 7, so 5,068 = 7 × 724.

The reason is one line of algebra. Write the number as 10a + b, with b the last digit. Then 10a + b = 10(a − 2b) + 21b. The 21b is always a multiple of 7, and 10 has no factor of 7, so 7 divides the number exactly when it divides a − 2b.

11: alternate the digits

Start at the right and add the first digit, subtract the second, add the third, and so on. If the result is 0 or a multiple of 11, the number is divisible by 11. For 2,013 that's 3 − 1 + 0 − 2 = 0, so 2,013 = 11 × 183. For 918,082 it's 2 − 8 + 0 − 8 + 1 − 9 = −22, a multiple of 11, and 918,082 = 11 × 83,462. The reason: 10 leaves a remainder of −1 when divided by 11, so each place flips the sign.

13: multiply the last digit by 4 and add

This is the mirror of the rule for 7. Cut off the last digit, multiply it by 4 and add it to the rest, then repeat. For 2,431: 243 + 4 × 1 = 247, then 24 + 4 × 7 = 52 = 4 × 13, so 2,431 = 13 × 187. It works because 4(10a + b) = 39a + (a + 4b), and 39 is a multiple of 13.

The same trick extends. For 17 subtract 5 times the last digit, and for 19 add 2 times the last digit. 3,247 gives 324 − 5 × 7 = 289 = 17 × 17, so 17 divides it, and 3,287 gives 328 + 2 × 7 = 342 = 18 × 19, so 19 divides that one.

7, 11 and 13 together: the 1,001 shortcut

7 × 11 × 13 = 1,001, and 1,000 is one less than 1,001. So split a number into groups of three digits from the right and alternate adding and subtracting them. The result leaves the same remainder as the original does when divided by 1,001, and so the same remainders for 7, 11 and 13. For 123,123 you get 123 − 123 = 0, so all three divide it, and it's just 123 × 1,001. Numbers shaped like abcabc, and 7,007 or 12,012, are always multiples of 1,001. For 7,654,321 the groups give 321 − 654 + 7 = −326, which tells you the remainders for all three divisors at once.

Spot the squares

The rules for 3, 7, 11 and 13 catch 9, 49, 121 and 169 like any other multiple. But the square of a bigger prime, such as 17² = 289, has no small factor for a rule to find, so it slips past all of them. Learn the squares of the primes up to 31: 289, 361, 529, 841 and 961, along with 121 and 169. Those seven are the squares of primes between 100 and 1,000.

Near a square: Fermat's trick

If a number is the product of two primes of similar size, it sits just under a square, and no divisibility rule will help. Take the square above it, subtract the number, and check whether what's left is a square. For 221: 15² = 225, 225 − 221 = 4 = 2², so 221 = 15² − 2² = (15 − 2)(15 + 2) = 13 × 17. For 1,517: 39² = 1,521, and 1,521 − 1,517 = 4, so 1,517 = 37 × 41. It also cracks 10,403: 102² = 10,404, one more, so 10,403 = 101 × 103. Pierre de Fermat described the method in the 1600s, and it's why an RSA key built from two primes that sit close together is weak (see RSA primes).

When there's no trick: stop at the square root

If a number has any factor besides 1 and itself, it has one no bigger than its square root, because two factors both above the root would multiply to something bigger than the number. So you never test past the root. For a number under 100 the primes to check are 3 and 7 (2 and 5 are done by the last digit). Under 1,000 you stop at 31, which is 9 primes. Under 10,000 you stop at 97, which is 23 primes, and under a million at 997, which is 166 primes. That's a lot by hand and nothing for a computer, which is why the prime checker can test a 300-digit number in a blink. The sieve of Eratosthenes does the same job for a whole range at once.

Where the shortcuts run out

Everything above proves a number is composite when it works, and says nothing when it doesn't. A number that passes all the rules for small primes can still be composite, like 1,517 (37 × 41). Another shortcut, the Fermat test, can even say "prime" for a composite: numbers such as 561 pass it for every base that shares no factor with them. They're called Carmichael numbers, and the table on the game page shows how badly 561 fools it. For the exact answer on any number, the prime factorizer gives the full factorization, and the GCD calculator finds what two numbers share.

Common questions