In article <>, Chris Croughton <> writes:
> > Keith Thompson wrote:
> >>
> >> Sure, but there's a trick for multiples of 7 as well. Take the last
> >> digit, double it, and subtract from what's left. Iterate as needed.
> >> If the final result is 0 or 7, it's a multiple of 7; if not, not.
>
> That's what puzzles me. It does work, it seems, but I don't understand
> it...
Let's see. It's easy to prove it works for the case where N/10 is
a multiple of 7, just by considering three cases: the one's digit is
0, 2*0 is 0, and you're left with N/10; the one's digit is 7, you
subtract a multiple of 7 from another multiple of 7, and their
difference must then also be a multiple of 7; or anything else (you
subtract a non-multiple of 7 from a multiple of 7, their difference
cannot be a multiple of 7).
The cases where N/10 is not a multiple of 7 are a bit trickier, but
not that much.
Consider the two-digit case:
N has digits a and b, so N == 10*a + b.
Hypothesis: 10*a + b == 0 (mod 7) iff a - 2*b == 0 (mod 7). (Note
that the case where you're left with 7 as the sole remaining digit is
just the other case, in base 10, of 0 mod 7 as a single digit.)
Now, this is the same as saying that a mod 7 == 2*b mod 7, so that
when we subtract 2*b from a, we cancel out the noncongruency to 0 (I
think - I am most definitely not a mathematician). In other words,
if a is, say, 3 "away" from a multiple of 7, then 2*b also must be 3
"away" from a multiple of 7.
Now think about a mod 7. This is the penultimate remainder you'd
have if you were dividing 7 into a number using long division. To
have a 0 remainder for the whole division process, ten times that
penultimate remainder (ie 10*(a mod 7)) plus the final digit (b) must
be a multiple of 7. If a mod 7 == 2, then b must be 1 or 8, for
example.
Equivalently, whatever 10*a is congruent to mod 7, b must be
congruent to 7 minus that value. If 10*a == 0 (mod 7), b must also
== 0 (mod 7); if 10*a == 1, b == 6, and so forth.
Make a table comparing a mod 7 with 10a mod 7. If 10a mod 7 is 1, a
mod 7 will be 3 (eg 10 mod 7 == 3, 80 mod 7 == 3, etc). So we want
the mapping between b mod 7 (must equal 10a mod 7) to 2b mod 7 (must
equal a mod 7) to be the converse of that between 10a and a. If
going from 10a to a gives us 1, going from b to 2b must give us 6,
and so forth:
And it is. If 10a is 1, a is 5; if b is 1, 2b is 2. 5 + 2 == 0.
And so on, for 0 through 6. You can write out the tables (of
congruencies mod 7):
10a | a b | 2b a + 2b
-------- ------- ------
0 | 0 0 | 0 0+0=0
1 | 5 1 | 2 5+2=0
2 | 3 2 | 4 3+4=0
3 | 1 3 | 6 1+6=0
4 | 6 4 | 1 6+1=0
5 | 4 5 | 3 4+3=0
6 | 2 6 | 5 2+5=0
(What's the term for the relationship between a and 2b in this case?
I can't remember.)
And I think that's why it works.
--
Michael Wojcik
_
| 1
| _______ d(cabin) = log cabin + c = houseboat
| (cabin)
_| -- Thomas Pynchon
Similar Threads
