5 ms·

Here's another human-friendly scheme to test divisibility by 7 that I don't think is popularly known: Write down the number, then cross off the least significan

by drfuchs 11y ago

Here's another human-friendly scheme to test divisibility by 7 that I don't think is popularly known: Write down the number, then cross off the least significant digit, double it, and subtract that from what's left of the number. Repeat until you get zero or an obviously divisible-by-7 number, or not. Example: 325 becomes 32 - 10 = 22, which is obviously not divisibile by 7. Better example: 8638 -> 863 - 16 = 847 -> 84 - 14 = 70 -> 7 - 0 -> 7, so we have a winner. Learned this as a kid (forget where), but it took decades for me to realize why it obviously works.

colinodell 11y ago
So why does this work?
- hcarvalhoalves 11y ago
  50 years from now this will be called "drfuchs last theorem"
  - newsignup 11y ago
    with the scribble "but it took decades for me to realize why it obviously works" somewhere in the margins and stating that there wasn't enough room to write that down though..
- pervycreeper 11y ago
  21=3*7 you are subtracting multiples of 21, then dividing by 10, which is coprime with 7
  - orbitur 11y ago
    The examples subtracted 10, 16, etc... Those aren't multiples of 21.
    - chadzawistowski 11y ago
      Since you scratched off the last digit, 10 is really 100, plus 5 for the digit you scratched off = 105. 105 is a multiple of 21.
    - deleted 11y ago
      [deleted]
- deleted 11y ago
  [deleted]
- mmastrac 11y ago
  You are subtracting enough 21s (ie: X * 21) to make the last digit zero. Since 21 is obviously a factor of 7, subtracting those should yield a factor of 7. You can then divide by zero because if X is a factor of 7 and ends in zero, X / 10 is a factor of 7 as well.
- Jtsummers 11y ago
  ...There was another answer here that seemed close. I'm not sure the best way to express it, but here's what I've got: Allow me to use a shorthand, N = AB where AB is shorthand for 10 * A + B, and B is the least significant digit. IF N is divisible by 7, then AB = 0 (mod 7). This allows us to do the following manipulations: AB = 0 (mod 7) 10*A + B = 0 (mod 7) 3*A + B = 0 (mod 7) 5*(3*A + B) = 5*0 (mod 7) // EDIT: had -2 on the RHS, that was correct but confusing A + 5*B = 0 (mod 7) A - 2*B = 0 (mod 7) So we've arrived at drfuchs' method. You only need to repeat the process until you've proven to yourself that A - 2 * B is divisible by 7 or not. That's all I've got. I ran a half-marathon yesterday, and I've been up for 16 hours today. My brain might work better tomorrow. EDIT: changed the steps a bit, had some unneeded ones. Also, this shows that you can use addition instead of subtraction, but you won't be moving towards 0, but you still have to be able to recognize that the new number is divisible by 7.
  - jacobenget 11y ago
    Thanks for this explanation! I was about to post something similar after working the math out, but I'm sure my answer would have been twice as long and less clear.
madcaptenor 11y ago
There's a similar test for divisiblity by 13: cross off the least significant digit, quadruple, and add to what's left. Example: 325 becomes 32 + 20 = 52 which is divisible by 13. Example: 8632 -> 863 + 8 = 871 -> 87 + 4 = 91 which is divisible by 13. It works because 39 = 40-1 is divisible by 13 (similarly to why the 7 test works because 21 = 20+1 is divisible by 7).
- Jtsummers 11y ago
  An equivalent test would be to use a factor of -9 instead of 4. 325 => 32 - 9 * 5 = 32 - 45 = -13 The method itself comes from the fact that what we're doing is really just modular arithmetic. Which has the wonderful property that, as long as all manipulations mod N don't fundamentally change the base we can keep repeating them. Similar to my mod 7 breakdown: AB = 0 (mod 13) 10*A + B = 0 (mod 13) 40*A + 4*B = 0 (mod 13) A + 4*B = 0 (mod 13) A - 9*B = 0 (mod 13) // because 4 = -9 (mod 13) This is neat. A similar construction should be doable for any number. EDIT: I have a rule of not questioning down votes, but many of my comments that get down voted have something disagreeable in them (well, I agree with them, but it's typically political/management style/economics/etc.). But how does a break down of modular arithmetic become worth down voting?
  - nkurz 11y ago
    Oops. That makes more sense now that you point it out. I thought they were just little scrolling arrows, and never understood why they didn't work right. Sorry about that. (While it's a good general practice not to question downvotes, there are some cases that just leave you wondering what the other person was thinking. This is one of the explanations I've imagined, although usually I just assume big fingers on a tiny touchscreen.)
  - madcaptenor 11y ago
    Doing it with -9 instead of +4 will terminate faster. But on the other hand one has to think about negative numbers. It's an interesting tradeoff. "A similar construction should be doable for any number." - yes, except 2 and 5. You just need to find a multiple of the number that's 1 more or less than a multiple of 10. In fact, we can even come up with a test for divisibility by 3 (or 9) this way: just add the last digit to the rest of the number repeatedly until you can tell if the result is divisible by 3 (or 9): 4752 -> 475+2 = 477 -> 47+7 = 54 -> 5+4 = 9 is divisible by 3 and 9 3752 -> 375+2 = 377 -> 37+7 = 44 -> 4+4 = 8 isn't divisible by 3 or 9 4755 -> 475+5 = 480 -> 48+0 = 48 -> 4+8 = 12 -> 1+2 = 3 is divisible by 3 but not 9. Of course this ends up being equivalent to the usual "add all the digits" test.
piAcceptor 11y ago
Well.. Why does it, then?!

by drfuchs 11y ago

colinodell 11y ago

So why does this work?

hcarvalhoalves 11y ago
50 years from now this will be called "drfuchs last theorem"
- newsignup 11y ago
  with the scribble "but it took decades for me to realize why it obviously works" somewhere in the margins and stating that there wasn't enough room to write that down though..
pervycreeper 11y ago
21=3*7 you are subtracting multiples of 21, then dividing by 10, which is coprime with 7
- orbitur 11y ago
  The examples subtracted 10, 16, etc... Those aren't multiples of 21.
  - chadzawistowski 11y ago
    Since you scratched off the last digit, 10 is really 100, plus 5 for the digit you scratched off = 105. 105 is a multiple of 21.
  - deleted 11y ago
    [deleted]
deleted 11y ago
[deleted]
mmastrac 11y ago
You are subtracting enough 21s (ie: X * 21) to make the last digit zero. Since 21 is obviously a factor of 7, subtracting those should yield a factor of 7. You can then divide by zero because if X is a factor of 7 and ends in zero, X / 10 is a factor of 7 as well.
Jtsummers 11y ago
...There was another answer here that seemed close. I'm not sure the best way to express it, but here's what I've got: Allow me to use a shorthand, N = AB where AB is shorthand for 10 * A + B, and B is the least significant digit. IF N is divisible by 7, then AB = 0 (mod 7). This allows us to do the following manipulations: AB = 0 (mod 7) 10*A + B = 0 (mod 7) 3*A + B = 0 (mod 7) 5*(3*A + B) = 5*0 (mod 7) // EDIT: had -2 on the RHS, that was correct but confusing A + 5*B = 0 (mod 7) A - 2*B = 0 (mod 7) So we've arrived at drfuchs' method. You only need to repeat the process until you've proven to yourself that A - 2 * B is divisible by 7 or not. That's all I've got. I ran a half-marathon yesterday, and I've been up for 16 hours today. My brain might work better tomorrow. EDIT: changed the steps a bit, had some unneeded ones. Also, this shows that you can use addition instead of subtraction, but you won't be moving towards 0, but you still have to be able to recognize that the new number is divisible by 7.
- jacobenget 11y ago
  Thanks for this explanation! I was about to post something similar after working the math out, but I'm sure my answer would have been twice as long and less clear.

madcaptenor 11y ago

There's a similar test for divisiblity by 13: cross off the least significant digit, quadruple, and add to what's left. Example: 325 becomes 32 + 20 = 52 which is divisible by 13. Example: 8632 -> 863 + 8 = 871 -> 87 + 4 = 91 which is divisible by 13. It works because 39 = 40-1 is divisible by 13 (similarly to why the 7 test works because 21 = 20+1 is divisible by 7).

Jtsummers 11y ago
An equivalent test would be to use a factor of -9 instead of 4. 325 => 32 - 9 * 5 = 32 - 45 = -13 The method itself comes from the fact that what we're doing is really just modular arithmetic. Which has the wonderful property that, as long as all manipulations mod N don't fundamentally change the base we can keep repeating them. Similar to my mod 7 breakdown: AB = 0 (mod 13) 10*A + B = 0 (mod 13) 40*A + 4*B = 0 (mod 13) A + 4*B = 0 (mod 13) A - 9*B = 0 (mod 13) // because 4 = -9 (mod 13) This is neat. A similar construction should be doable for any number. EDIT: I have a rule of not questioning down votes, but many of my comments that get down voted have something disagreeable in them (well, I agree with them, but it's typically political/management style/economics/etc.). But how does a break down of modular arithmetic become worth down voting?
- nkurz 11y ago
  Oops. That makes more sense now that you point it out. I thought they were just little scrolling arrows, and never understood why they didn't work right. Sorry about that. (While it's a good general practice not to question downvotes, there are some cases that just leave you wondering what the other person was thinking. This is one of the explanations I've imagined, although usually I just assume big fingers on a tiny touchscreen.)
- madcaptenor 11y ago
  Doing it with -9 instead of +4 will terminate faster. But on the other hand one has to think about negative numbers. It's an interesting tradeoff. "A similar construction should be doable for any number." - yes, except 2 and 5. You just need to find a multiple of the number that's 1 more or less than a multiple of 10. In fact, we can even come up with a test for divisibility by 3 (or 9) this way: just add the last digit to the rest of the number repeatedly until you can tell if the result is divisible by 3 (or 9): 4752 -> 475+2 = 477 -> 47+7 = 54 -> 5+4 = 9 is divisible by 3 and 9 3752 -> 375+2 = 377 -> 37+7 = 44 -> 4+4 = 8 isn't divisible by 3 or 9 4755 -> 475+5 = 480 -> 48+0 = 48 -> 4+8 = 12 -> 1+2 = 3 is divisible by 3 but not 9. Of course this ends up being equivalent to the usual "add all the digits" test.

piAcceptor 11y ago

Well.. Why does it, then?!