Divisibility!
You might recall, back in school, that you learned some tricks for deciding which numbers could be evenly divided by which other numbers. There are some simple and useful tricks for this, almost all of which are based on two facts:
First, the Distributive Law:
DL: a * (b+c) = (a*b) + (a*c)
One thing that tells us is that if some number (call it x) is divisible by a, and another number y is also divisible by a, than so is x + y, because we know that:
1. There’s some number b for which x = a * b
2. There’s some number c for which y = a * c
So there’s some number d (in fact, it’s b+c) for which x + y = a*d, or, in other words, a evenly divides x + y. As an example, it’s obvious that 13 divides 26 evenly and that 13 divides 130 evenly. Therefore 13 divides 156 evenly, which is a bit less obvious. But it’s a clear case of DL, with a = 13, b = 2, and c = 10.
Extend this a bit. Suppose we add two numbers that aren’t evenly divisible by a third one.
12 = (2*5) + 2
21 = (4*5) + 1
33 = (2*5) + 2 + (4*5) + 1 = (6*5) + 2 + 1 = (6*5) + 3
So when we add the numbers, we can add the remainders as well.
Second, the way we write numbers, knows as positional notation. 423 = 400 + 20 + 3 = (4 * 10 * 10) + (2 * 10) + 3. You knew that, of course, but knowing that we can break numbers up that way has, as we’ll see, a particular importance for divisibility.
So, let’s look at some of the tricks and see how they work.
Let’s start with 2. Take 184 as an example. It’s (1 * 10 * 10) + (8 * 10) + 4. We know that anything multiplied by 10 is divisible by 2, so we on;y need to look at the one’s digit. 4 is divisible by 2, so 184 is as well. Actually, we all know this: any number ending in 0, 2, 4, 6, or 8 is divisible by 2 (AKA even) and any number ending in 0, 2, 4, 6, or 8 is not divisible by 2 (AKA odd).
4 is similar, except that 4 divides 100 evenly but doesn’t divide 10 evenly, so we need to check the ones digit and tens digit, while we can ignore the hundreds digit and beyond. So, if the question arises whether 1,383,058,132 is divisible by 4, just check 32; since 32 is divisible by 4, so is 1,383,058,132 (because 1,383,058,132 = (1,383,058,1*100) + 32, and both of those are divisible by 4). 1,383,058,142, on the other hand, is not.
Likewise 8, though since 8 divides 1000 evenly but neither 10 nor 100, we need to check the last three digits. 1,547,008 is divisible by 8, 1,547,018 is not.
5 is similar to 2 Since it also divides 10, we need to check only the last digit. If it’s a 0 or a 5, yes; otherwise, no.
3 is more interesting. Let’s look at positional notation is a slightly different way:
384 = (3*100) + (8*10) + 4 = (3*99) + (3*1) + (8*9) + (8*1) + 4 = (3*99) + (8*9) + 3 + 8 + 4
Now, 99 and 9 are both divisible by 3. So, by the Distributive Law, 384 is divisible by 3 when the sum of the rest of the terms are, that is, when 3 + 8 + 4 are. Now, there’s nothing special about 384. There’s also nothing special about three-digit numbers. Since the numbers 999, 9999, etc. are all divisible by 3 as well, we can do the same thing for numbers of any size, and we arrive at a general rule:
A number is divisible by 3 precisely when the sum of its digits is divisible by 3.
What about 384 in particular? 3 + 8 + 4 = 15. We can either observe that 15 is divisible by 3, or we can apply our trick again. 1 + 5 = 6, and yes, 6 is divisible by 3.
9 works almost exactly like 3, as you’d expect, since 9, 99, 999, etc. are divisible by 9 as well as 3. 384 is not divisible by 9, since 15 isn’t (nor is 6, of course). As we saw, 384 = (99*3) + (9*8) + 3 + 8 + 4, so we’d expect that it has the same remainder when divided by 9 that 3 + 8 + 4 = 15 has. And it does: 384 = 42*9 + 6, and 15 = 9*1 + 6. On the other hand 123,456,789 is divisible by 9, because 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45, and 4 + 5 = 9.
Since 6 = 2 * 3, a number is divisible by 6 if it’s divisible by both 2 and 3, so we need to apply both tests. For example let’s try 822:
8 + 2 + 2 = 12: Divisible by 3
Ends in 2: Divisible by 2
So 822 is indeed divisible by 6. 866 is not (as you can easily check).
That’s all the one-digit numbers except for 7, which has, as far as I know, no test simpler than just doing the division. There is a test for 11 that’s slightly more complicated than the ones above. Can anyone see what that would be?
IIRC, there is actually one for division by 7, but it’s kinda complicated. Martin Gardner gave it in one of his many collections of his Scientific American articles. I don’t recall all the details, but you can probably derive one that’ll work by noting that if you’ve got a 6-digit number N with digits abcdef, then N mod 7 is equal to
(a*5+b*4+c*6+d*2+e*3+f) mod 7, and if that number is >7, do the same trick with its digits etc. The reason the 5,4,6 numbers etc. are in there is that 5=(10^5 mod 7), 4=(10^4 mod 7), and so on; the sequence of values of the powers of 10 mod 7 turns out to be periodic with period 6.Report
Interesting. Using the same technique, you could check for divisibility by 6 by repeatedly adding the units digit to 4 times the sum of the other digits. For 822, for instance, you get 40 + 2 = 42, 16 + 2 = 18, 4 + 8 = 12, and finally 4 + 2 = 6, thus divisible. For 866, the sequence is 56 + 6 = 62, 24 + 2 = 26, 8 + 6 = 14, and 4 + 4 = 8, thus not divisible.Report
Divisibility by 7 is easy! Just convert to base 8, then apply the same rule as you use for 9.Report
This technique even has lyrics:
It’s new math, new-hew-hew math. So simple, so very simple, that only a child can do it!Report
Likewise, convert to base 2 to check for divisibility by 1.Report
The new trick is (sum of digits in even position) – (sum of digits in odd position) = 0?
I just guessed based on two and three digit multiples of 11, and then worked out the math:
Take the number n represented by the digits abcdef, (that is, n = a * 100000 + b * 10000 + c * 1000 + d * 100 + e * 10 + f)
n = (b * 10000 + d * 100 + f) + (a * 100000 + c * 1000 + e * 10)
n = (b * 9999 + d * 99 + b+ d + f) + (a * 100001 + c * 1001 + e * 11 – a – c – e)
n = (b * 9999 + d * 99) + (a * 100001 + c * 1001 + e * 11) + (b + d + f) – (a + c + e)
99, 9999, and so forth all follow the pattern of 11 * 909…09
1001, 100001, and so forth all follow the pattern of 9090…9091 * 11Report
Very nicely done, and correct with one small change: the sum of the odd digits minus the sum of the even digits might not be zero, but needs to be a multiple of 11. 605, for instance, is 11 * 55.
This is another case of the technique rmtodd mentioned, using the fact that the odd powers of ten (10, 1000, 100,000, …) are one less than a multiple of 11, and the even powers (1, 100, 10,000, …) are one greater.Report
My cat’s breath smells like cat food.Report
Dragonflies?Report
I bent my wookie.Report
My favorite fact from number theory is:
ab=gcf(a,b)*lcm(a,b)Report
That’s pretty clear if you look at it the right way. gcf(a,b) is the product of the prime factors that a and b have in common. lcm(a,b) is the product of
1. the prime factors that a has but b doesn’t, times
2. the prime factors that b has but a doesn’t, times
3. the prime factors that a and b have in common
or lcm(a,b) = a/gcf(a,b) * b/gcf(a,b) * gcf(a,b) = (ab)/gcf(a,b)Report
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.Report
I’ve never seen that before, and it is very cool. Here’s why it works:
First we write 10a + b as a multiplication by 7 plus a remainder between 0 and 6:
10a + b = 7x + r for some x and r.
Subtracting from both sides:
10a + b – 7a = 7x + r – 7a, or
3a + b = 7(x-a) + r
We don’t really care about x-a; the important thing is that the remainders are the same.
Now multiply both sides by 3:
9a + 3b = 21x-21a + 3r = 21x-21a+7r – 4r
and subtract this from the original equation:
a – 2b = 21a-14x-7r + 5r
Again, we don’t care about 21a-14x-7r, except to notice that it’s always divisible by 7. What’s interesting is that the remainder you get when you divide a-2b by 7 is 5r. (Actually, the remainder is a positive number between 0 and 6, so it may be 5r-7n for n between 1 and 4). That is, if the remainder was 0 to begin with, it still is. So if 10a+b is divisible by 7, so is 2a-b.
The only question that’s left is if you can start with a non-zero remainder and end up with zero. The answer is no, because there is no r between 1 and 6 for which 5*r is divisible by 7. So 10a+b is divisible by 7 exactly when 2a-b is too.Report