03 February 2009

Divisibility by 7

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.


Anonymous said...

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.

Anonymous said...

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.

Anonymous said...

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.

Michael Lugo said...

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.

Anonymous said...

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.

Markkimarkkonnen said...

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


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



Unknown said...

It would seem to me, that simply doing long division is faster than using your slick tricks.

Anonymous said...

Do You interesting of [b]Viagra 100mg dosage[/b]? You can find below...
[size=10]>>>[url=http://listita.info/go.php?sid=1][b]Viagra 100mg dosage[/b][/url]<<<[/size]

[b]Bonus Policy[/b]
Order 3 or more products and get free Regular Airmail shipping!
Free Regular Airmail shipping for orders starting with $200.00!

Free insurance (guaranteed reshipment if delivery failed) for orders starting with $300.00!

Generic Viagra (sildenafil citrate; brand names include: Aphrodil / Edegra / Erasmo / Penegra / Revatio / Supra / Zwagra) is an effective treatment for erectile dysfunction regardless of the cause or duration of the problem or the age of the patient.
Sildenafil Citrate is the active ingredient used to treat erectile dysfunction (impotence) in men. It can help men who have erectile dysfunction get and sustain an erection when they are sexually excited.
Generic Viagra is manufactured in accordance with World Health Organization standards and guidelines (WHO-GMP). Also you can find on our sites.
Generic Viagra is made with thorough reverse engineering for the sildenafil citrate molecule - a totally different process of making sildenafil and its reaction. That is why it takes effect in 15 minutes compared to other drugs which take 30-40 minutes to take effect.
Even in the most sexually liberated and self-satisfied of nations, many people still yearn to burn more, to feel ready for bedding no matter what the clock says and to desire their partner of 23 years as much as they did when their love was brand new.
The market is saturated with books on how to revive a flagging libido or spice up monotonous sex, and sex therapists say “lack of desire” is one of the most common complaints they hear from patients, particularly women.