Testing for divisibility by 37

Here is a quick and easy trick for determining if a number is divisible by 37. The trick is designed for numbers longer than three digits. (For shorter numbers, it's very easy -- see below).

The method

1. Divide the number up in groups of three digits, starting from the right. (The left-most group may not have three digits.)
2. Add the groups together.
3. If the result is still longer than three digits, repeat steps 1 and 2.

When you finish this you have a three-digit (or smaller) number which can be quickly examined for divisibility by 37. The original number is divisible by 37 if and only if this three-digit number is.

For short numbers

For one-digit and two-digit numbers, it's pretty trivial: the only ones divisible by 37 are 37 and 74. For three-digit numbers what I do is compare the number to a nearby multiple of 37 -- in particular, a nearby multiple of 111. For example, 291 differs from 222 by 69, and 69 is not divisible by 37, so 291 is not divisible by 37. On the other hand, 925 differs from 999 by 74, so 925 is divisible by 37.

Examples

First let's do 9,138,431,772 (the phone number at Grace Pearson Scholarship Hall, where I spent my undergraduate days at the University of Kansas):

1. 9 + 138 + 431 + 772 = 1350
2. 1 + 350 = 351
3. 351 differs from 333 by 18
4. 18 is not a multiple of 37
5. Therefore 9,138,431,772 is not a multiple of 37

If Jenny, from the 1980s Tommy Tutone song, lived in Atlanta, her phone number would be 4,048,675,309:

1. 4 + 48 + 675 + 309 = 1036
2. 1 + 36 = 37
3. 37 is a multiple of 37
4. Therefore 4,048,675,309 is a multiple of 37

Why it works

Suppose you have a number D with four or more digits. This number can be written as 1000X + 100c + 10b + a, where a, b, and c are the last three (lowest order) digits, and X is the number formed by all the rest of the digits. For convenience of notation, let cba = 100c + 10b + a, not to be confused with c×b×a. In other words, D = 1000X + cba.

Since 999X is divisible by 37, subtracting it from D will not change the divisibility; i.e., D is equivalent to D - 999X, modulo 37. But D - 999X = X + cba, so this is just the same as adding the "front matter" onto the last three digits.

This doesn't quite show that the number can be broken completely down into three-digit parts before adding them all together, but if you've read this far without keeling over from boredom or confusion, then (1) you can probably see that it would generalize; and (2) you're probably capable of doing a more rigorous mathematical proof of the whole shebang than I am anyway.

Note

This trick occurred to me during a long drive home from a white water rafting trip in SW Pennsylvania (the lower Youghigheny River). After discovering the trick, I spent a few hours practicing by testing license plate numbers and tractor-trailer registration numbers for divisibility by 37. Don't ask me why I think about such things.