## Sunday, December 11, 2011

### Basic Math - Division Rules

When people find out one is a math major they always seem to expect it means one can do math with incredible ease and knows all kinds of neat tricks. That... isn't quite... true. It's rather far from the truth actually.

But there is a trick that most people find neat, I've never found much practical use for it, but I've seen people, even adults, regard it as if it were magic. You almost certainly know this trick yourself. It's how you tell if a number is divisible by nine. Should, someday, you find yourself in a situation where the fate of the world hinges on knowing whether or not a large number is divisible by nine, you just add up all the digits, and if that's divisible by nine the original number is. Repeat as necessary.

People naturally wonder if there are other such rules. Yes. There are. You already know some of them for example the ones for 2, 5, and 10 are probably ones you use without thinking. Here are 14 such rules, along with explanations for how they work. Guaranteed to bore you.

-

0

Is the number zero?

If a number is divisible by zero then it must be of the form X = 0 * Y for some Y that is a whole number. For any number Y, 0 * Y = 0, so X is only divisible by zero if X = 0.

I have a tendency to forget about super special special cases that aren't intuitive.  Zero is, by definition, a divisor of nothing.  This means that zero is the only number that doesn't divide itself.  It also means that the only number that doesn't divide zero is zero.  Pick any other integer.  It divides zero.  The sole exception is the one number you would most expect to be a divisor of zero.

-

1

Is it a number?

I should probably be more specific since divisibility only applies to integers, but basically if the question, “Is this number divisible by [whatever]?” makes any kind of sense that means the number is definitely divisible by 1.

-

2
Is the last digit divisible by two?

This is because two is a factor of 10, so when you hit the next number divisible by ten it's like you reset the last digit, 0, 2, 4, 6, 8, and then you're back to 0. So anything ending in 0, 2, 4, 6, or 8 is divisible by two, and anything that doesn't end in one of those isn't.

-

3

Add up all the digits, is the result divisible by three?

This is tied up in something called modular arithmetic. It it's a lot like if you took the idea of even and odd and then generalized it. If I were going to ask you if the result you got when you added or multiplied two numbers was even or odd, you wouldn't need to know what the two numbers were, you'd just need to know whether they were even or odd. All you need to know is if the remainder when you divide by two is 0, in which case the number is even, or 1, in which case the number is odd. That's mathematics, modulo two.

In this case we're doing sort of the same thing, but we're looking at the remainder when you divide by three. 10 is 1 modulo 3. (Three goes into ten three times with one left over.) This is what we can do with that knowledge:
I randomly punch a number into my keyboard 1987346543197864.
Is it divisible by 3? I don't know. Let's find out.
The number is actually 198734654319786 * 10 + 4, but since we're doing this modulo 3, that ten can be replaced with a 1, and one times anything is itself, so we can simplify to, 198734654319786 + 4. Repeat and we get: 1+9+8+7+3+4+6+5+4+3+1+9+7+8+6+4 = 85.
Then we can test 85 by repeating. 8+5 = 13. 1+3 = 4. It's not divisible by three, it's off by one. If it had been 1987346543197863, it would have been divisible by three.

The process can actually be simplified a bit more than that. We know that 3, 6, and 9 are all divisible by three, so there's no need to add them up, we can just get rid of them. So if we started with 1987346543197863 we wouldn't need to add up every digit, just the ones that aren't 3, 6, or nine:
1+8+7+4+5+4+1+7+8+3 = 48.
4+8 = 12. 1+2 =3. The number is divisible by 3 just like we thought it would be.

In theory you could make it even simpler, since you never really need to deal with a number larger than two. (4 and 7 are one modulo 3. 5 and 8 are two modulo 3.) But there comes a point where what's theoretically simplifying is actually making things more complicated. While I'm on the subject of making things more complicated, 2 is equal to -1 modulo 3. So really you don't need to even deal with something as big as two.
So 1+9+8+7+3+4+6+5+4+3+1+9+7+8+6+3 = 84 becomes 1+0-1+1+0+1+0-1+1+0+1+0+1-1+0+0 = 3. At which point we're just being silly. Moving on.

-

4

Are the last two digits divisible by four?

Of course, then you've got to wonder, “How do I know if the last two digits are divisible by four?” Here's how: Take the tens digit, multiply it by 2, and subtract the ones digit. Is it divisible by four? (For example, 68. 6*2 – 8 = 12 – 8 = 4, four is divisible by four, so 68 is divisible by four.)

The reason the first test works is because 100 is divisible by four, so every time you reach the next hundred it's like you've reset the last two digits and are starting over.

The reason the second test works is because of twelve. If you get zero when you do that test, then the number is divisible by 12, and everything divisible by 12 is divisible by 4. (Because 12 is divisible by 4.) When you don't get zero you're getting something that's kind of sort of like a remainder but not quite. It's kind of complicated to say exactly what it is. The important thing is that it's a number that, if you add it to the original number you'll get something divisible by twelve:
16 → 1*2 – 6 = 2 – 6 = -4. 16 + – 4 = 12
80 → 8*2 – 0 = 16 – 0 = 16. 80 + 16 = 96. 96 = 12 * 8.
And so on. If you've got a number such that X = A + B, and C divides both A and B, then C divides X. What we're doing with the second rule is breaking down the number we want to test into two parts, something divisible by twelve (in the above examples 12 and 96 respectively) and another number (in the above examples 4 and negative 16, respectively) we know that the thing divisible by twelve is divisible by four, we just have to check if the other number is.

I'm guessing that that makes even less sense now that I've explained it, but just like the rule with nine, the important thing is that it works, as if by magic.

-

5

Is the last digit divisible by five?

Just like two, five divides ten so every time that you get to the next ten it's like the last digit resets. So all you ever have to do is to check the last digit. And since the only one digit numbers divisible by five are zero and five, all you need to do is check to see if the last digit is a zero or a five.

Another way to think about why we only need to think of the final digits when looking at things like two, four, five, and eventually eight, is not that the final digits reset when you get to the thing they divide (10, 100, 10, and 1000 respectively) but that the other digits don't matter. If we take the number 10943856873651387465 that I have just randomly typed into my keyboard (and was actually surprised to see it ended in 5) that's actually 1094385687365138746 * 10 + 5. Anything divisible by ten is divisible by five, so we can throw out the 1094385687365138746 * 10 and just ask if the remaining number, here 5, is divisible by five.
Both ways of looking at it are perfectly legitimate, and the important thing is that you can ignore most of the number.

-

6

Is it divisible by 3 and 2?
That's pretty boring.

There are other things we could do. For example, we could drop the last digit, add together the remaining digits, multiply that by four, and then add the last digit. Sound complicated? It is. Here's how it works: Start with 54660. 5+4+6+6 = 21. 21 * 4 = 84. 84 + 0 = 84. Is that divisible by six? Who knows. Repeat. 8*4= 32. 32 + 4 = 36. And that is divisible by six. (You could repeat again to get 18 and again to get 12, and again to get 6, if you wanted.)

Or, we could do the same thing but multiplying by negative two instead of 4.
Starting, again, with 54660. 5+4+6+6 = 21. 21 * -2 = -42. -42 + 0 = -42. -4 * -2 = 8. 8 + -2 = 6.

Ok, so why do these rules work? For the first thing it's because six is two times three so obviously anything divisible by both must be divisible by six. This works because two and three are relatively prime. Which means that we don't risk tripping up the same way we would if we assumed 18 was divisible by 12 because it can be divided by two and six. Two and three don't have any factors in common, so anything divisible by both of them has to be divisible by six as well.
To be more formal. If X is divisible by A and B, and A and B have no common factors apart from 1, then X is divisible by AB.

As for the second rule, it has to do with the thing that I said was sort of like a remainder above which is actually tied in with almost everything discussed so far. Using the example above:
54660 is 5*10000 + 4*1000 + 6*100 + 6*10 + 0
10 = 6 + 4 so 10 = 4 modulo six. Which is often written: 10 = 4 (mod 6)
100=10*10= 4*4 (mod 6). Now 4*4 = 16 = 12 + 4. And 12 = 0 (mod 6) So 4*4=4 (mod 6).
So every power of ten is 4 (mod 6).
Thus 5*10000 + 4*1000 + 6*100 + 6*10 + 0 becomes 5*4 + 4*4 + 6*4 + 6*4 + 0
And that can be written as (5+4+6+6)*4 + 0. which is what the rule is.

The rule for two does the same thing with zero instead of four, as does the rule for 5, the rule for three uses 1 instead of four.

As for why it works with negative two, it's actually pretty simple. Negative two is four modulo six. Ten is equal to four modulo six because it is four more than six, it is also equal to negative two modulo six because it is two less than twelve.

-

7

Seven has got to be the most annoying of the single digit numbers.
Take the three lowest digits, subtract from them the next three lowest digits, add to them the next three, subtract from the three after that, and so on. Is the result divisible by seven?
What if you only have a three digit number to work with and thus can't do that? Subtract twice the last digit from the rest.
To illustrate:
Starting with: 456897209752172. We get:
456-897+209-752+172 = -812
-81 – 2 * (-2) = -77 (which is clearly divisible by seven, but continuing anyway)
-7 – 2 * (-7) = 7.

Ok, so why does this mess work? Well, it just so happens that 1000 is negative one modulo seven (that is, 1001 is divisible by seven.) So we can break down a very big number like this:
456897209752172 = 456897209752*1000 + 172 which is -456897209752 + 172 (mod 7).
That's just -456897209*1000 – 752 + 172 = 456897209 – 752 + 172 (mod 7), and so on.
Note that if the last thingy doesn't have 3 digits, that's ok. 1204 is -1 +204 (mod 7). The second rule is, I'm told, borrowed from a rule used to check to see if things are divisible by 21. You see 10*-2 = -20 = 1 (mod 21) Which also happens to be 1 (mod 7) because 21 is divisible by seven.
So, from the example above, -812 = -81*10 -2.
We multiply the whole thing by -2 and get -81*(-20) -2*(-2).
-20 is 1(mod 7) so we get rid of it. Confused yet?

-

8

Are the last three digits divisible by 8?
How do we tell if the last three digits are divisible by eight?
Take the ones digit, add it to two times the tens digit and 4 times the hundreds digit. Is that divisible by eight? (For example 512. 5*4+1*2+2= 24. 2*2+4= 8. Yes it is.) Why just the last three digits? See above in the descriptions of 2, 4, and 5. Or, look at 7. 1000 is 0 mod 8, so we do the same thing as we did with seven except we use zero instead of negative one. 456897209752*1000+172 = 456897209752*0 + 172 = 172 (mod 8). Why are we multiplying by 2 and 4? Because 10 = 2 (mod 8) and 100 = 4 (mod 8).
So, continuing, 172= 1*100 + 7*10 + 2 = 1*4 + 7*2 + 2 = 20 (mod 8).
20 = 2*2 + 0 = 4 (mod 8). It isn't divisible by eight.

-

9

This is going to feel like the three rule all over again. Add up all of the digits, are they divisible by 9?
Just like ten is 1 (mod 3) it is also 1 (mod 9). Which is why you get to add up all the digits. I'm not going to repeat the entire three speech.

-

10

Is the last digit divisible by ten? By which I mean, is the last digit zero?

Base ten mathematics is the most experience most people have with addition and multiplication modulo anything, because if you just look at the last digit you'll find you're doing math modulo 10. Anyway, if the last digit is anything other than 0, then there's some remainder when you divide by 10.

-

11

Add the first digit, subtract the second, add the third, subtract the fourth, and so on. Is the result divisible by 11?

Ten is negative one modulo 11. So what we get here is like the sevens rule but using one digit instead of blocks of three. So, starting with 94875204935724957257458439, we get:
-9+4-8+7-5+2-0+4-9+3-5+7-2+4-9+5-7+2-5+7-4+5-8+4-3+9 = -11
That worked out absurdly well considering that I just hit random keys and then adjusted to the nearest multiple of 11.
If you somehow didn't know that negative 11 is divisible by 11, you'd just repeat:
-11 → -(-1) + -1 = 1-1=0. 0 is divisible by everything, including 11, and so it is divisible by 11 and you're done.

-

12

Is it divisible by four and three?
Again, a boring rule, though it is probably more useful than anything else we can come up with.
We could also subtract the last digit from twice what remains when you remove it, as we did with 4.
72 → 2*7 -2 = 12.
156 → 2*15 – 6 = 30 – 6 = 24. If that's not good enough: 2*2 – 4 = 0. We're done.

What if there are a lot of digits and we want to make the number we have to multiply smaller. Well, you're in luck (sort of) there is something else we can do.
Take all the digits except the last two. Add them together. Multiply them by four. Subtract twice the tens digit, add the ones digit.
458760249588 → (4+5+8+7+6+0+2+4+9+5)*4 – 8*2 + 8 = 192
192 → 1*4 – 9*2 + 2 = -12
And we know it's divisible by 12.

As for why it works, more of the same. 10 = -2 mod 12. So 156 = 15*(-2) + 6= -30 + 6 = -24 (mod 12). But if -X is divisible by 12 then so is X, and for whatever reason 15*2 – 6 just looks nicer than 15*(-2) + 6.
For the other thing we just see what each power of ten is, modulo twelve. 10, we've already said, is -2. To find the next power we just multiply by -2 again. -2 * -2 = 4. Then something interesting happens. 4 * -2 = -8, and -8 = 4 (mod 12). Which means that for every power of ten after the first, what we have is 4 modulo 12. That's why we can just add up everything in the digits other than the first two and multiply the sum by four. Or, if we wanted to, we could multiply each by four individually. Either way works.

-

13

Remember the addition and subtraction thing with blocks of three numbers each you did up at 7? That's back.
After that you get to add 4 times the ones digit to the other digits.

-2+267-142+305-814+737=351
35 + 1*4 = 39 and that's divisible by 13.
Unfortunately if you don't know that it kind of gets stuck in a rut there because 3+9*4=39, and you'll just go around in a loop. Not completely sure what to do about that. You could, I suppose, add the ones digit to negative three times the rest. That will work.
3*(-3) + 9 = 0. 0 is divisible by 13. You're done.

So, why does it work? The first thing works for the same reason it worked for seven. 13 divides 1001. (So too does 11, but we don't have to resort to that there.)
The second thing works because 13 divides 39, which means 40 = 1 (mod 13). I didn't mention this last time this came up (in the test for 7) but the reason this works is that the number we're multiplying by isn't a factor of the number we're testing for. Not a problem because in both cases (7 and 13) the number we're testing for is a prime number. There's no way the result of multiplying by four could be divisible by 13 if the original number wasn't.
Anyway, we start with 351, which is 35*10 + 1. We multiply the whole thing by four:
35*40 + 1*4, we know that 40 = 1 mod (13) so that is 35 + 1*4 (mod 13).
The third thing works because 10 = -3 (mod 13). Hopefully I've explained that one enough that I don't have to do it again.

-

And those are some division rules.

1. x^2 = (x+c)(x-c) + c^2 (because x^2 = x^2 + xc - xc - c^2 + c^2).

This is useful for squaring numbers in your head, where x is the number you want to square and c is a number you pick (any number will work) to make the math easy.

So, let's square 82. a good number to pick for c is "2" or "8" or "18" (if you have 18 squared memorised, otherwise it's a poor choice).

82^2 = (82+2)*(82-2) + 2^2 (this step is just for completion, in my head i usually skip to the next step)
82^2 = 84*80 + 4
8*8 = 64, 8*4 = 32. therefore. 84*80 = 6400+ 320 = 6720. add 2^2 and you get 82^2 = 6724.

the reason I said 18 was a good number to pick:

82^2 = (82+18)(82-18) + 18^2
100*64 = 6400. 18^2 = 324. 6400 + 324 = 6724.

Once you get the hang of that, try 3 digit numbers. You can do them in multiple steps:

321^2 = 300*342 + 21^2
300*342 = 102600 there will probably be a carry, so start saying "one hundred three thousand" out loud while you work out the rest. it'll make it look like you solved it faster. hang on to the 600 on your fingers if you have to. if you didn't know there would be a carry, just start saying "one hundred" and hold on to 2600 on your fingers.

meanwhile. 21^2 = 20*22 + 1 = 441. now finish giving the answer "forty one". 321^2 = 103041.

--P

2. Oh wow! A rule for 13? My 13yo learned the sevens rule in his number theory class this summer, but they didn't do the rule for 13.

I was really excited to learn the rule for 7 this summer, because *my* high school Advanced Math teacher said, "There's a rule for seven, but it's much more complicated than just doing long division," and wouldn't tell us what it was.

3. You consider 0 to be divisible by 0? You might want to review your indeterminate forms.

4. Indeterminate forms aren't usually treated as definitive for number theory.

0^0 = 1 in number theory by convention, even though it's an indeterminate form when encountered as a limit.

On the other hand, I'm pretty sure the standard convention in number theory is that n|0 for all n *except* n=0

5. You're right, it's been years since I've been in a math class and I forgot the exception.

Pulling out a number theory book, I see that zero is explicitly excluded. a (not equal to zero) divides b if b=ac, a, b, and c all integers.

I don't like that definition for a few reasons. Mostly it just seems inelegant. There's also the fact that intuitively it doesn't make a lot of sense to me to say, "a divides b because because there exists and integer c, which does not remotely divide b, such that ac = b." If c can't divide b then what the hell is it doing in the equation?

I don't think that zero being indeterminate really makes a difference. If we say that zero divides zero that still doesn't help us determine the the result. 0=0*c where c is an integer, yes, but there are an infinite number of things c can be, so it's still indeterminate.

Which brings me to how I would define divisibility if I really thought that it was for some reason important to exclude zero (and obviously someone did.)

I'd say, the b integer b is divisible by an integer a iif there exists a unique integer c, such that b=ac. Pretty sure that gets you the same exact results, but it doesn't leave you saying, "Zero obviously satisfies this rule, why'd we make an exception?"

Infinity isn't an integer, so I think the only time this would come up is when a and b are both zero.

It has been a while though.

6. It's fun when you change number bases: some of the rules stayed kindasorta the same, and others you can forget. (I was a CS major with some boring classes. And I got 'New Math' when I was younger: base 7 and base 12 are both familiar.)

7. And these are infinitely important rules to know, so that when you are driving in your car and trying to find the prime factors for the number on you 100K+ odometer, you can figure out in advance whether a given number is worth attempting as a factor.

Yes, this is how I pass the time on long trips. For convenience, I never bother starting with a number which cannot be divided by 6 and I rarely start with a number that cannot be divided by 36. The fun part is trying to finish the factoring before the number changes again. (Okay, I did factor out 111,111 despite being obviously divisible only by 3 with the tricks I knew. I was pleasantly surprised to find it factored neatly within my mental math capacity.)