# 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!

Paul —