Quick Divisibility Test for Primes up to 67

While there’s known divisibility tests for certain primes (see my notes), the following test very quickly determines if a number is divisible by any prime up to 67 by hand! The original method is due to John Conway, and I learned it from Arthur Benjamin.

Here’s a sample problem along with explanation:

63779 is the product of three primes, each less than . Determine their sum.

We set up the equation , where and are primes.

We begin by finding the factor of 2000 closest to 63, namely 64,000. We can therefore rewrite this as

We can quickly determine that since and , . We now add , the quotient in the divisibility above to both sides of the equation to produce:

Notice the factor of and the left hand side have both increased, while our original number, 63779 has remained the same. Now, as any good contest math student should have the years close to the current year memorized, we know Therefore , however, . Similarly . This time, , therefore . We’ve found one prime divisor: .

We could now divide by , however, this gives the equation , and we don’t have any better ideas for how to factorize . Therefore, instead, we’ll use the prime factorizations of some other numbers close to :

and

For instance, to determine if our number is divisible by , we would take the original equation and subtract to produce Then, we know , however, clearly .

Similarly, to test if our number is divisible by or , we simply add to our original equation to produce . Therefore, again , however, clearly , hence the same is true for .

Next, to determine if the original number is divisible by or , we add to our original equation (or more simply, to the equation in the last paragraph) to get

Since , we see , however, clearly . Similarly, . Now since , we see , hence , and . We’ve therefore found a second prime factor: .

At this point that we have two prime factors, we could continue on with our test, but we have a pretty good idea of what the third factor is by division: . One way to quickly compute this in our heads would be to notice

Since we know is an integer, we attempt to bound it. We know . We notice , while , therefore, .  We then subtract from both sides of our equation:

While we could compute the numerator mentally, since we know , we know it must be a single numerical digit! We therefore just consider the unit digit of the numerator which is . Since we’re dividing by a number which ends in , we know must be , since . Therefore .

Hence our desired sum is .

Alternatively, we could verify using the prime factorization of next year, 2021. I’ll leave this as an exercise for anyone interested.

While this method isn’t super practical, I think it’s interesting that you can essentially compute prime factors up to 67 with a quick trick in your head. The most difficult part is memorizing the prime factorizations of the numbers close to 2000, but hopefully this is familiar for any seasoned contest mathematician (who might be interested in using this).

References: Arthur Benjamin, Factoring Numbers with Conway’s 150 Method
The College Mathematics Journal, Vol. 49, No. 2, pp. 122-125, March 2018.