Quickly recognizing primes less than 1000: divisibility tests

I took a little hiatus from writing here since I attended the International Conference on Functional Programming, and since then have been catching up on teaching stuff and writing a bit on my other blog. I gave a talk at the conference which will probably be of interest to readers of this blog—I hope to write about it soon!

In any case, today I want to return to the problem of quickly recognizing small primes. In my previous post we considered “small” to mean “less than 100”. Today we’ll kick it up a notch and consider recognizing primes less than 1000. I want to start by considering some simple approaches and see how far we can push them. In future posts we’ll consider some fancier things.

First, some divisibility tests! We already know how to test for divisibility by $2$ , $3$ , and $5$ . Let’s see rules for $7$ , $11$ , and $13$ .

To test for divisibility by $7$ , take the last digit, chop it off, and subtract double that digit from the rest of the number. Keep doing this until you get something which obviously either is or isn’t divisible by $7$ . For example, if we take $2952$ , we first chop off the final 2; double it is 4, and subtracting 4 from $295$ leaves $291$ . Subtracting twice $1$ from $29$ yields $27$ , which is not divisible by $7$ ; hence neither is $2952$ .

As an optimization, we can always reduce things mod 7. For example, if we see the digit 7, we can just throw it away; if we see an 8 or 9 we can treat it as 1 or 2, respectively. And if we see a 3, the rule would tell us to subtract 6, but if it’s easier we can add 1 instead, since subtracting 6 and adding 1 are the same mod 7. With a bit of practice this can be done quite quickly.

For an explanation of why this works, and several other fun methods for testing divisibility by 7, see this post by Mark Dominus.
To test a $3$ -digit number for divisibility by $11$ , just add the first and last digits and then subtract the middle digit. The original number is divisible by 11 if and only if the result is.

This is especially obvious with numbers like $187$ , where the sum of the first and last digits is equal to the middle digit. (Subtracting the middle digit would leave 0, which is divisible by 11.) But it also applies in cases like $517$ : we have $5 + 7 - 1 = 12 - 1 = 11$ .

The reason this works is that $10$ is equivalent to $-1 \pmod{11}$ , so $a \cdot 10^2 + b \cdot 10 + c \equiv a \cdot (-1)^2 + b \cdot (-1) + c \equiv a - b + c \pmod{11}$ . This also suggests how to generalize to more than just 3-digit numbers: just alternately add and subtract digits.
To test for divisibility by $13$ , chop off the last digit, multiply it by $4$ , and add it to the remaining number. Keep doing this until you end up with something that you know either is or isn’t divisible by $13$ .

Here reducing mod $13$ can be even more helpful. For example, if the last digit is a $7$ , the rule says to add $28$ to what’s left. But $28$ is only 2 more than $2 \times 13 = 26$ , so adding $28$ is equivalent to just adding $2$ .

Why does this work? Suppose the final digit of our number is $b$ and the rest of the number is $a$ . That is, our number is of the form $10a + b$ , and we want to know whether this is equivalent to $0 \pmod{13}$ . But now note that $10a + b \equiv 0 \pmod{13}$ if and only if $40a + 4b \equiv 0 \pmod{13}$ . Why? From left to right, we are just multiplying both sides by $4$ ; from right to left, we are allowed to divide by $4$ since $4$ is relatively prime to $13$ . So why did we choose to multiply by $4$ ? It’s because it lets us get rid of the $10$ : $40$ is the smallest multiple of $10$ which is one away from a multiple of $13$ . Hence $10a + b \equiv 0 \pmod{13}$ iff $40a + 4b \equiv 0 \pmod{13}$ iff $a + 4b \equiv 0 \pmod{13}$ .

(Challenge: can you go back now and prove the test for divisibility by $7$ ?)

At this point we might ask: if we take a number less than $1000$ and test it for divisibility by $2$ , $3$ , $5$ , $7$ , $11$ , and $13$ , what’s left? In other words, what are the composite numbers under $1000$ that we haven’t found yet? It turns out there are $27$ of them: 289, 323, 361, 391, 437, 493, 527, 529, 551, 589, 629, 667, 697, 703, 713, 731, 779, 799, 817, 841, 851, 893, 899, 901, 943, 961, and 989. I’ll let you work out the factorizations; of course each one is a product of two primes which are at least $17$ .

So we could try to memorize this list and call it a day. Then the procedure becomes: given a number less than $1000$ , (1) test it for divisibility by all primes up to 13, and (2) check if it is one of the 27 composite numbers we have memorized. If it passes both tests, then it is prime. This sounds doable, though honestly I’m not super excited about memorizing a list of 27 composites.

There are a few more things we could do, though. First of all, notice that the divisibility test for 19 is super easy, since 19 is one less than 2 times 10: chop off the last digit, double it, and add it to the rest. Keep doing this until… you know the drill. This is just like the test for 7, but we add instead of subtract.

OK, so what if we test for all primes up to 13 and also 19? Then there are only 18 composites left that we have to memorize: 289, 391, 493, 527, 529, 629, 667, 697, 713, 731, 799, 841, 851, 899, 901, 943, 961, and 989. This is looking a bit better, and I am already noticing lots of patterns that would help with memorization: 529 and 629; 713 and 731; 899 and 901… oh, and $289 \to 391 \to 493$ (since $102$ is $6 \times 17$ ). (…and it turns out that before publishing this post I couldn’t help myself and went ahead and memorized the list. It wasn’t that hard. I’ll say more about it in a future post!)

We could also test for divisibility by 17, of course. Unfortunately it is a bit more annoying: the smallest multiple of 10 which is one away from a multiple of 17 is 50, which is one less than $3 \times 17 = 51$ . So, to test for divisibility by 17, we chop off the last digit, multiply by 5, and subtract. This seems distinctly harder to do in my head than the other tests, because it seems to actually require dealing with two-digit numbers. If we do this, though, we are down to only 9 composites to memorize, which is not bad at all: 529, 667, 713, 841, 851, 899, 943, 961, 989.

3 Responses to Quickly recognizing primes less than 1000: divisibility tests

Pingback: Quickly recognizing primes less than 1000: memorizing exceptional composites | The Math Less Traveled
Jamie Hope says:

October 18, 2018 at 10:20 am

Have you looked at numbers expressed in bases other than 10? In hexadecimal (and binary), obviously it’s trivial to identify multiples of powers of 2 (and multiples of powers of 2, minus 1), but there are other simple tests analogous to the ones you discussed here.

For divisibility by 3, you can add the digits just like in base 10:
0x10*a+b = 0 (mod 3) => a+b = 0 (mod 3)

That also works for divisibility by N=5 and N=15, since 16 = 1+15 = 1+3*5:
0x10*a+b = 0 (mod N) => a+b = 0 (mod N)

For N=7 and N=9, 16a+b = 0 (mod N) => a+4b = 0 (mod N).
Pingback: Yes, I Am Late With The Comics Posts Today – nebusresearch

Comments are closed.