One of the traditional grumbles about divisibility rules is that in some cases - I’m looking at you, seven - there’s very little benefit to knowing the rule over “just” performing the division.

I have one exception to this rule, and while it’s still some work, it has two Very Nice Aspects to it:

  • The same rule works for 7, 11 and 13
  • The rule gives the remainder in each case.

The rule deals with groups of three digits at a time, and I’ll use the 12-digit number 322,592,801,163 for an example.

Starting with the last group, add up alternate groups of three digits: 163 + 592 = 755.

Then add up the remaining groups: 322 + 801 = 1123.

Subtract the second number from the first: 755 - 1123 = -368.

Optionally: add 1001 to make it positive: 633.

The resulting number is congruent to the original number, modulo 7, 11 and 13.

(In this case, it’s $3 \pmod 7$, $6 \pmod {11}$ and $9 \pmod {13}$.)

Why does it work?

There was a very broad hint in the “if you don’t like the negative” bit, wasn’t there? This works because 1001 is $7 \times 11 \times 13$, and the add-and-subtract rule is equivalent to efficiently subtracting multiples of 1001. You may, if you’re an interested reader, wish to prove this as an exercise.