There's a pretty well-known test for divisibility by seven that came up over coffee today. Namely, to check if a number written in base 10 is divisible by 7, remove the last digit; then subtract twice that digit from the "rest" of the number. The input is divisible by 7 if and only if the output is; since this test makes numbers smaller, that's fine.
For example, 4728402 is divisible by 7. Why? Remove the last digit (2) and subtract its double (4) from the "rest" of the number, giving 472840 - 4 = 472836. Repeating, we get:
47283 - 12 = 47271
4727 - 2 = 4725
472 - 10 = 462
46 - 4 = 42
4 - 4 = 0
which is divisible by 7. (The number isn't special in any way; I just pressed a bunch of number keys and multiplied by 7 to create it.)
But I'd never seen a proof that this works. Here's a quick one. We want to show that 10k + m is divisible by 7 if and only if k - 2m is.
Say 10k + m is divisible by 7. Then 3k+m is, so 10k+m - 3(3k+m) = k-2m is.
Conversely, say k-2m is divisibile by 7. Then 3(k-2m) + 7(k+m) = 10k+m is.
A random walk through mathematics -- mostly through the random part.
Blog Archive
-
►
2011
(46)
- December (3)
- November (3)
- October (1)
- September (2)
- August (6)
- July (1)
- June (2)
- May (3)
- April (5)
- March (8)
- February (10)
- January (2)
-
▼
2009
(122)
- December (3)
- October (2)
- September (7)
- August (5)
- July (9)
- June (7)
- May (6)
- April (7)
- March (18)
- February (27)
- January (31)
Contributors
Other blogs
- An American Physics Student in England
- Anarchaia
- Arcadian Functor
- Ars Mathematica
- Brown Sharpie
- Casting Out Nines
- Confessions of a Mathematician
- Data Mining: Text Mining, Visualization and Social Media
- Freakonomics
- Game Theorist
- Good Math, Bad Math
- Gooseania
- Gowers's Weblog
- http://mathnotations.blogspot.com
- Information Aesthetics
- Information Processing
- Junk Charts
- Language Log
- Learning Curves
- Machine Learning (Theory)
- Math Notations
- MathTrek
- Science After Sunclipse
- Scientific Curiosity
- SciTalks
- Secret Blogging Seminar
- Sentient Developments
- Statistical Modeling, Causal Inference, and Social Science
- Statistics Consulting Blog
- Terence Tao's blog
- The Everything Seminar
- The Narrow Road
- The Unapologetic Mathematician
- The Universe of Discourse
- Vlorbik on Math Ed
- WebDiarios de Motocicleta
- Wingie
- Wolfram Blog
- WSJ.com: The Numbers Guy
7 comments:
Wouldn't it be easier to repeatedly replace the top two digits by their value mod 7?
4728402 => (47 mod 7)28402 => 528402
528402 => (52 mod 7)8402 => 38402
38402 => (38 mod 7)402 => 3402
3402 => (34 mod 7)02 => 602
602 => (60 mod 7)2 => 42
42 => (42 mod 7) => 0
It's clearer from this, I think, that there's nothing special about 7. You can make up an alternative left-to-right rule that works more similarlly to the right-to-left one (remove the top digit and add its triple to the next digit) but it's much slower.
But then I also tend to add pairs of multi-digit numbers left-to-right instead of right-to-left so maybe I'm doing this backwards as well.
Since (10mod7)=3, (10^2mod7)=2, and (10^3mod7)=-1,...(10^6mod7)=1...(10^9mod7)=-1... We can check divisibility by 7 by the following:
Is 108425723 divisible by 7?
Well, this number mod 7 could be written as 108425723 = 723 + 425*-1 + 108*1 which is just 2 + -5 + 3 (mod 7) which is 0.
Therefore, I know 5329809714 isn't divisible by 7 since r7(714-809+329-5) = r7(0-4+0-5) = 5.
Subtract 21 times the last digit from the number. Clearly this is divisible by seven. Further, the new final digit is zero, so we can divide by 10. This also leaves divisibility by 7 unchanged.
All you're doing is a slightly slicker way of computing the same result.
David: yes, but that assumes you can reduce things mod 7, which one might argue is a bit harder than my rule.
Anonymous: this requires dealing with some pretty big numbers and arbitrary constants. Could you remember it?
John: well, yeah. But I didn't prove anything new today.
Well, strictly speaking for divisibility by 7, taking the mod7 remainder of a 3 digit number in base 10 isn't too difficult. Not sure what you mean.
one more way to do it is to generalize the famous rule for 3 or 9 in base ten (add the digits) to
1st digit * 1 +
2nd digit * 3 +
3rd digit * 2 -
4th digit * 1 -
5th digit * 3 -
6th digit * 2 +
7th digit * 1 +
8th digit * 3 +
9th digit * 2 -
10th digit * 1
.
.
.
Where I'm counting from the right. This is just because, for example, 10 mod 7 = 3, so multiply the ten's digit by three. I'm also considering, for example 1000 mod 7 = -1, rather than 1000 mod 7 = 6, because it's easier to do the addition problem that way.
You can do this even faster if you take everything mod seven, so for example to test
4728402
you can do
2 + 0 + 1 - 1 - 6 - 0 + 4 = 0
which is a multiple of seven. As you go from digit to digit, you keep a running tally of your current total, which is always somewhere from minus 7 to 7 (because if it goes outside you just take mod 7). You can do an arbitrarily long number in your head easily, as long as you keep track of the
1
3
2
-1
-3
-2
pattern.
It would seem to me, that simply doing long division is faster than using your slick tricks.
Post a Comment