Proof for the divide-by-three rule and other rules of thumb

Factual Questions
1

In little people school I/we learned that if the sum of a number’s digits are evenly divisible by three, then the number is as well.
This is very cool, and for most people its good enough.
Not for me. I demand proof!
I went digging around the internet, and found squat. So I started in on it, using induction:

  1. Prove it is true for n(1). The first number whose sum is divisible by 3 is 3, which is divisible by 3.

  2. Assume it is true for n. Prove it is true for n+1.
    Let X be a number that is evenly divisible by 3. Assume that sum of the digits of X : k+m+n are also evenly divisible by 3. The next number in the series is X+3, whose digits are one of:

  3. k=k, m=m, n=n+3, for n<7

  4. k=k, m=m+1, n=n-7 for n>=7, m!=9

  5. k=k+1, m=m-9, n=n-7 for n>=7, m=9

If k+m+n is divisible by three, then:

  1. (k+m+n)+3 is divisible by three, since k+m+n is divisible by 3 and 3 is divisible by 3.
  2. k+m+1+n-7 == k+m+n-6 is divisible by three, since k+m+n is divisible by 3 and -6 is divisible by 3.
  3. k+1+m-9+n-7 == k+m+n -15 is divisible by three, since k+m+n is divisible by 3 and -15 is divisible by 3.
  4. For further carryover, we are adding extra -9s, which are divisible by 3, and finally a +1, which makes the -7 a -6, divisible by 3.

QED.

This is great, and I was very proud of myself, but I don’t think it proves what I want it to - I believe I have proved that “if a number is divisible by 3, the sum of its digits is as well” which seems to be a far cry from the converse, what I originally wanted to prove.

Does anyone have an elegant proof for the original statement? Or at least a more elegant proof for the converse, and/or some reasoning why this also means the converse must be true?

Also, I’m interested in proof for the divide-by-two rule (if the one’s digit is evenly divisible by 2, the number is).

Thanks,
Plavacek

2

Ah, the joys of trying to do math notation in ASCII. Allow me to use _ to denote a subscript, and ^ t denote "raising to a power).

Any number can be written as
d_0 + d_1 * 10 + d_2 * 10^2 + … + d_n *10^n
where the d_i are single decimal digits and n is set sufficiently high. Since I can’t type big sigma, let me denote this sum as
sum(i=0, n, d_i * 10^i)

Theorem:
sum(i=0, n, d_i * 10^i) mod 3 = sum(i=0, n, d_i) mod 3

Proof:
sum(i=0, n, d_i * 10^i) =
d_0 + sum(i=1, n, d_i * ((10^i) - 1) + d_i) =
sum(i=1, n, d_i * (10^i - 1)) + sum(i=0, n, d_i)

Therefore
sum(i=0, n, d_i * 10^i) mod 3 =
(sum(i=1, n, d_i * (10^i - 1)) + sum(i=0, n, d_i)) mod 3 =
(sum(i=1, n, d_i * (10^i - 1)) mod 3 + sum(i=0, n, d_i) mod 3) mod 3

Now, 10^i-1 gives us numbers 9, 99, 999, etc, which are all obviously evenly divisble by 3, so

sum(i=1, n, d_i * (10^i - 1)) mod 3 = 0

and therefore

(sum(i=1, n, d_i * (10^i - 1)) mod 3 + sum(i=0, n, d_i) mod 3) mod 3 =
(0 + sum(i=0, n, d_i) mod 3) mod 3 =
(sum(i=0, n, d_i) mod 3) mod 3 =
sum(i=0, n, d_i) mod 3

QED

3

How about proof of the “divide-by-seven” rule? :slight_smile:

Divide by two is simple – all even numbers are by definition divisible by two.

For the record, here are some other rules:

1 – all numbers are divisible by one.
2 – last digit is divisible by two.
3 – sum of the digits are divisible by three
4 – last two digits divisible by four
5 – ends in 5 or 0
6 – the rules for both 2 and 3 apply (even, with sum divisible by 3)
7 – Double ones digit and subtract the reusult from the other digits. If the answer is divisible by 7, the number is. (e.g., 84 = 8 - 8 = 0, divisible by 7). Not very useful, but it does work.
8 – last three digits divisible by eight
9 – sum of digits divisible by nine
10 – last digit is zero
11 – sum of the even digits minus the sum of the odd digits is divisible by 11 (e.g., 121. Even digits sum = 2. Odd digit sum = 2, subtract – zero is divisible by 11. )
12 – the rules for both four and three apply
13 – four times the ones digit plus the other digits is divisible by 13 (e.g., 156 – 6 x 4 = 24 + 15 = 39, divisible by 13) This is even less useful than 7.
14 – the rules for seven and two both apply
15 – the rules for five and three both apply
16 – last four digits divisible by 16

I don’t know 17, I’m afraid.

4

The branch of maths you want is known as number theory, and has a reputation for being useful in cryptography and solving puzzles. A proof might use modular arithmetic, and go something along the lines of

let A be the number, An-1 … A1 A0 be the digits in the number, n is the number of digits, and Ai is the ith digit. In effect you want to prove that A mod 3 = Sum(Ai) mod 3.

A = Sum(Ai*10^i) in the decimal system [1]
It can be shown that:
Sum(anything) mod 3 = Sum(each thing mod 3) mod 3 [2]
10^anything mod 3 = 1 [3]

Start with A mod 3 = Sum(Ai) mod 3
From [1] =Sum(Ai10^i) mod 3 = Sum(Ai) mod 3
From [2] =Sum(Ai10^i mod 3) mod 3 = Sum(Ai) mod 3
From [3] =Sum(Ai mod 3) mod 3 = Sum(Ai) mod 3
From [2] =Sum(Ai mod 3) mod 3 = Sum(Ai mod 3) mod 3

=0, of course, if A is a multiple of 3

This is nowhere near a mathematical proof, and I’m tired, so it’s probably not valid anyway. On preview, ChordedZither has a respose that looks more detailed.

5

First of all, thanks to the three of you for your help and hard proofing, and congrats to ChordedZither on overcoming the limitations of the medium. There was a class on number theory at Pitt, Alescus, and I hid from it like a WMD in Iraq.
Mayhaps not the best idea I’ve had.
Second of all, RealityChuck there’s no such thing as a non-useful shortcut :). In a high-speed requirement computer program with a fast adder and no mul/mod unit (ok, a little far fetched), either of those rules (7 or 13) would be a godsend for quick checks of mod = 0. And one day, someone faced with just such a problem will find this thread, you mark my words. :slight_smile:
I still disagree with the divide-by-two thing though - proof by definition just seems so … wrong.

Plavacek

6

Easy proof of divisibility by 2.

x is a number of any number of digits. z is the last digit of that number.

x = 10y+z
=52y+z

So 10y is always divisible by 2. Therefore x is divisible by 2 if and only if z, its last digit, is divisible by 2.

Lots more information here and nearby pages: Why do the divisibility ‘rules’ work?

The following is implied by the use of the mod function, but it’s worth stating explicitly: The resulting number you get by adding all the digits of a number has the same remainder after dividing by 3 or 9 as the original number.

This also means you can apply those rules recursively until you get down to one digit, the remainder itself. You can also simply ignore or “cast out” 3s or 9s and any digits which add up to those numbers or multiples of those numbers.

Also see the bottom of this page: http://mathforum.org/k12/mathtips/ward3.html

7

I have a rule for 17, but it’s pretty ugly: take the two least-significant digits and subtract them from double the remaining digits. If that number is evenly divisible by 17, then the original number is evenly divisible by 17. You can solve recursively from there.

So: 123454:
2 * 1234 - 54 = 2414
2 * 24 - 14 = 34
34 is evenly divisible by 17, so 123454 is evenly divisible by 17.

The way you can do this is by analyzing powers of the base in question (for our purposes, base 10) with respect to the modulus of the number in question (for this example, 17)

If you don’t know modular math, it basically squishes all integers together, saying that for modulus m, if a = b * m + c, for integers a, b, c, then a is congruent to c modulus m. Congruency is not equality, but I’ll just use the equal sign for simplicity for the rest of the post.

For instance, 1 = -16 mod 17, since 1 = 1 * 17 + (-16). Then:

1 = 1 mod 17, and 1 = -16 mod 17
10 = 10 mod 17, and 10 = -7 mod 17
100 = 15 mod 17, and 100 = -2 mod 17

Now, -2 seems to be an awfully convenient number. Now, for any number n, it can be represented as 100 * i + j, where i & j are integers, and 0 <= j < 100.

So, if n = 0 mod 17, then 100 * i + j = 0 mod 17. And, since 100 = -2 mod 17, then -2 * i + j = 0 mod 17. Multiplying the terms by -1, we get 2 * i - j = -0 mod 17.

So, that means that if n is evenly divisible by 17, then 2 * i - j is evenly divisible by 17.

To take it a little farther, let’s look at 19:

1 = -18 mod 19
10 = -9 mod 19
100 = 5 mod 19 and 100 = -14 mod 19

Now, 100 = 5 mod 19 looks convenient. That means that if n = 100 * i + j, then if n = 0 mod 19, that 100 * i + j = 0 mod 19, so 5 * i + j = 0 mod 19. That means that we can take the two least significant digits and add them to the other digits multiplied by five. If that number is evenly divisible by 19, then the original number is evenly divisible by 19. Again, we can recurse until we can solve trivially.

For example, the number 11096:
110 * 5 + 96 = 646
6 * 5 + 46 = 76

Since 76 is evenly divisible by 19 (76 = 4 * 19) then 11096 is evenly divisible by 19.

8

My favourite test for divisibility by seven: Suppose you have a number with digits ABCDEF. Then if F + 3E + 2D - C - 3B - 2A is divisible by seven, so is the original number. If you have more than six digits, cycle back through these multiplications & additions. The proof is pretty much a direct crib of ChordedZither’s proof, except instead of ending up with the numbers 9, 99, 999, etc., you end up with the numbers 7, 98, 1001, 10003, and 100002, all of which are divisible by seven. (The number 999999 comes into play too if you have a number longer than 6 digits.)

9

Here’s a nice test that works simultaneously for 7, 11, and 13.

Starting with the right-most digits, break the number up into groups of digits of 3 each (with the last group having possibly less than 3 digits). Then, starting with the right-most group, alternately add, then subtract each group. Your new number will have the same remainders as the original number, when divided by 7, 11, and 13.

For example, start with our number:

4758947509549867

break into groups of 3:

4 758 947 509 549 867

combine them:

867 - 549 + 509 - 947 + 758 - 4

= 634.

634 and 4758947509549867 have the same remainders when divided by 7, 11, or 13:

Remainder of 4 when divided by 7, remainder of 7 when divided by 11, and a remainder of 10 when divided by 13.

This works because 71113 = 1001.

10

One of the things I am astonished by is that for some of the more complex rules, esp. 7, that these are at least as hard as just do the division!. I mean, why bother? I can see 2, 5, 10, etc. where you only look at the last digits, but 7, etc. What the hey are people thinking?

11

Aha, brilliant rowrrbazzle, and much simpler than expected. And many thanks for the links.
As for the rest of you…showoffs :smiley:
j/k, by all means continue and thanks

ftg, for some of them, I already demonstrated one possible use: on some computers, division and/or mod are very costly operations (on one architecture in particular, division costs over 10 times as much processor time as addition). If someone didn’t need to perform the addition, just confirm that it would succeed without remainder, some of these rather ridiculous rules would still be faster than performing a mod you don’t need. Noone ever said they were easier or better for people, just easier or better.

Again, my thanks to all participants.

Plavacek

12

Plavacek, I cannot conceive of any situation involving computer math where any of the rules involving looking at all digits would be faster than a division. Division is hardwired in at the word level. The time to do even the divisibility by 3 rule would be ridiculously long in comparison to a division. You’d have to have a loop! *

Nope, these “rules” are merely for humans who go into brain lock when the word “division” is used.

*(And I’m assuming you’re using the base 2 equivalents of these rules. Converting to and from base 10 is another time killer. BTW the test for divisibility by 3 in base 2 looks at 2 bits at a time. So for 32 bits, that a size 16 loop, with shifts and all each time thru. A monstrous waste of time and programmer effort.)

13

ftg, for small numbers you are right that just doing the division would be faster than using the ‘shortcut’. However, if I asked you to determine if 2349872439587239472394872498273591 is divisible by 13, Cabbage’s trick would probably be faster than doing a long division.

Admittedly most people go through life quite happily without ever needing to do that, but it’s still a cute trick…

14

I understood ftg’s post to be referring to computer math only, not human calculations.

15

That was his second post, which was a response to Plavacek’s response to his first post. I understood ftg’s first post to be referring to human calculations.

I agree, by the way, that it’s very difficult to think of a plausible scenario in which one of those tricks (except divisibility by two, which is even more trivial in binary than it is in decimal) would be useful in a computer program, and even less in which it would be worth the effort.

16

RealityChuck’s “rules” for divisibility by 7 and 13 are absurd. Try 132, for example. I guess it works for two digit numbers, maybe.

As for divisibility by 2, it basically comes down to the fact that 2 divides 10 so that a number of the form 10a+b is divisible by 2 if and only if b is.

None of these tests is of any interest to computers since they use base 2, not 10.

17

Unless, of course, he is a she, in which case I apologise.

18

Um… Hari, realitychuck’s tests work fine in the case of 132. Divisibility by 7: 13 - 22 = 9, which isn’t divisible by 7 (and neither is 132.) Divisibility by 13: 13 + 42 = 21, which isn’t divisible by 13 (and neither is 132.)

I’ll admit, though, that his description was a little weird. For 7, if your number to be tested is ABCDEF, then you look for divisibility by 7 in ABCDE - 2F. Similarly, for 13, you look at ABCDE + 4F. This process doesn’t help much if you apply it once to large numbers, but you can apply it repeatedly until you reduce your number to something manageable.

19

Hrm, you’re right about binary complicating things. I’ve most recently done work in Java, which should tell you a bit about my performance requirements :slight_smile:
However, for an admittedly old (Motorolla 68HC11, c.1998) look at just how far some people are/were willing to go to avoid division:
How to optimize dividing by three.

And Plavacek is most certainly male.

20

Well, I understood it to mean 1+3-2*2=0. So he means 13-4. I guess that’s right. How to prove it? So I guess the claim is that 10a + b is divisible by 7 if and only if a - 2b is.

It’s amazing but true. Here is the proof. If x =10a+b and y =a-2b, then x - 3y = 7a + 7b, which is divisible by 7. But then x is divisible by 7 if and only if 3y is, which is to say if and only if y is.