The divisibility trick

January 7, 2014

You might have learned the “divisibility trick” in grade school. It says that if you want to know whether a number is divisible by 3, there is a shortcut: if the sum of its digits is divisible by 3 then the number itself is divisible by 3. For example, is 459 divisible by 3? Well, 4 + 5 + 9 = 18, which is divisible by 3, so 459 is divisible by 3 as well.

This trick also works with the number 9. Again, you can try it with 459.

A week or two ago I was reading Anthony Esolen’s “Word of the Day” blog in which he stated a result about the divisibility trick generalized to a base-X number system; namely, in a base-X number system the divisibility trick works for X-1 and its factors. I was intrigued, and, as I had given some thought to the divisibility trick a few years ago and had some notes on it, I sat down last night and came up with what I think is a sound proof of the claim.

I am sure there is a nice way to formulate the argument — my approach leans heavily on modular arithmetic, which is closely related to the elegant theory of cyclic groups — but I went about it in the most simpleminded way imaginable. You can read my argument here:

DivisibilityTrickBaseX [pdf, Updated]

An amusing application of this result is in a binary (base-2) number system. The claim simply says that any binary number for which the sum of its digits is divisible by 1 (which is all of them, since every positive integer is divisible by 1) is itself divisible by 1 (which is all of them, for the same reason). So the claim is almost empty in that case.

12 Responses to “The divisibility trick”

  1. Vince Says:

    Interesting! Thank you!

  2. cburrell Says:

    I expect you are one of the few who will have that response, so thank you.

  3. Christina Says:

    It saddens me that I used to know math and might have been able to follow your argument at one time. That time has apparently completely passed.

  4. cburrell Says:

    We’re all getting rusty, Christina, so don’t be too discouraged. If you know what the modulo operator does (basically, A mod z returns the remainder when A is divided by z), then there’s actually not much to my argument. I use three properties of the mod operator: (1) A mod z = (A mod z) mod z; (2) (A x B) mod z = (A mod z) x (B mod z); and (c) A mod ( y z ) = A mod y = A mod z.

    Or you could do something you enjoy instead, like find a way to turn table runners into placemats!

  5. Christina Says:

    LOL! Yes for all my aspirations of becoming an astrophysicist in my youth…it’s in matters of economia where I’ve come to find my calling.

  6. Vince Says:

    I’m having trouble with properties (2) and (3). 56 mod 5 = 1, but (7 mod 5) * (8 mod 5) = 6.

    Also, 2 = 56 mod 6 = 56 mod (2*3). 56 mod 2 = 0, 56 mod 3 = 2.
    Are there assumptions I’m missing?

  7. cburrell Says:

    Well, let’s see.

    I misstated (2): everything should be modulo z: (A B) mod z = ( A mod z ) (B mod z) ) mod z. I think it works then.

    As for (3)… confound it all. Ah, I see. My (3) only works if both factors (y and z) are factors of the integer quotient [floor(A/(yz))], but that won’t always be the case.

    Unfortunately I don’t have any time right now to think about this. As it stands, my argument is only valid for X-1, but not for its factors.

    Thanks! This is a fun challenge.

  8. cburrell Says:

    Vince, (3) works as long as A mod (yz) < y,z.

    Think of it this way: when A mod (yz) = 0 (there is no remainder) then (yz) is a factor of A. But then both y and z are also factors, so the relation as I stated it holds. This same argument works as A increases until the remainder becomes as large as one of the factors. Then the arithmetic modulo the factor starts wrapping but the arithmetic modulo the product doesn’t, so the expressions are no longer equal.

    In my argument, I need A mod (yz) = 1. Since 1 is always going to be less than the factors y,z (except in the trivial case where y or z = 1 (which I have to disallow)), the argument goes through.

    If I can figure out a slick way to prove all of that, I’ll modify the pdf. In the meantime, I’ll just fix it to state the tighter condition. Tonight, if I have time.

  9. cburrell Says:

    Alright, I updated the pdf to reflect the new and improved argument. I think I successfully showed that the modified version of (3) is true.

  10. Vince Says:

    Thanks! I look forward to looking all this over.

  11. Then there is this amazing result from string theory:

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: