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.