Is This Prime? - Puzzle Prime

In the past few days, I, my friends, and a whole lot of Twitter people have been trying to beat each other’s scores in the game “Is This Prime?”.

The game itself is simple; you are shown random integers on the screen and you need to guess whether they are prime or composite. Since most presented numbers are between 1 and 200, after a couple of games, players naturally memorize them. However, this is a good opportunity for students to review some main number division rules.

Numbers that end with an even digit are divisible by 2. If the number formed by the last 2 digits of a number is divisible by 4, the original number is also divisible by 4. If the number formed by the last 3 digits of a number is divisible by 8, the original number is also divisible by 8.
- 536 is divisible by 2 because 6 is an even digit
- 1348 is divisible by 4 because 48 is divisible by 4
- 71824 is divisible by 8 because 824 is divisible by 8
Numbers that end with 5 are divisible by 5. Numbers that end with 25, 50, 75, or 00 are divisible by 25.
- 45 is divisible by 5
- 675 is divisible by 25
Numbers whose sum of digits is divisible by 3 are divisible by 3. Numbers whose sum of digits is divisible by 9 are divisible by 9.
- 144 is divisible by 3 because 1+4+4=9 is divisible by 3
- 1638 is divisible by 9 because 1+6+3+8=18 is divisible by 9
If the difference between the sum of the digits in odd places and the sum of the digits in even places is divisible by 11, the number is divisible by 11.
- 121 is divisible by 11 because 1+1-2=0 is divisible by 11
- 209 is divisible by 11 because 2+9-0=11 is divisible by 11
- 1628 is divisible by 11 because 1+2-6-8=-11 is divisible by 11
If the number before the last digit minus twice the last digit is divisible by 7, the original number is also divisible by 7.
- 161 is divisible by 7 because 16-2×1=14 is divisible by 7
- 371 is divisible by 7 because 37-2×1=35 is divisible by 7
- 1589 is divisible by 7 because 158-2×9=140 is divisible by 7

All the rules above apply in both directions, e.g. if the sum of the digits of a number is not divisible by 9, then the number itself is also not divisible by 9. There are more complicated rules that apply to larger numbers but the chances are you will never get to use them. If you are curious to learn more about them, go to the bottom of this article.

Once we know the main number division rules well, we are ready to play the game! Here are a few tips for getting high scores:

Memorize as many numbers as possible. Knowing the multiplication table up to 10×10, it should be easy to learn by heart whether each number up to 100 is prime or composite.
Pay attention to the last digit. If it is 5, then the number is composite (unless it is =5).
Check whether the sum of the digits is divisible by 3. If it is, then the number is composite (unless it is =3).
If the number is between 100 and 300, check whether the sum of the first and the third digits equals the second digit. If this is true, then the number is divisible by 11, and therefore it is composite. 209 is the only other number in this range divisible by 11.

Good luck playing and let us know if you beat our personal record of 67 points!

Primes between 1 and 300:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199

211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293

Sneaky composites:

51, 57, 87, 91

119, 133, 161, 169

209, 217, 221, 247, 253, 259, 287, 289, 299

Some Math

Some of you may be wondering why the rules listed above work and whether we can create similar rules for larger numbers. Here are some explanations for the curious among you:

Rule for division by 3

Consider the 5-digit number ABCDE. It can be written as:

ABCDE = 10000A + 1000B + 100C + 10D + E

Since 10000 = 3 × 3333 + 1, 1000 = 3 × 333 + 1, 100 = 3 × 33 + 1, and 10 = 3 × 3 + 1, we can see that:

ABCDE = 3 × (3333A + 333B + 33C + 3D) + (A + B + C + D + E)

Therefore, ABCDE is divisible by 3 if and only if (A + B + C + D + E) is divisible by 3.

Rule for division by 11

Consider again the number ABCDE. Since 10000 = 11 × 909 + 1, 1000 = 11 × 91 – 1, 100 = 9 × 1 + 1, and 10 = 11 – 1, we can see that:

ABCDE = 11 × (909A + 91B + 9C + D) + (A – B + C – D + E)

Therefore, ABCDE is divisible by 11 if and only if (A – B + C – D + E) is divisible by 11.

Rule for division by 7

Once again, consider the number ABCDE. Notice that it can be written as:

ABCDE = 10 × ABCD + E

Now, let us find a number X such that 10X gives remainder 1 when divided by 7. Such number is X = 5. Indeed, 5 × 10 = 50 = 7 × 7 + 1. Therefore, the following statements are equivalent:

ABCDE = 10 × ABCD + E is divisible by 7
5 × ABCDE = 49 × ABCD + ABCD + 5E is divisible by 7
ABCD – 2E is divisible by 7

Rules for division by 13, 17, 19, etc.

The idea of the rule for division by 7 can be applied to rules for divisions by higher numbers. For example, here is how we can find a rule for division by 13:

Find the smallest positive integer X, so that 10X – 1 is divisible by 13. Such number is X = 4. Note that ABCDE is divisible by 13 if and only if 4 × ABCDE is divisible by 13.
Rewrite 4 × ABCDE as:
4 × ABCDE = 39 × ABCD + ABCD + 4E
Conclude that ABCDE is divisible by 13 if and only if ABCD + 4E is divisible by 13.

As an exercise, try to deduce a similar rules for division by 17 and 19! Note that for 17, instead of finding X, such that 10X – 1 is divisible by 17, you may get a simpler rule by finding X, such that 10X + 1 is divisible by 17.

For deeper understanding of how division of integers works, we recommend our more enthusiastic readers to look into Modular Arithmetic.