## Divisibility By 7 Revisited

One of the most-viewed posts on this blog describes a rule for checking whether a number is divisible by seven.

This post is about another, simpler way to do it.

Take a long number, say

$960,937,563,483$

One way to check if it’s divisible by $7$ is to subtract multiples of seven until you get down to something small. For example, $910,000,000,000$ is a multiple of seven because $91$ is. So subtract this number from the original to get $50,937,563,483$. Now subtract $49,000,000,000$ to get $1,937,563,483$, etc.

This procedure is fine for small numbers, but you’ll only eliminate one or two digits per subtraction. Here’s a method useful for very long numbers.

First, turn all the $7$‘s into $0$‘s, all the $8$‘s into $1$‘s, and all the $9$‘s into $2$‘s. This is just a simple case of the rule above – subtracting some multiples of $7$. The original number becomes

$260,230,563,413$

(If you want, you can take this step further by turning $6$ into $-1$, etc. I won’t do that here.)

Now break apart each group of three digits separated by parentheses, starting from the right. Put a negative sign on every other group of three digits, then add them all up.

$\begin{array}{cc} {} & +413 \\ {} & -563 \\ {} & +230 \\ + & \underline{-260} \\ {} & -180 \end{array}$

This number is divisible by $7$ if and only if the original is.

We need to check $-180$ for divisibility by $7$. Here, adding and subtracting multiples of $7$ is easy. For example, add $210$ to get $30$. Now subtract $28$ to get $2$. The remainder when you divide $960,937,563,483$ by $7$ is $2$.

If you want to use this rule, but the number of digits isn’t a multiple of three, you can simple add some zeros on front. For example,

$45,338,017$

turns into

$045,331,010$

and we get

$\begin{array}{cc} {} & +010 \\ {} & -331 \\+ & \underline{+045} \\ {} & -276 \end{array}$

$-276 + 280 = 4$, so the remainder when you divide $45,338,017$ by $7$ is $4$.

This rule works due to a convenient pattern in the remainders of the powers of ten.

If we start with $n = 0$, the remainder when you divide powers of $10$ by $7$ is

$1, 3, 2, -1, -3, -2, 1, 3, 2, -1, -3, -2, \ldots$

Each group of three digits, after alternating groups are multiplied by $-1$, has the same rule for divisibility by $7$. For example, the remainder when $124,000,000,000$ is divided by seven is the same as the remainder for $-124$. So we just take those groups of three and add them, simplifying the task greatly.