A Mental Trick for Checking Primeness of Two-Digit Numbers

Is 57 prime? How about 71?

If you aren’t sure (like me), then read on. Here’s a trick for quickly checking two-digit numbers for primality.

I’ll first cover how it works, before finally showing how to apply it.

Overview

It boils down to this: a two digit number is prime if it’s not divisible by any of 2, 3, 5, or 7. I’ll explain why later.

We can break this test down into easier parts:

Divisibility by 2 and 5: This can be done instantly, by inspection.
… by 3: There’s a simple test you can apply
… by 7: You can memorise this bit

I’ll explain each of these in more detail shortly.

You may ask: “Why not just memorise the list of all 21 two digit primes?”. I’d wager that this method is much easier to remember, and much more likely to stay remembered.

That’s because instead of remembering 21 numbers, I just need to remember the “seed” of the method: It’s only necessary to check divisibility by 2, 3, 5, and 7. The rest of the method follows from that fact.

Later

So why do we only need to check 2, 3, 5, and 7? Because…

Any composite (non-prime) number has a prime factor less than its square root
All two-digit numbers are less than 100
The square-root of 100 is 10
Therefore all two-digits numbers have a square root less than 10
Therefore, all two-digit composite numbers have a prime factor less than 10.

Finally, the only primes less than 10 are 2, 3, 5, and 7.

You might not be convinced by the first statement- that a composite number \(n\) has a prime factor less than \(\sqrt n\) - so we’ll prove it by contradiction.

First, observe that a composite number \(n\) has at least two factors by definition:

\[n = ab\]

Suppose \(a \gt \sqrt n\) and \(b \gt \sqrt n\). Then \(ab \gt (\sqrt n)^2\), and so \(ab \gt n\).

However, our premise was that \(ab = n\), so we’ve reached a contradiction. Therefore, either \(a \leq \sqrt n\) or \(b \leq \sqrt n\).

Neither \(a\) nor \(b\) must be prime, but if composite they must have a smaller prime factor - thus proving that \(n\) has a prime factor smaller than \(\sqrt n\).

Note that this doesn’t mean the prime factors of two-digit numbers are all less than 10. Only one of \(a \leq \sqrt n\) or \(b \leq \sqrt n\) need be true. For example, \(91 = 13 \times 7\), and \(13 > \sqrt{100}\)

Shortly

Now we know checking divisibility 2, 3, 5, and 7 is sufficient, we want to make it quick.

Divisibility by 2 or 5 is as simple as checking the final digit. If it’s even, or 5, it’s not prime.

Divisibility by 3 has a simple test: sum the digits of your number. If that sum is divisible by 3, then so is the number.

Divisibility by 7 is harder. The divisibility test on Wikipedia is not so easy to do in your head. However, once you’ve eliminated the numbers divisible by 2, 3, and 5, there are only 3 left which are divisible by 7!

Those are:

\(49 = 7 \times 7\)
\(77 = 7 \times 11\)
\(91 = 7 \times 13\)

Of these, 49 and 77 are pretty clearly not prime - at least, I would recognise these as being \(7^2\) and \(7 \times 11\).

I don’t know a trick other than memorisation for \(7 \times 13 = 91\), but it doesn’t seem too high a price to pay.

Finally

To summarise, here’s how you check a two-digit number for primeness:

A two-digit number is prime if you answer no to all these questions:

Is it even? (i.e., does it end in 0, 2, 4, 6, or 8?)
Does it end in 5?
Does the sum of its digits divide by 3?
Is it 49, 77, or 91?

Although this looks like a lot of text, this is pretty straightforward to apply. After a couple minute’s practice, it can be done in just a few seconds.

Let’s apply it to the original question: Is 57 prime? How about 71?

Let’s begin with 57:

It’s not even
It doesn’t end in 5
Its digits sum to 12, which is divisible by 3

Therefore, it’s not prime. \(57 = 19 \times 3\)

Now for 71:

It’s not even
It doesn’t end in 5
Its digits sum to 8, which isn’t divisible by 3
It’s not 49, 77, or 91

Therefore, 71 is prime.

Hopefully you’re convinced this is pretty straightforward to do in your head: after all, steps 1, 2, and 4 don’t really take any time at all. Only step 3 is a bit indirect, but adding two digits together isn’t too bad!

—