How can you tell whether a number is divisible by 7? Almost everyone knows how to easily tell whether a number is divisible by 2, 3, 5, or 9. A few less know tricks for testing divisibility by 4, 6, 8, or 11. But not many people have ever seen a trick for testing divisibility by 7.
Here’s the trick. Remove the last digit from the number, double it, and subtract it from the first part of the number. Do this repeatedly until you get something you recognize as being divisible by 7 or not.
For example, start with 432. Split into 43 and 2. Subtract 4 from 43 to get 39. Since 39 isn’t divisible by 7, neither is 432.
For another example, start with 8631. Split into 863 and 1. Subtract 2 from 863 to get 861.
Now split 861 into Split into 86 and 1. Subtract 2 from 86. Maybe you recognize 84 as a multiple of 7. If not, double 4 and subtract from 8 to get 0, which is divisible by 7. Either way, we conclude that 8631 is divisible by 7.
Why does this work? Let b be the last digit of a number n and let a be the number we get when we split off b. That says n = 10a + b. Now n is divisible by 7 if and only if n – 21b is divisible by 7. But n – 21b = 10(a − 2b) and this is divisible by 7 if and only if a − 2b is divisible by 7.
What about the remainder when you divide a number by 7? Here’s where the rule for 7 differs from the more familiar divisibility rules. For example, a number is divisible by 3 if its digit sum is divisible by 3, and furthermore the remainder when a number is divided by 3 is the remainder when its digit sum is divided by 3. But the divisibility rule for 7 does not give the remainder when a number is divided by 7. For a simple example, the divisibility rule for 31 terminates in 1, but the remainder with 31 is divided by 7 is 3.
Why doesn’t the divisibility rule for 7 give the remainder? It is true that 10a + b and (10a + b) – 21b have the same remainder when divided by 7. But then we factored this into 10(a − 2b). It’s true that 10(a − 2b) is divisible by 7 if and only if (a − 2b) is divisible by 7, but if neither is divisible by 7 then they will leave different remainders.
If you think of the digits of the number as a vector (315 becomes then you can take the dot product of that with truncated to the right number of digits…so times gives 14, a multiple of 7, so 7 divides into 315 with zero remainder… If we used 316, we would have gotten 15 for the dot product, and so the remainder would be 1.
I talked about this, and some other divisibles in my blog here
Ok, that didn’t work because I tried to use brackets for the vectors… so call 315 ( 3,1,5) and multiply with the vector (5,4,6,2,3,1) truncated (cutting off in the front) to the matching length or, in this case (2,3,1) then your dot product is 14… and that has the same modulus base 7 as the original… Sorry, not thinking clearly today… and the blog link still works.
There are similar tricks for any prime, though they become increasingly unwieldy with size. For 11, subtract the ones digit from the remainder. For 13, add 4 times the ones digit to the remainder. For 17, subtract 5 times the ones digit from the remainder. For 19, add twice the ones digit to the remainder. For 23, add 7 times the ones digit to the remainder. For 29, add 3 times the ones digit to the remainder, and for 31, subtract 3 times the ones digit. Those last two show the general principle, though it rapidly becomes unworkable in one’s head.
Still, just by standing and staring long enough at a number less than 2000, I can figure out whether it’s prime.
John, for larger numbers there is no need to go one digit at a time. Since 7 divides 1001, you can alternately add/subtract in blocks of three, then work with the three digit number. Actually, since 1001 – 7*11*13, you can generate the three digit number once and use it for all three.
Your rule is fine for people who want to use the same algorithm for every problem, but if you switch strategies based on the number, then there are few that can’t be done quickly. Multiplying or dividing by a number other than the prime doesn’t change the divisibility, and adding or subtracting a multiple of the prime doesn’t either.
So, I would have done 8631 as: 631 – 8 = 623; 623 + 7 = 630; 630 / 10 = 63, which is divisible by 7. Checking it for 13 would have been 623 – 13 = 610; 610 / 10 is 61, which is prime and therefore not divisible by 13. And don’t forget that going to a larger number can help too. For example, instead of dividing out the 2’s from 532, use 532 * 2 = 1064, which can be immediately reduced to 64 – 1 = 63.
Mark, I don’t stop at determining prime or not anymore, now I continue so I can compute the total number of factors.
There is a nice rule for divisibility by 11: Just take the digits and instead of adding all digits proceed as follows: take the first digit plus, the second minus, the third plus… asoasf: if the sum is divisible by 11 so is the no. (0 also counts as divisible): e.g. 1001 is +1 -0 +0 -1 -> divisible by 11!
I learned this trick from this new wonderful book:
Mathematics 1001: Absolutely Everything That Matters About Mathematics in 1001 Bite-Sized Explanations by Richard Elwes
HOW DID YOU WORK THIS OUT!?
Amazing!
Well, it’s all on Wikipedia (http://en.wikipedia.org/wiki/Divisibility_rule) so I don’t see why all the buzz.
Well, someone has to create the knowledge before it can be put on Wikipedia. Understanding where facts come from allows you to continue further and discover new facts, whereas looking them up on Wikipedia only lets you use them by rote.
Joss, you can make a rule for any number by splitting it into 10a + b as shown, and then multiplying it by a number x (relatively prime to n) that makes 10x one more or less than a multiple of n, and then using modular arithmetic to reduce 10x to 1 or -1. For instance, in the example given we multiply by 2 to produce 20a + 2b, then -a + 2b since 20 is -1 modulo 7, and then negate all the terms.
If you choose, you don’t have to pick a multiplier that produces a 1 for the rest of the number. So, the rule for 7 can also be 10a + b -> 3a + b, or “three times the digits before the last, plus the last”. It can also be 30a + 3b -> 2a + 3b, or “twice the digits before the last plus 3 times the last”. Generally the rule that produces a 1 is picked as the easiest to compute with in your head.
You can make rules using 100a + b or 1000a + b as well: For 7, 100a + b -> 2a + b, or “twice the digits before the last two, plus the last two digits” – handy for 3 and 4 digit numbers. 1000 = -1 modulo 7 so all you have to do is subtract the thousands from the last three digits to handle 4-6 digit numbers.
Hi,
I wonder, is this rule practical? I mean, number of operations you have to perform here is roughly equal to number of digits in n. In roughly the same number of operations you could divide the number by 7 and find out if it is divisible, as well as the result and reminder, if any.
On an (un)related note, I would like to know a proof for the rule for divisibility by 3. I mean, n = a1 + a2 * 10 + a3 * 100 + … mod 3 = 0 if and only if a1 + a2 + a3 + … mod 3 = 0. Why is that, I wonder?
@kisiel by stating the problem you’ve practically written the proof yourself.
Just add: 10 ≡ 1 (mod 3) then 10^n ≡ 1
then the conclusion falls
a1 + a2 * 10 + a3 * 100 + … + an * 10^n ≡ a1 + a2 + a3 + … + an
and thus as a lemma
a1 + a2 * 10 + a3 * 100 + … mod 3 = 0 if and only if a1 + a2 + a3 + … mod 3 = 0
@John Can’t you get your original remainder back by multiplying your final remainder by 3 as many times as you performed the iteration? Perhaps it’s not as cute anymore at that point.
Thanks!
@Steven:
Good one! So, if I get it right, in octal system there is a rule for divisibility by 7 equivalent to the rule for 3 in decimal system: number is divisible by 7 if and only if sum of all it’s (octal) digits is divisible by 7.
Also, hexadecimal system seems to have the same rule for 15, as well as 3 and 5 (divisors of 15). It’s kind of cool actually :)
Very interesting this method! Thank you to help me and probably many others to approach the maths.
Nice trick!
thanks
Elena
Actually it won’t work for all numbers. For instance , 37905.
since , first take off 5 and double it and then subtract from 3790 then you get 3780. Now here, if we take 0 off and double it then it remains 0 and if you subtract 0 from 3780,then get again 0. It repeats the same….
” So this method is not valid for all numbers…. “
srinivas: From 3780, double 0 and subtract from 378 and you get 378. Now double 8 and subtract from 37 and you get 21. Now you can stop because 21 is obviously divisible by 7. Or if you’d like, continue by doubling 1 and subtracting from 2 to get 0, which is even more obviously divisible by 7 because it’s divisible by everything.
Sir, thank you so much…….
I see this is a couple years old, but…
@kisiel is right, its pretty much just as easy to compute the remainder the good old fashioned way. Actually, with a little practice its even easier to calculate the remainder directly, and there are some nice advantages.
Maybe the cryptography guys all know this, but the trick is to perform short division, but discard the quotient digits completely and just keep track of the remainder. With a divisor of 7, you can do this in your head for dividends of any size, because you handle the digits one at a time from left to right, you don’t even have to be able to remember the dividend. And unlike the trick presented, this method computes the actual remainder, so you can use it for a wider variety of problems than just testing divisibility. Plus, it works on all divisors. This is a nice complement to testing divisibility by 8, and it works equally well for 3, 6, 9, 11 and 13.
I’m not sure why everybody promotes all the divisibility shortcuts before covering this baseline method, but try it! With just a little practice its as easy or easier than all the tricks, and you only have to remember one algorithm.
For example, is 123456789 divisible by 7?
current remainder : 0 1 5 4 2 4 4 5 2
input digit : 1 2 3 4 5 6 7 8 9
new remainder : 1 5 4 2 4 4 5 2 1 -> 1
No, 123456789 mod 7 = 1
For divisibility by 7, please watch this video that compares two rules of divisibility by 7: https://www.youtube.com/watch?v=d8Bmf9BNonU
This is the quickest “Moura Velho” rule of divisibility by 7. Hope you like it.
I am a little interested in these divisibility rules, but not a mathematician.
As a programmer though, I wonder if these rules can be expressed in numbering systems other than base-10.
For instance, I just tested and the divisible-by-three rule does not seem to work in a base-5 number system. I wonder why.
One thing I learned from the above discussions is that there is NOT a way to determine if a number is divisible by seven with a method that can be reliably remembered. The easiest way seems to be the usual way: try dividing the number by seven. Don’t waste your time with any of these alleged shortcuts.
Doing this for math homework -_-
So confused, why 21b???