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.

Interestingly, you can repeat for longer numbers and it still works.
For 1512:
151-4=147
14-14=0
0 is divisible by 7, so 1512 is as well.

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:

*ZPN
ZZZZ
PZPN
NZNP

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.

*0123456
00000000
10123456
20246135
30362514
40415263
50531642
60654321

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)), 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.

Please do be so kind as to share this post.
Share

6 thoughts on “Divisibility!

  1. Okay, so my brain hurts, but this is making me wonder…

    Clock 10 has 9 numbers that have quick and dirty tricks to help you figure out divisibility. (Well, two gimmies and 7 others (2, 3, 4, 5, 6, 8, 9)) leaving only one number that is legitimately tricky.

    Is this representative of a pattern? I suppose that nobody uses any Clocks other than 10 with any frequency, though. Well, not to the point where we need to learn division…

      Quote  Link

    Report

    • The following are true for any base N:

      1. If M divides N evenly, you only need to check the units digit, because the rest is obviously divisible by M. In base 10, that gives us 2 and 5.
      2. If M is the k’th power of a number that divides N evenly, you only need to check the rightmost k digits, because the rest is obviously divisible by M. In base 10, that gives us 4 and 8.
      3. For N-1, you can do the trick of adding up all the digits.. In base 10, that gives us 9.
      4. If M is a root (square root, cube root, etc.) of N-1, you can also do the trick of adding up all the digits. In base 10, that gives us 3.
      5. For N+1, you can do the trick of subtracting the sum of the even digits from the sum of the odd digits. In base 10, that gives us 11.
      6. If M is a root (square root, cube root, etc.) of N+1, you can also do the trick of subtracting the sum of the even digits from the sum of the odd digits. That doesn’t help in base 10, because 11 is prime, but in base 8 that would give us 3.
      7. If M is K*L, and K and L are relatively prime, and there are tests for both of those, do both tests. In base 10, that gives us 6.

      7 is tricky because none of these apply.

      So, looking at some other simple bases:

      • Base 4 has tricks for 2 by rule 1, 3 by rule 3, and 5 by rule 5.
      • Base 6 has tricks for 2 and 3 by rule 1, 4 by rule 2, 5 by rule 3, and 7 by rule 5.
      • Base 8 has tricks for 2 and 4 by rule 1, 3 by rule 6, 6 by rule 7, 7 by rule 3, and 9 by rule 5. 5 is tricky.
      • Base 12 has tricks for 2, 3, 4, and 6 by rule 1, 8 and 9 by rule 2, 11 by rule 3, and 13 by rule 5. 5, 7, and 10 are tricky.

        Quote  Link

      Report

Leave a Reply

Your email address will not be published. Required fields are marked *