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.

About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in arithmetic, computation, primes and tagged , , , , . Bookmark the permalink.

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

  1. Pingback: Quickly recognizing primes less than 1000: memorizing exceptional composites | The Math Less Traveled

  2. Jamie Hope says:

    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).

Leave a reply. You can include LaTeX $latex like this$. Note you have to literally write 'latex' after the first dollar sign!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.