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.

### Like this:

Like Loading...

*Related*

This entry was posted on January 7, 2014 at 10:47 pm and is filed under Science.

Tags: Mathematics

January 8, 2014 at 1:22 pm

Interesting! Thank you!

January 8, 2014 at 1:33 pm

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

January 9, 2014 at 11:38 pm

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.

January 10, 2014 at 12:52 pm

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!

January 11, 2014 at 5:23 pm

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.

January 11, 2014 at 9:09 pm

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?

January 11, 2014 at 11:19 pm

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.

January 13, 2014 at 4:10 pm

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

untilthe 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.

January 14, 2014 at 5:56 pm

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.

January 18, 2014 at 2:06 am

Thanks! I look forward to looking all this over.

January 21, 2014 at 1:19 pm

Then there is this amazing result from string theory:

January 21, 2014 at 2:51 pm

That ‘=’ sign calls for some interpretive nuance. But it’s a fun video; thanks.