Divisibility!

Let’s start with a comment rescue. EB responded to the previous post on divisibility with:

No promises, but the trick I remember for 7 is:
Given n-digit number, take off the nth digit, multiply by 2, and subtract the product from the (n-1) digit number. If the result is divisible by 7, the original number is also divisible by 7.
So for the case of, say, 245:
5 x 2 = 10
24 – 10 = 14
14 is divisible by 7, so 245 is as well.
Lo and behold, 245/7=35.

I have no idea why this works.

I responded with an explanation, but it’s pretty ugly: lots of unintuitive, ad hoc algebraic manipulation. There’s a better way to get there, by taking a few detours along the way.

We’ll start with the notion of equivalence classes, which means that you take a set of things, divide it into disjoint subsets, and then treat each subset as a single object. The key is that there has to be some way that the members of each subset act like each other but differently from the members of the other subsets. Let’s take a simple example. Divide the real numbers into three subsets:

• The positive numbers (call them “P”)
• The negative numbers (“N”)
• zero (“Z”)

If we think about multiplication and ignore everything but the sign of the result, we’ve got a perfect example equivalence of classes. We can write out the multiplication table for Z, P, and N:

This works because we can let any positive number stand in for P and any negative number stand in for N, and know that (for example) P*N will be negative. We can’t do this for addition, though. 2 + -1 is positive, while 2 + -3 is negative. Knowing just the sign of the addends doesn’t tell us the sign of the sum.

Another example of equivalence classes is what’s called modulo arithmetic, where we pick a number (called the modulus) and separate the integers into subsets depending on their remainder when divided by the modulus. For any modulus N, the result is the subsets with remainders 0, 1, 2, … N-1, so there are N of them. In particular, for modulus 7, the equivalence classes are the ones with remainders 0 through 6. (Note that this still works for negative numbers. For, say, -5, we think of it as 7*-1 + 2, so the remainder is 2.) There’s some handy notation that goes with this. If two numbers x and y have the same reminder when divided by 7, we can write

x ≡ y (mod 7)

For instance

-5 ≡ 2 (mod 7)
7 ≡ 0 (mod 7)
355 ≡ 12 (mod 7)

There are a few interesting properties here. Suppose that x ≡ y (mod 7) so that they’re both in the subset with remainder q. Then there’s some j for which

x = j*7 + q

and some k for which

y = k*7 + q.

Thus

x – y = j*7 + q – (k*7 + q) = (j-k) * 7

In other words, their difference is a multiple of 7. It works the other way, too: if (x-y) is a multiple of 7, then x ≡ y (mod 7)

Let’s consider an x and y that might be in different subsets p and q. Then there are some j and k for which

x = 7*j + p
y = 7*k + q

Then

x * y = (7*j + p) * (7*k + q) = 49*j*k + 7*j*q + 7*k*p + p*q

Since all the terms but the last are divisible by 7, the remainder when z is divided by 7 depends only on p and q. That is, the subset x*y is in depends only on what subsets x and y are in, or

if x ≡ y (mod 7) and z ≡ w (mod 7), then x*z ≡ y*w (mod 7)

Thus these subsets are equivalence classes under multiplication: that is, once again we can make a multiplication table.

So if you (for instance) pick numbers x and y such that

x ≡ 3 (mod 7)
y ≡ 4 (mod 7)

than

x*y ≡ 5 (mod 7)

Let’s try one, just to be sure. 24 * 39 = 936 ≡ 5 (mod 7), since 936 = 133*7 + 5. As you’d expect.

Now we have enough machinery to get back to EB’s trick: take any number, remove the units digit, and subtract twice that from what’s left. That’s divisible by 7 exactly when the original number was.

Write the original number as 10*x + y. Now, subtracting a multiple of 7 (7*x) from this won’t change its remainder when divided by 7, so

10*x + y ≡ 3*x + y (mod 7)

We can multiply both sides by -2, and get

-2*(10*x + y) ≡ -6*x – 2*y (mod 7)

Once again we can add 7*x without affecting the remainder, so

-2*(10*x + y) ≡ x – 2*y (mod 7)

Looking at our multiplication table above, if you multiply a number with remainder 0 by 5 (we multiply by 5 because -2 ≡ 5 (mod 7[/efn_note], you get another number with remainder 0. And if you multiple a number with a non-zero remainder by 5, you get another number with a non-zero remainder. (The remainder will be different, but still non-zero.) In other words, 10*x + y will be divisible by 7 exactly when x – 2*y is divisible by 7.

Which is precisely EB’s trick.