The smallest non-obvious composite

It’s been a while, I know.

My partner sent me a link to this tweet yesterday:

Testing divisibility by 17 is hard!  There’s a test: 10A + B is divisible by 17 if and only if A – 5B is.  (Proof: 10A + B is divisible by 17 if and only if 12(10A + B) is, since 12 and 17 are relatively prime; then observe 12(10A + B) – 17(7A + B) = A – 5B.). But nobody has internalized this test.

But 51 is also divisible by 3, and that’s easy to see if you know the usual test: a number is divisible by 3 if and only if the sum of its digits is.  5 + 1 = 6.

So assume you know this test. Also assume you know how to test for numbers that are divisible by 2 or 5 (you can look at the last digit), 11 (for two-digit numbers you can just check if the two digits are the same), and you know the squares.  Then the smallest number that looks prime but isn’t is the product of the first two distinct primes I haven’t mentioned, 7 × 13 = 91.

Back in 2016 Christian Lawson-Perfect collected data on this from a game he made that asked people which numbers were prime; 51 is the number people got wrong most often.  But 91 is the composite most often identified as prime that’s not a multiple of three.

57 also looks prime.

2 thoughts on “The smallest non-obvious composite

  1. I really enjoyed your article. I made a similar observation after making my “Is it a prime?” game. It s incredible that 101, 103, 107, 109 are all primes and this happens for 191, 193, 197, 199 but then doesn’t happen for a long while. Also 1001 is a composite of 3 distinct primes 7, 11 and 13 which I also found fascinating. 1231 and 1231231 are both primes but 1231231231 isn’t. 11 and 101 are prime but the next prime of the form 10^n + 1 doesn’t happen for a while (n=17?)

Leave a Reply

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 )

Facebook photo

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

Connecting to %s