A week after the Fourth of July, a lesser-known but certainly-important holiday occurs each year. Tomorrow, friends, is 7-11, a day to enjoy free Slurpees at 7-11 stores, to roll some dice at the craps table, and to honor your favorite prime numbers. So to celebrate 7-11, let’s talk about these two important prime numbers.
Checking Whether A Number Is Prime
Consider a number like 133. Is that number prime? The first three prime numbers (2, 3, and 5) are easy to check to see whether they are factors (if any are, then the number is clearly not prime):
2 – this number is not even, so it’s not divisible by 2.
3 – the sum of the digits (an important rule for divisibility by three!) is 7, which is not a multiple of 3 so this number is not divisible by 3.
5 – the number doesn’t end in 5 or 0, so it’s not divisible by 5
But now things get a bit trickier. There are, in fact, (separate) divisibility “tricks” for 7 and 11. But they’re relatively inefficient compared with a universal strategy. Find a nearby multiple of the target number, then add or subtract multiples of that target number. If we want to test 133 to see whether it’s divisible by 7, we can quickly go to 140 (you know this is a multiple of 7) and then subtract by 7. That’s 133, so you know that 133 is a multiple of 7. (Doing the same for 11, you know that 121 is a multiple of 11 – it’s 11-squared – so add 11 more and you’re at 132, so 133 is not a multiple of 11)
This is even more helpful when, for example, a question asks something like “how many prime numbers exist between 202 and 218?”. By finding nearby multiples of 7 and 11:
210 is a multiple of 7, so 203 and 217 are also multiples of 7
220 is a multiple of 11, so 209 is a multiple of 11
You can very quickly eliminate numbers in that range that are not prime. And since none of the even numbers are prime and neither are 205 and 215 (the ends-in-5 rule), you’re left only having to check 207 (which has digits that sum to a multiple of 3, so that’s not prime), 211 (more on that in a second), and 213 (which has digits that sum to 6, so it’s out).
So that leaves the process of testing 211 to see if it has any other prime factors than 2, 3, 5, 7, and 11. Which may seem like a pretty tall order. But here’s an important concept to keep in mind: you only have to test prime factors up to the square root of the number in question. So for 211, that means that because you should know that 15 is the square root of 225, you only have to test primes up to 15.
Why is that? Remember that factors come in pairs. For 217, for example, you know it’s divisible by 7, but 7 has to have a pair to multiply it by to get to 217. That number is 31 (31 * 7 = 217). So whatever factor you find for a number, it has to multiply with another number to get there.
Well, consider again the number 211. Since 15 * 15 is already bigger than 211, you should see that for any number bigger than 15 to be a factor of 211, it has to pair with a number smaller than 15. And as you consider the primes up to 15, you’re already checking all those smaller possibilities. That allows you to quickly test 211 for divisibility by 13 and then you’re done. And since 211 is not divisible by 13 (you could do the long division or you could test 260 – a relatively clear multiple of 13 – and subtract 13s until you get to or past 211: 247, 234, 221, and 208, so 211 is not a multiple of 13. Therefore 211 is prime.
By Brian Galvin