# Divisibility by Seven
**URL:** https://boards.straightdope.com/t/divisibility-by-seven/568568
**Category:** Factual Questions
**Created:** [January 22, 2011, 3:42pm UTC](https://boards.straightdope.com/t/divisibility-by-seven/568568 "2011-01-22T15:42:54Z")
**Posts on this page:** 20
**Page:** 1
### Author:  [@pdunderhill](https://boards.straightdope.com/u/pdunderhill)
#### Post date: [January 22, 2011, 3:42pm UTC](https://boards.straightdope.com/t/divisibility-by-seven/568568/1 "2011-01-22T15:42:54Z")
A quickie, I hope!.
I’m hopping that one of you has a way to assertiain if a whole positive integer is divisible by 7.
1!, 2,3,4,5,10,11 are fairly easy, for instance 11 look at the number and split it up into it’s odd and even numbered components and compare. If they’re identical or the difference is divisible by 11 you’re on a winner.
To parahrase myself can I look at a number and analyse it’s structure without long division and tell if it’s a multiple of seven?
Good people your help is, as always, invaluable.
Peter Underhill
---
### Author:  [@Asympotically\_fat](https://boards.straightdope.com/u/Asympotically_fat)
#### Post date: [January 22, 2011, 3:45pm UTC](https://boards.straightdope.com/t/divisibility-by-seven/568568/2 "2011-01-22T15:45:50Z")
> [@pdunderhill](#):
>
> A quickie, I hope!.
> I’m hopping that one of you has a way to assertiain if a whole positive integer is divisible by 7.
> 1!, 2,3,4,5,10,11 are fairly easy, for instance 11 look at the number and split it up into it’s odd and even numbered components and compare. If they’re identical or the difference is divisible by 11 you’re on a winner.
> To parahrase myself can I look at a number and analyse it’s structure without long division and tell if it’s amultiple of seven?
> Good people your help is, as always, invaluable.
> Peter Underhill
Google divisibilty test:
> **[Divisibility rule | Divisibility by 7](https://en.wikipedia.org/wiki/Divisibility_rule#Divisibility_by_7)**
>
> Divisibility by 7 can be tested by a recursive method. A number of the form 10x + y is divisible by 7 if and only if x − 2y is divisible by 7. In other words, subtract twice the last digit from the number formed by the remaining digits. Continue to do this until a number is obtained for which it is known whether it is divisible by 7. The original number is divisible by 7 if and only if the number obtained using this procedure is divisible by 7. For example, the number 371: 37 − (2×1) = 37 − 2...
---
### Author:  [@Czarcasm](https://boards.straightdope.com/u/Czarcasm)
#### Post date: [January 22, 2011, 4:09pm UTC](https://boards.straightdope.com/t/divisibility-by-seven/568568/3 "2011-01-22T16:09:35Z")
Moving thread from Great Debates to General Questions.
---
### Author:  [@glowacks](https://boards.straightdope.com/u/glowacks)
#### Post date: [January 22, 2011, 10:39pm UTC](https://boards.straightdope.com/t/divisibility-by-seven/568568/4 "2011-01-22T22:39:11Z")
Basically, there is no easy way to determine divisibility by 7 like there is for other small numbers. Usually just dividing by 7 will get you an answer just as fast as any other method. If you really don’t like dividing though, you can use the following:
For numbers of 3 digits or less, you can subtract twice the unit digit from the other two digits: 392 is divisible by 7 since 39 - 2_2 = 35 is. If you don’t even like subtraction, you can add 5 times the unit digit to the other two: 392 -\> 39 + 2_5 = 49, a multiple of 7. These work due to 21 and 49 being multiples of 7.
For 4-6 digit numbers, use the fact 1001 is divisible by 7: write in the thousands separator and subtract the two numbers it separates; the result will be divisible by 7 whenever the original is. For even larger numbers, use the fact that 999,999 is divisible by seven (as the previous test will verify): add blocks of 6 digits together. Combining this with the previous test, you use an alternating sum of blocks of 3 digits. That is, 4,895,879,234,895,897,345,892 is divisible by 7 if 892 - 345 + 897 - 895 + 234 - 879 + 895 - 4 is.
Personally, I find it easier to do long division, which is effectively the same thing as subtracting numbers that are obvious multiples of 7 that are close in size. That requires having a good working knowledge of the multiplication/division table, so the above method using mainly addition and subtraction might be faster for some.
---
### Author:  [@RadicalPi](https://boards.straightdope.com/u/RadicalPi)
#### Post date: [January 22, 2011, 11:11pm UTC](https://boards.straightdope.com/t/divisibility-by-seven/568568/5 "2011-01-22T23:11:15Z")
As a sort of highjack question (since the OP’s OP has been answered), why are divisibility tests for 7 so much more convoluted than all the others at least up to 13?
**1** : Easy, since given by definition.
**2**. Easy, since a component of base 10, which means repeatibility.
**5**. Easy, same as 2.
**10**. Easy, the actual base, otherwise same as 2 or 5.
But what of **4** and **8**? I guess we could reconsider numbers in base 100 or 1,000 here, thus getting a repeatible pattern. And I guess that’s what actually is happening. Is this right?
**3** and **9**? It seems to be just a fluke, really, that the add-them-up method works. Is there something else? They’re both powers of 3, but I don’t know how that might matter.
**11** is like 3 and 9, but alternating addition and subtraction. Is that a fluke, too? 11 is not a power of 3, so I got nothing here. (3 is one more than 2, and 11 is one more than 10, so that might be important. Is there an add-them-up method for 6, then?)
**6** and **12** are combos (of 3 and 2 for 6 and 3 and 4 for 12), which makes sense for the same reason that a convoluted way to tell if a number is divisible by 10 is to check to see if it’s divisible by 5 and 2).
Then **13** is hard again. . . .
---
### Author:  [@Skald\_the\_Rhymer](https://boards.straightdope.com/u/Skald_the_Rhymer)
#### Post date: [January 22, 2011, 11:30pm UTC](https://boards.straightdope.com/t/divisibility-by-seven/568568/6 "2011-01-22T23:30:16Z")
> [@RadicalPi](#):
>
> As a sort of highjack question (since the OP’s OP has been answered), why are divisibility tests for 7 so much more convoluted than all the others at least up to 13?
>
> **1** : Easy, since given by definition.
> **2**. Easy, since a component of base 10, which means repeatibility.
> **5**. Easy, same as 2.
> **10**. Easy, the actual base, otherwise same as 2 or 5.
>
> But what of **4** and **8**? I guess we could reconsider numbers in base 100 or 1,000 here, thus getting a repeatible pattern. And I guess that’s what actually is happening. Is this right?
To determine whether a number with three-plus-digits is divisible by four, check the last two digits. If they are divisible by four, the entire number is.
To determine whether a number with 3-plus digits is divisible by four, check the last three digits. If the last two are divisible by 8, and the other is even, the entire number is a multiple of 8. If the last two are divisible by four but not by eight, and the other is odd, then the whole number is a multiple of eight.
Both these methods only require memorizing the twenty-five multiples of four from 0 to 96.
The adding-up method for 3 & 9 is called digit sums. (Well, Isaac Asimov called it that.) A shortcut in doing that, for divisibility by 3, is to discard all 3s, 6s, & 9s in the number you are testing. For 6 check for evenness (obviously trivial) and then use the digit-sum method for 3. For 9 use the digit sum method but discard all 9s.
---
### Author:  [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)
#### Post date: [January 23, 2011, 12:26am UTC](https://boards.straightdope.com/t/divisibility-by-seven/568568/7 "2011-01-23T00:26:16Z")
> [@RadicalPi](#):
>
> As a sort of highjack question (since the OP’s OP has been answered), why are divisibility tests for 7 so much more convoluted than all the others at least up to 13?
In base n, there’s going to be a simple divisibility test for any k that divides either n or n - 1, and for k = ab where a divides n and b divides n - 1. Two and five divide ten, three and nine divide nine, four and eight are powers of two, and six is the product of two and three.
---
### Author:  [@Lance\_Turbo](https://boards.straightdope.com/u/Lance_Turbo)
#### Post date: [January 23, 2011, 12:51am UTC](https://boards.straightdope.com/t/divisibility-by-seven/568568/8 "2011-01-23T00:51:18Z")
Also in base n there will always be an alternating digit sum test for n+1 since n is congruent to -1 mod n+1 and n^2 is congruent to 1 mod n+1. ( n^2 = (n+1)(n-1) + 1 )
---
### Author:  [@RadicalPi](https://boards.straightdope.com/u/RadicalPi)
#### Post date: [January 27, 2011, 7:11am UTC](https://boards.straightdope.com/t/divisibility-by-seven/568568/9 "2011-01-27T07:11:51Z")
> [@Skald\_the\_Rhymer](#):
>
> To determine whether a number with 3-plus digits is divisible by four, check the last three digits. If the last two are divisible by 8, and the other is even, the entire number is a multiple of 8. If the last two are divisible by four but not by eight, and the other is odd, then the whole number is a multiple of eight.
>
> Both these methods only require memorizing the twenty-five multiples of four from 0 to 96.
I think that this is pretty much what I meant by thinking in terms of base 100. Divide the number up into groups of two, where each pair is considered a “digit.” Now that I think about it, the same trick you mention for 8 could work with 4, too. Basically, double the ten’s digit and add it to the one’s digit. If that’s divisible by 4, so is the whole thing. I think. So, for 8, that would be quadruple the hundred’s digit added to double the ten’s digit added to the one’s digit. Again, I think.
> [@Lance\_Turbo](#):
>
> Also in base n there will always be an alternating digit sum test for n+1 since n is congruent to -1 mod n+1 and n^2 is congruent to 1 mod n+1. ( n^2 = (n+1)(n-1) + 1 )
Ah. This is also why the 9’s and 3’s work out as they do, except without the alternating, isn’t it?
100_a_ + 10_b_ + _c_ ≡ (11∙9 + 1)_a_ + (9 + 1)_b_ + _c_ ≡ _a_ + _b_ + _c_ (mod 9).
(This works with 3, too, since everything that is 0 (mod 9) must also be 0 (mod 3).) Also, I’m sure it’ll work with more than 3 digits.
Incidentally, why do you determine _n_[SUP]2[/SUP] by (_n_ + 1)(_n_ − 1) + 1? I would think that if _n_ ≡ − 1, that _n_[SUP]2[/SUP] ≡ _n_∙_n_ ≡ (− 1)(− 1) ≡ 1 (mod _n_ + 1). Is there some nuance I’m missing?
---
### Author:  [@Hari\_Seldon](https://boards.straightdope.com/u/Hari_Seldon)
#### Post date: [January 27, 2011, 1:41pm UTC](https://boards.straightdope.com/t/divisibility-by-seven/568568/10 "2011-01-27T13:41:51Z")
Thus in octal there is a trivial test (sum of the digits) for divisibility by 7.
---
### Author:  [@Giles](https://boards.straightdope.com/u/Giles)
#### Post date: [January 27, 2011, 1:47pm UTC](https://boards.straightdope.com/t/divisibility-by-seven/568568/11 "2011-01-27T13:47:50Z")
> [@Hari\_Seldon](#):
>
> Thus in octal there is a trivial test (sum of the digits) for divisibility by 7.
And in hexadecimal there is an easy test for divisibility by 3 and 5 (since 3 times 5 = 15), and an easy one for 17. However, 7, 11 and 13 are harder.
---
### Author:  [@Hari\_Seldon](https://boards.straightdope.com/u/Hari_Seldon)
#### Post date: [January 28, 2011, 2:55pm UTC](https://boards.straightdope.com/t/divisibility-by-seven/568568/12 "2011-01-28T14:55:50Z")
If you care, here is a test for divisibility by 7 (but I think it easier just to divide), but I was having trouble falling asleep last night, so here goes:
Take the units place, add three times the tens place, add twice the hundreds place, subtract the thousands place, subtract three times the ten thousands place, subtract twice the hundred thousands place. Continue using the using coefficients 1, 3, 2, -1, -3, -2. If the result is divisible by 7, so is the original number (and conversely). These numbers are the remainders when successive powers of 10 are divided by 7 (technically the absolutely least remainders, although you could also use the series 1, 3, 2, 6, 4, 5 if you don’t want to subtract).
---
### Author:  [@Lance\_Turbo](https://boards.straightdope.com/u/Lance_Turbo)
#### Post date: [January 28, 2011, 5:18pm UTC](https://boards.straightdope.com/t/divisibility-by-seven/568568/13 "2011-01-28T17:18:09Z")
**Hari** , the method you just posted is one of the methods from the link in post #2.
> [@RadicalPi](#):
>
> Incidentally, why do you determine _n_[SUP]2[/SUP] by (_n_ + 1)(_n_ − 1) + 1? I would think that if _n_ ≡ − 1, that _n_[SUP]2[/SUP] ≡ _n_∙_n_ ≡ (− 1)(− 1) ≡ 1 (mod _n_ + 1). Is there some nuance I’m missing?
I guess I was avoiding using the theorem that (ab) mod m = ((a mod m)(b mod m)) mod m. However, I don’t really see a big difference between the two ways. It’s a fairly trivial fact that both methods explain in one line.
---
### Author:  [@cplif](https://boards.straightdope.com/u/cplif)
#### Post date: [January 28, 2011, 5:39pm UTC](https://boards.straightdope.com/t/divisibility-by-seven/568568/14 "2011-01-28T17:39:07Z")
You could check the Trachtenberg texts, (I’m too lazy to search), there is a way of multiplying by 7, maybe some of you thinkers can deduce something smart.
---
### Author:  [@RealityChuck](https://boards.straightdope.com/u/RealityChuck)
#### Post date: [January 28, 2011, 6:36pm UTC](https://boards.straightdope.com/t/divisibility-by-seven/568568/15 "2011-01-28T18:36:24Z")
> [@RadicalPi](#):
>
> Then **13** is hard again. . . .
Multiply the units digit by four and add the tens digit. If the result is divisible by 13, so is the number.
Not a very useful one, but it works.
---
### Author:  [@statsman1982](https://boards.straightdope.com/u/statsman1982)
#### Post date: [January 28, 2011, 7:10pm UTC](https://boards.straightdope.com/t/divisibility-by-seven/568568/16 "2011-01-28T19:10:54Z")
> [@RadicalPi](#):
>
> As a sort of highjack question (since the OP’s OP has been answered), why are divisibility tests for 7 so much more convoluted than all the others at least up to 13?
>
> **1** : Easy, since given by definition.
> **2**. Easy, since a component of base 10, which means repeatibility.
> **5**. Easy, same as 2.
> **10**. Easy, the actual base, otherwise same as 2 or 5.
>
> But what of **4** and **8**? I guess we could reconsider numbers in base 100 or 1,000 here, thus getting a repeatible pattern. And I guess that’s what actually is happening. Is this right?
>
> **3** and **9**?.. (snip)
Here’s the argument from a charming book _Excursions in Number Theory_ by C. Stanley Ogilvy and John T. Anderson:
Without loss of generality, take a four-digit number _abcd_. We can rewrite this as :
1000a + 100b + 10c + d
= 999a + 99b + 9c
-
```
a + b + c + d
```
Now the first number after the equal sign is always divisible by 3 (or 9). Thus, for the entire number to be divisible by 3 (or 9), we need a + b + c + d to be divisible by 3 (or 9).
ETA: This uses the theorem that if a and b are both divisible by c, then a + b is divisible by c, which can be shown using the transitivity property of modulo arithmetic.
---
### Author:  [@Lance\_Turbo](https://boards.straightdope.com/u/Lance_Turbo)
#### Post date: [January 28, 2011, 8:41pm UTC](https://boards.straightdope.com/t/divisibility-by-seven/568568/17 "2011-01-28T20:41:09Z")
> [@RealityChuck](#):
>
> Multiply the units digit by four and add the tens digit. If the result is divisible by 13, so is the number.
>
> Not a very useful one, but it works.
This is because 4 is the inverse of 10 modulo 13.
Suppose 4a + b = 13k
-\> 10 (4a + b) = 130k
-\> 40a + 10b = 130k
-\> a + 10b = 130k - 39a
-\> a + 10b = 13(10k - 3a)
In other words, any non-negative integer can be written uniquely as 10b + a where 0 \<= a \<= 9. And when 4a + b is a multiple of 13 so is 10b + a.
---
### Author:  [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)
#### Post date: [January 28, 2011, 8:45pm UTC](https://boards.straightdope.com/t/divisibility-by-seven/568568/18 "2011-01-28T20:45:18Z")
All the divisibility tests basically work on the same principle: to test for divisibility by d, or more generally for the remainder when you divide by d, is to work in arithmetic modulo d. But we write numbers in base 10, which is to say, as linear combinations of powers of 10. So the series of coefficients to use in interpreting a string of digits modulo d is the series of powers of 10 modulo d (that is, 1 mod d, 10 mod d, 10^2 mod d, …).
One of two things happens with this series: Either this series eventually hits 0 and stays there, or it eventually returns to 1 and starts cyclically repeating. [The latter happens if 10 is coprime to d; otherwise, the former]. The longer the series takes to do this, the less nice the corresponding divisibility rule.
In other words: the niceness of the divisibility rule for d corresponds to the size of the smallest multiple of d which is either a power of 10 or one less than a power of 10.
[On top of that, the one last bit of sophistication is that we can restrict attention to the case where d is a prime power (since divisibility by a product of powers of distinct primes is the same as divisibility by each factor).]
Everything I’ve said so far works no matter what 10 is, whether it’s “two”, “ten”, or “seventy-six”. But let’s look at what this implies for 10. For the various prime powers d, what does the series of powers of 10 modulo d look like? How long does it take before it hits 0 or re-hits 1? (Or -1, after which it will just take as long again to come back to 1). Well, here’s a chart of the powers of 10 modulo the first several d:
Mod 2: 1, 0
Mod 3: 1, 1
Mod 2^2: 1, 2, 0
Mod 5: 1, 0
Mod 7: 1, 3, 2, -1
Mod 3^2: 1, 1
Mod 11: 1, -1
Mod 13: 1, -3, -4, -1
Mod 17: 1, -7, -2, -3, 4, 6, -8, 5, -1
Mod 19: -9, 5, -7, 6, 3, -8, -4, -2, -1
So, yeah, 7 is a little bad, but not nearly as bad as 17 and 19. The reason the divisibility tests for these aren’t very nice is simply because it takes so long before a string of 9s is divisible by them (in math jargon, 10 has a high multiplicative order modulo these; in fact, 10 is actually a primitive root modulo each of these).
On the other hand, the divisibility test for 13, which is exactly as arduous as that for 7, might be considered surprisingly nice…
---
### Author:  [@Lance\_Turbo](https://boards.straightdope.com/u/Lance_Turbo)
#### Post date: [January 28, 2011, 9:02pm UTC](https://boards.straightdope.com/t/divisibility-by-seven/568568/19 "2011-01-28T21:02:34Z")
> [@Indistinguishable](#):
>
> On the other hand, the divisibility test for 13, which is exactly as arduous as that for 7, might be considered surprisingly nice…
If you want surprisingly nice compute the sequence for 41 and compare it to those of 37 and 43.
---
### Author:  [@Spectre\_of\_Pithecanthropus](https://boards.straightdope.com/u/Spectre_of_Pithecanthropus)
#### Post date: [February 1, 2011, 7:18pm UTC](https://boards.straightdope.com/t/divisibility-by-seven/568568/20 "2011-02-01T19:18:55Z")
> [@Hari\_Seldon](#):
>
> Thus in octal there is a trivial test (sum of the digits) for divisibility by 7.
I came in to mention this, but I wasn’t sure it was exhaustive.
IIRC this can be generalized to any base; e.g. if you were using base 12 the number would be divisible by 11 if the sum of the digits is divisible by 11.
[Next page](https://boards.straightdope.com/t/divisibility-by-seven/568568.md?page=2)