My favourite divisibility test for 7 is removing multiples of 1001 (=7*11*13). For the number 2716, you can subtract 2002 and get 714, which is obviously divisible by 7. Works great to get big numbers small by subtracting 10010, 100100 and so on.
I don't usually comment on videos, but I had to share this story on this video. I went to grade school with a math whiz who worked out a divisibility test for seven, on his own, in 5th grade (I'm sure it was something along the lines of those in this video, but I'm equally sure he worked it out independently; I wish I could remember what it was). He was as proud as I ever saw him when he showed it to the teacher. The teacher's response was "that's neat, but it's kind of like doing cartwheels to get into your chair when you could just walk; why don't you just do the problems the way I showed you." It wasn't even me and it still hurts to think about.
Well it is a neat trick, but it's sort of an antiquated thing, like unless you have an eidetic memory it's not worth memorizing bc calculators are always immediately available, and finding if something is divisible isn't an especially common a problem in the first place.
And this is why kids end up hating math. Teachers don't let them actually do math, and get excited about it. When a kid does actually do some math on his own the response is "that's neat" at best. Then back to following some formula that someone else came up with a long time ago. I know people need to know what's already out there, but you've gotta encourage innovation at the same time
I think I prefer my own divsibility by n method... 1. Write the number down. 2. Stare at it for ten seconds. 3. Get annoyed that I can't remember any of the divisibility rules I've written down. 4. Give up. 5. Cave in and get a calculator for the actual result. Works like a charm every time. 😂
@@ltloxa1159 my fav is divisibility by n-1 in base-n. In base 10 that would be div by 9. So in binary it can work as div by 3, 7, 15, 31, 63 etc, just by grouping digits into higher 2^N base systems.
If I'm unable to sleep, then I think of a sufficiently large number, but not too large, to check if it's prime. I take an approximate square root in my head, and then I do the check of divisibility for each prime number up until the biggest one less than the original number's square root. Because of this, I had to come up with divisibility rules in my head, and I always used this "take away the last digit, multiply it by a correct number, then subtract or add it to the rest" method. This way, I checked that 8329 is indeed a prime number, thus, it's my favorite one! Coming up with the multipliers was a long mental process, though. I'm glad you made this video, Matt!
I would do the same thing while rollerblading. I determined that 1,023 was not prime that way. I would also determine multiples of large two- and three-digit numbers. It really helped pass the miles . . .
1023 shouldn't take long, but I also ignore a test of 2, 3, and 5 sometimes, which makes the realisation that 3 was a divisor all along really frustrating :D I'm glad I'm not the only one doing mental arithmetic to pass the time
Ha, what a bunch of nerds... anyways when I'm bored/passing time I try to approximate weird probabilities/distributions. Although it's often much harder to actually verify.
Back when the dozenal video came out on Numberphile (at this point, almost a dozen years ago...), I started working out divisibility rules for base 12. For most of the single digit numbers, checking is fairly straightforward. For 2, 3, 4, and 6, it's just a case of looking at the last digit. 144 is divisible by 8, so that just requires the last 2 digits. 11 (el) can be found by summing the digits (for the same reason that 3 and 9 work in base 10). That left 5, 10 (dec), and 7, which I found amusing because 5 and 10 are two of the easiest in base 10. Eventually, I found through trial and error that you could test divisibility by 5 by summing the ones digit, plus twice the 12s digit, plus 4 times the 144s digit, and so on - basically evaluating the number as if it were in base 2 instead of base 12. If the result was divisible by 5, so was the original! The same method works for 10 as well, and a similar method worked for 7 (except you multiply by increasing powers of 5). After working through this, I found a general rule that works in any base: To check if a (base b) is divisible by n (base b), evaluate a as if it were written in base c, where c is the remainder of b/n. If the result is divisible by n, so is a.
I think fairly early on, it’s easier to use the divisibility rule called “long division”. The only multiplying you need to do is working out the N times table up to 9N, and then it works for all values of N the same way. It even tells you *how many* times your number is divisible by N! (That’s just an exclamation mark, not N factorial)
4 години тому+5
IMO if the divisibility test still needs O(n) effort, it needs to be really intuitive, otherwise you are memorising random magic and have to believe that it worked for barely any time gain.
Yeah, doing long division without tracking the outcome is pretty much the same as these methods... 2716 / 7 - 2100 = 616 / 7 -560 = 56 / 7 You don't even need to do it "correctly"; if you see any easy divisor it's fine to switch it up midway 2716 / 7 - 2800 = -84 / 7 / -4 = 21 / 7 (equals signs are modulo 7)
The highest prime test to have been assigned is 23027 (The Taekiro tests). As of the video being released, 23029 and higher are all free real estate! (Coincidentally cut off is between twin primes)
I got three minutes into re-watching your video on the Egyptian papyrus on fractions, and suddenly you show up in a notification telling me you have MORE to tell me on division? THIS CANNOT BE A COINCIDENCE 🤯
My teacher taught me "Drop everything but the last two digits, then if either digit is 4 or higher, subtract 4 from that digit (repeat for 8 or 9). Then check your times table."
@@SkippiiKai Depends on how much of the times table you have memorized. No need to subtract if you know 68 is divisible by 4 off the top of your head, but most kids only learn up to 12 x 12 or so, and 4 x 17 is a bit off to the side.
@@siosilvaryes, but 60 is divisible and 8 is divisible therefore 68 is di isible by 4. Or, 68/2=34 and 34/2=17. When we can divide by 2 twice, we have divided by 4. Practically, I do not use divisible rules but the calculator. 0 decimals indicates divisibility.
The week after i first watched the james grime video, i also knocked together some terrible python code to find divisibility rules for every number up to 10000. To make the rules for composites i had it combine and simplify the divisibility rules for its prime factors into one function. Love the video as always, good stuff
My personal favorite divisibility test for 7 is the test in binary, where you split it up into chunks of three bits and add them up. For example: 100101001001111011 = 152187 splits into 100|101|001|001|111|011 4 5 1 1 7 3 which, added up gets 100 + 101 + 001 + 001 + 111 + 011 = 10101 = 21 (base 10) then 101 + 10 = 111 = 7 The reason I like it so much (besides the fact that it's easy for computers) is that it's functionally identical to the divisibility by 3 or 9 rule, but for binary. I was thinking about the 3 or 9 rule that we learn in elementary school when cutting cucumbers in my kitchen and was wondering about how it extended past those two numbers. I realized that my teachers never told us about how it also applies to 99, thus also 33 and 11 so long as you group the digits into pairs before adding them up. Likewise for 999, 333, 111, and so on for any 10^n-1 and its factors. It was about this point that I cut my finger and had to leave my cucumbers to get a bandaid.
For large decimal numbers, you can reduce them down to at most 6 digits by taking 6 digit chunks and summing them (padding one end of the original number with 0s to get enough digits if needed), which preserves divisibility by 7. It also preserves divisibility by all the other factors of 999999, though among other prime power factors, only 13 needs the full 6 digits - 27 and 37 each work with 3 digit chunks and 11 only needs 2.
@@KevinMcFlying They included a zero at the left side to be able to split the number up into chunks of three without changing the value. 10101 = 010101 Splits into 010 | 101 Add them up 010 +
So what I’m going to take away from this is, when I hear a big number, I can just sagely remark in passing “divisible by one” and nod as if this was a singularly unique talent that I have cultivated.
I like Matt's divisibility-by-7 rule the best as it preserves the remainder. So that, for example, if the final number is one off from being divisible by 7, then the original number is also one off from being divisible by 7.
Fun fact, in seximal (base six), the units-based test will work for any prime greater than 3 out of the box, since all primes greater than 3 end in either 1 or 5 in base six (the 5 version works the same as the 9 version in decimal). Powers of primes other than 2 and 3 (six's factors) will also end in 1 or 5
I remember getting a homework problem as an undergrad to create divisibility tests for various numbers based on modular arithmetic. This leads to some different tests than the ones in the video and is also neat imo. Could be a followup vid.
I just only just now realized the similarity of "Matthew" and "Maths" because of the intro. So it's really, "Stand -up Math-ew"? I must be the last person to notice this.
Another way to prove Michael's is that, at any step, the difference between applying each method is 7×units, so if one is a multiple, then so is the other
My test for is 2716 divisible by 7? take away groups of 7: so let's subtract 2100 and we have 616 left now let's divide by 2: 308 and again: 154 and I know that's divisible by 7 !! voila !!
On the topic of fast prime tests, you should look into (or do a video on) the Miller-Rabin primality test. It's technically probabilistic for each individual witness test, but it is **extremely** fast (as in like basically instant for all 64-bit numbers), and it's fairly easy to implement and understand too. And heck, you _can_ make it be robust and polynomial time if you assume the generalized Reimann hypothesis or use the hand-selected witnesses for your test range.
I am a little surprise the 1001-trick wasn't mentioned. You capture three flies in one bang and it is fast for larger numbers since we don't do operations for every single digit, but instead just every third digit. Since 7•11•13=1001 you can actually check divisibility by both 7,11 and 13 in one nice swoop by utilizing this. Which is extra cool since they are three consecutive primes! Here is how you do it. Example 1: I wonder if 11250057 is divisible by either 7,11 or 13. 1. Group the digit in groups of 3 (hey! That's how we normally write them anyway). So 11 250 057 2. Then make every other group negative (it's wise to choose so we get a positive sum but not necessary). So here -11+250-57 or simply 250-68 = 182. 3. Now all you have to do is to check whether 182 is divisible by either 7,11 or 13. We notice 182=7•26=7•2•13. 4. Cool 182 is divisible by both 7 and 13. Hence 11250057 is divisible by both 7 and 13 but not by 11. Another example 2424737531233. 1. Group the digit in groups of 3 (hey! That's how we normally write them anyway). So 2 424 737 531 233 2. Then make every other group negative (it's wise to choose so we get a positive sum but not necessary). So here 2-424+737-531+233 = (2+737+233)-(424+531)=972-955=17 3. Now all you have to do is to check whether 17 is divisible by either 7,11 or 13. We notice 17 is prime. 4. Cool 2424737531233 is neither divisible by 7, 11 nor 13.
The explanation for how all this works is so much more easy and beautiful! It all comes down to modulo classes. Take Michael's approach. Split any number into two parts so that the number equals 10a+b. If that is divisible by 7, then 3a+b is as well, which if multiplied with 3 is still divisible by 7: 9a+3b. Subtract that from 10a+b and you get a-2b which gives the same rest as a+5b. And that's his formula. Using those calculations you can get super nice divisibility checks. E.g. for 7: Take the first digit. Multiply with 3. Add the next digit. Multiply with 3, add the next digit... Until you added the last digit. E.g. 112: 1*3 = 3, +1 = 4, *3 = 12, +2 =14 which is divisible by 7, so 112 is as well.
wow i feel proud i was looking at your thumbnail and was like 'hey that reminds me of an old ding video' and i was instantly validated :D thank you mr count binface counting agent parker
This is a nice explainer. At the start of the video, I paused and proved the modulus 7 congruence of 10a+b and a+5b and a-2b. This method turned out to be straightforward once I observed that 7a and 7b are both congruent to 0 modulo 7. It also required division by 3, so 3 must be coprime with 7. Which, yeah, no problem there. Generalizing this method could be tricky for a non-prime modulus. Other bases would be easy with this method. Instead of starting from 10a+b, just start from base*a+b, or raise the base to a greater power if you want to remove multiple digits at once.
I like to think about divisibility tests in terms of the number whose moduli the digital addition preserves, because doing so makes it clear why the tests work. Like, adding up the digits is the 9 test, or adding pairs of digits is the 99 test (useful for multiples of 11 obviously). I use the 98 test for 7, which is just the Matt method, but for long numbers I just break it up into two-digit pairs right off the bat, then multiplying the higher-order pairs by increasing powers of two.
I was once in a unique situation: at a competition where I knew I had ten minutes to answer a question about arithmetic mod 7. So before I started, I wrote down the multiples of 3 mod 7 for digits 0-9 so that I could start with the first digit and multiply by 3 and add the next digit all while taking mod 7, effectively evaluating the base-10 expansion of the number (10 mod 7 = 3). The interesting thing though is that this is generalizable-by simply starting with the first digit and continuously multiplying by 10 and adding the next digit all while taking the modulo of the number for which you want to test divisibility, you can compute any number modulo any other number without having to divide large numbers and test for divisibility by seeing if the result is 0 or not. It wouldn't be too far or a stretch to call this "the universal divisibility test".
Funnily enough I find basically just doing the division so much faster than almost any divisibility trick. Obviously there are exceptions for 2 or 3 or the really easy numbers but at any point where you have to do a calculation or add/subtract different parts of the number i just do it straight up 7889/7 -7000 889-700 189-140 49 is divisible by 7. If I slowed down I would see it’s 1127x7 but if I just want to know whether it’s divisible or not I can just skip the division part and do most of the method for short division in my head The video example: 2716 -2100 616 -560 56 is divisible by 7
The "you can just subtract out batches" approach has led me to a divisibility test that I think I like in practice: Subtract out 5*10^n for the largest n that makes that less than the number you're testing, then add 10^(n-1). So for 2716, you'd remove 5 500s and add 5 10s; 2716-> 216 -> 266. You've removed 490 5 times, which is a multiple of 7. Then remove 50 5 times and add 5 1s; 266 -> 16 -> 21. You've removed 49 5 times. That's a multiple of 7 so we're done. It's nice because you are just working with multiples of 10, which I find easier to manipulate in my head, even if it is based on the same basic math as the Veritasium approach.
Matt's "but I didn't stop there", reminds me of a scene from a British sitcom called My Hero, where a doctor says "Apparently one dose is enough to bring a giraffe to its knees.... so I put in 4".
This was the Masters Round question at the State MathCOUNTS competition when I was in 8th grade! I was the NH state champion that year, but I didn't really do well with this one at 12.
IMO the first method shown is definitely better than the second, as Matt sort of nodded at the difference in effort/time/error opportunity of multiplying a single digit by 2 vs 5 is massively overwhelmed by the difference in effort/time/error opportunity of adding vs subtracting, especially if working in your head (this is not to say that either is particularly hard, but small differences can add up for larger numbers with this kind of iterative process)
"I called it the vsause method." We live in a bizarre world where, if Matt comes up with something that actually works, he can't call it the Parker method, because that would make people think there was something wrong with it!
Here is another one that converges to 7 by repeating the step. Let’s denote the original number as ( N ). We can express ( N ) in terms of its digits. For example, if ( N = 308 ), we can write it as: [ N = 10a + b ] where ( a ) is the number formed by all digits except the last one (in this case, 30), and ( b ) is the last digit (in this case, 8). 1. Remove the last digit ( b ). 2. Multiply the remaining number ( a ) by 3. 3. Add back the last digit ( b ). This gives us a new number 98 Repeat (9 × 3) + 7 = 35 And again (3 × 3) + 5 = 14 And finally (1 × 3) + 4 = 7
3:49 I can already tell the reason these both work is related to modular arithmetic because the +5 and -2 relate to a position mod 7. If the last digit is a 1, then it’s saying that the remainder of the digits is congruent to 2 (mod 7), so adding 5 or subtracting 2 return you to 7. If it doesn’t, then you can conclusively say that the remaining digits don’t maintain the property they need to be a multiple of 7 with the extra digit afterwards. In fact, you can apply the same logic to the Matt test as far as I can tell. Multiply those first two digits by 5 and subtract the result from the last two. Yeah, you’ll end up with a negative number, but it’ll be divisible by 7.
Fun algorithm to make a list of primes: Make an array of bits and set it to all 1s. Iterate through the array: if 1, set every multiple of the prime index to 0. If 0, skip. What remains is an array where each prime index is 1, and each composite index is 0.
I didn't realise how easy and interesting it was to prove the 7 divisibility rules. (I proved as you went through the divisibility rules. Like I proved the simple ones, but honestly can't really remember the 7 divisibility rule because it's often easier to just use short division in my opinion...
I've been using a very similar algorithm since forever (I did prime factorization as a way to pass the time in school lol), subtracting large known multiples of 7, or subtracting the test number from them. It's slightly faster than removing small multiples and dividing by 10 I think, but your method is nicer. Maybe I'll start doing factorizations again when work is slow, there are a lot more 4-digit numbers than 3-digit ones.[citation needed]
*does a convoluted test for multiples of 1009 when no one asked except him and calculators exist* 19:46 "MATHS!" "Now that's applied useful mathematics."
I have the test for 8513. Take the 10,000s, multiply by 1487, and add to the rest. Multiply the units by 2554 and add. Thanks for all the great videos Matt.
Divisibility Rules! What does Divisibility rule? Was Divisibility elected? "Well, I didn't vote for you." "Help, I'm being repressed!" That would have been funny a few years ago; now I just made myself sad again.
This "times 5 plus the rest" kinda reminds me of the 3x+1 problem. If you continue the method after 35, you get 28, 42, 14, 21 and 7. And if you do this method one more time, 7*5+0, you loop back to 35 again.
I've always used the 21 rule (james) myself, and never even considered using the 49 rule (michael). But your 98 rule is pretty good and i might start using it sometimes also.
Idk if it's more computationally efficient, but you can test for divisibility by a power of a prime just by first testing by that prime and if it succeeds, divide the number by the prime and try again. For instance, if you're trying to test if an arbitrary number is divisible by 9, you can just test for 3, then divide by 3 and test again.
I think this was one of the best maths videos on UA-cam, thoroughly enjoyed it! I've always wondered - of course, not so much as to look it up - how those divisiblity rules are created. Now I wonder, are there any other generalizable methods besides summing/subtracting to a power of 10 🤔
A general rule I like to remember is that if the divisor's rightmost digit is co-prime to the base (1, 3, 7, and 9 in base 10), then each multiple from 0-9 of that divisor has a unique digit in the 1's place; this means that you can do some pretty simple "backwards" long division. Let's say we want to see if 63893 is divisible by 7 (I have no clue if it is yet): 63893-63=63830 63830-630=63200 63200-4200=59000 (which is clearly not divisible by 7) May not be the easiest mental math method, but can reasonably be done quickly with pencil and paper; just scratch out the multiples of the divisor from 1-9 to the side and subtract whichever one matches the current rightmost non-zero digit.
I've been trying to find some unexpectedly juicy simple ones, but for the most part the juicy ones are pretty expected, like this one: 4999 is a prime and has the 'Justin' tests: Take the 10,000s, multiply by 2, and add to the rest. Multiply the units by 500 and add. Very easy, but also it's so close to 5k you probably wouldn't have had trouble to begin with. Still though, it's quite juicy.
If you have a subtract test, you can easily convert it to the add test by subtracting the multiplier from the factor. For example. let's say you have the subtract test for 7 in mind. The multiplier is 2. 7 - 2 = 5. Now you have the multiplier for the add test for 7. This works because any number that is 2n above a multiple of 7 will also be 5n below another multiple of 7.
6:31 "If I care that it is divisible by 7, I don't care about any other factor. I could actually divide-out other factors and that won't change if it is or is not divisible by 7." > That's only true as long as the factors you divide-out by are not multiples of 7.
The easiest method is taking your base10 number 1000x3+100x2+10x1+x0 and taking 6x3+2x2+3x1+x0. As 1000mod7, 100mod7, 10mod7 is 6,2,3. Reduces extremely fast. Best method by far.
I remember looking at powers of 11 and realising it resembles the pascals triangle. After thinking about it for a while i realised its because you can write powers of 11 as (10 + 1) ^ n. Which is known to resemble the pascals triangle. I always imagined that the divisibility rules have a similar proof requiring the decomposition of numbers but this is a little easier.
Loving this video, enjoyed the Ding video and will remember the method better much better now I have the Why. (I'm sticking with the Ding method because mutiply by 5 and add a multiple of 5 is the easiest)
The way I see the 6720 check: 6720 / 20 = 336 336 = 350 - 14 350 & 14 are divisible by 7 ✅ "Is the distance to an obvious multiple of X also an obvious multiple of X" is one of my essential go-to's.
I always check the divisibility by seven (or any other number) by comparing to big multiples close to the number. So for example, I'd do: 2716-2100 = 616 700-616 = 84 84-70 = 14 14 is divisible by seven, so 2716 is too!
*OMG* Amazingly, this approach also proves the Reimann hypothesis. Allow me to explain... Oh shoot, this comment box is just a bit too small. I'll get back to you.
On the Second Method you used, with "Double the Last then Subtract it" If you End up with Zero, You actually don't confirm the Multiple. Lol, I'm just being a stickler, but you said if you did happen to end with Zero it would confirm it. Just a flubb though You are Brilliant
You can kind of get the test with modular arithmetic you need 10x+y to be equivallent to x+a*y in mod 7 if they're equivallent to 0 10x + y = 0 (mod 7) -> y = -10x = 4x (mod 7) x + a*y = 0 (mod 7) -> x = -ay (mod 7) substitute one equation on the other and you get x = 10a*x = -4a*x (mod 7) so you just need to find a value of a such that -4a = 1 (mod 7) the solutions are 5 and -2 (which are equivallent) -4*-2 = 8 = 7+1 -4*5 = -20 = -21 + 1 If you're using python you can get the solution straight away by doing pow(10,-1,7)
I like to imagine Terrible Python is a version of Python, and Matt is very good at programming it.
It's slightly more efficient than Monty Python.
so, Parker Python?
Python is already terrible, though
@@DanielHarveyDyer A nice bit of recursion there, seeing as Python is also named for Monty Python. Sadly, an infinite loop.
@@WildMatsu import bait
My favourite divisibility test for 7 is removing multiples of 1001 (=7*11*13). For the number 2716, you can subtract 2002 and get 714, which is obviously divisible by 7.
Works great to get big numbers small by subtracting 10010, 100100 and so on.
This is also my favourite, especially because it works for 11 and 13 at the same time :)
I wish I knew that one when I was actually participating in math competitions, and not just doing math at home, here I can just check online :/
You can phrase this test differently: Divide your number into blocks of three digits and then add and sub these blocks alternatingly.
That gives me linear algebra vibes
I don't usually comment on videos, but I had to share this story on this video. I went to grade school with a math whiz who worked out a divisibility test for seven, on his own, in 5th grade (I'm sure it was something along the lines of those in this video, but I'm equally sure he worked it out independently; I wish I could remember what it was). He was as proud as I ever saw him when he showed it to the teacher. The teacher's response was "that's neat, but it's kind of like doing cartwheels to get into your chair when you could just walk; why don't you just do the problems the way I showed you." It wasn't even me and it still hurts to think about.
I had a 5th grade teacher just like that. He thought outsmarting ten year olds made him pretty slick.
Well it is a neat trick, but it's sort of an antiquated thing, like unless you have an eidetic memory it's not worth memorizing bc calculators are always immediately available, and finding if something is divisible isn't an especially common a problem in the first place.
And this is why kids end up hating math. Teachers don't let them actually do math, and get excited about it. When a kid does actually do some math on his own the response is "that's neat" at best. Then back to following some formula that someone else came up with a long time ago.
I know people need to know what's already out there, but you've gotta encourage innovation at the same time
I remember being in 4th grade or so and I figured out how to make consistent divisibility rules for all prime numbers. I don't remember how.
@@noahdavid5258Divisibility rules for prime numbers ⁉️
Someone's about to make this code a 10000000000% more efficient
I think I prefer my own divsibility by n method...
1. Write the number down.
2. Stare at it for ten seconds.
3. Get annoyed that I can't remember any of the divisibility rules I've written down.
4. Give up.
5. Cave in and get a calculator for the actual result.
Works like a charm every time. 😂
As a programmer, my favourite divisibility test is:
return x%n == 0
!(x%n)
For powers of 2 i like x & ((1
Hi I'm javascript. -18%9 = -0 and -16%9 = -7. I'm so good at math.
@pwnchip, nice
@@eu7059 Only in languages with weak type systems, where you can freely cast integers to bools.
This is so base 10 focused. To test if its devisable by a number x, first convert to base x, and if it ends with a zero, its dividable by that..
That’s basically just doing the divison 😂
On a more serious note, there are some very interesting patterns when you look at divisibility rules for different bases.
Are you serious now?
@@waz1y woosh
@@ltloxa1159 my fav is divisibility by n-1 in base-n. In base 10 that would be div by 9. So in binary it can work as div by 3, 7, 15, 31, 63 etc, just by grouping digits into higher 2^N base systems.
That Wikipedia article is about to get a lot bigger.
I’ll definitely add “my” test to the Wikipedia page!
If I'm unable to sleep, then I think of a sufficiently large number, but not too large, to check if it's prime. I take an approximate square root in my head, and then I do the check of divisibility for each prime number up until the biggest one less than the original number's square root.
Because of this, I had to come up with divisibility rules in my head, and I always used this "take away the last digit, multiply it by a correct number, then subtract or add it to the rest" method. This way, I checked that 8329 is indeed a prime number, thus, it's my favorite one!
Coming up with the multipliers was a long mental process, though. I'm glad you made this video, Matt!
I would do the same thing while rollerblading. I determined that 1,023 was not prime that way. I would also determine multiples of large two- and three-digit numbers. It really helped pass the miles . . .
1023 shouldn't take long, but I also ignore a test of 2, 3, and 5 sometimes, which makes the realisation that 3 was a divisor all along really frustrating :D I'm glad I'm not the only one doing mental arithmetic to pass the time
Ha, what a bunch of nerds... anyways when I'm bored/passing time I try to approximate weird probabilities/distributions. Although it's often much harder to actually verify.
Back when the dozenal video came out on Numberphile (at this point, almost a dozen years ago...), I started working out divisibility rules for base 12. For most of the single digit numbers, checking is fairly straightforward. For 2, 3, 4, and 6, it's just a case of looking at the last digit. 144 is divisible by 8, so that just requires the last 2 digits. 11 (el) can be found by summing the digits (for the same reason that 3 and 9 work in base 10). That left 5, 10 (dec), and 7, which I found amusing because 5 and 10 are two of the easiest in base 10.
Eventually, I found through trial and error that you could test divisibility by 5 by summing the ones digit, plus twice the 12s digit, plus 4 times the 144s digit, and so on - basically evaluating the number as if it were in base 2 instead of base 12. If the result was divisible by 5, so was the original!
The same method works for 10 as well, and a similar method worked for 7 (except you multiply by increasing powers of 5). After working through this, I found a general rule that works in any base:
To check if a (base b) is divisible by n (base b), evaluate a as if it were written in base c, where c is the remainder of b/n. If the result is divisible by n, so is a.
I think fairly early on, it’s easier to use the divisibility rule called “long division”. The only multiplying you need to do is working out the N times table up to 9N, and then it works for all values of N the same way. It even tells you *how many* times your number is divisible by N! (That’s just an exclamation mark, not N factorial)
IMO if the divisibility test still needs O(n) effort, it needs to be really intuitive, otherwise you are memorising random magic and have to believe that it worked for barely any time gain.
You mean O(logn), all of the tests described in the video, as well as long division itself, are proportional to the length of n, not n itself.
@@phiefer3 Oh yeah, sorry, I thought of n as the number of digits.
Yeah, doing long division without tracking the outcome is pretty much the same as these methods...
2716 / 7
- 2100 =
616 / 7
-560 =
56 / 7
You don't even need to do it "correctly"; if you see any easy divisor it's fine to switch it up midway
2716 / 7
- 2800 =
-84 / 7
/ -4 =
21 / 7
(equals signs are modulo 7)
The highest prime test to have been assigned is 23027 (The Taekiro tests). As of the video being released, 23029 and higher are all free real estate! (Coincidentally cut off is between twin primes)
I got three minutes into re-watching your video on the Egyptian papyrus on fractions, and suddenly you show up in a notification telling me you have MORE to tell me on division? THIS CANNOT BE A COINCIDENCE 🤯
Matt: "We are putting the prime numbers on ebay."
Also Matt: *holds up the number 9*
9 is a Parker prime
9 is in fact 3x3, it's a parker square
He's doing integers by parts
No, it was a 6, but he was holding it upside down.
9 is the smallest fake prime in base 10.
"Divisibility Rules" is the motivational phrase that keeps the composites going.
4:36 Surely, it should be called the Parker method. Gotta follow the theme.
Too bad there are no "spelling" rules for the title card at 1:00.
took me longer than i care to admit to spot the errror
@@servvonot sure that's an error exactly. When the word gets divided and shifts, the 'I' appears
I remember asking my teacher in 4 the grade what the test for divisibility by 4 was. He looked at me like i had a squid hat on.
My teacher taught me "Drop everything but the last two digits, then if either digit is 4 or higher, subtract 4 from that digit (repeat for 8 or 9). Then check your times table."
@@torokkuroi6928that seems unnecessary complicated.
@@SkippiiKai Depends on how much of the times table you have memorized. No need to subtract if you know 68 is divisible by 4 off the top of your head, but most kids only learn up to 12 x 12 or so, and 4 x 17 is a bit off to the side.
@@siosilvaryes, but 60 is divisible and 8 is divisible therefore 68 is di isible by 4.
Or, 68/2=34 and 34/2=17. When we can divide by 2 twice, we have divided by 4.
Practically, I do not use divisible rules but the calculator. 0 decimals indicates divisibility.
@@torokkuroi6928 What I teach my students is "drop everything but the last two digits and divide them by 2. If the result is even it's divisible by 4"
@ 3:08 If you actually continue with 35:
25 + 3 = 28 =>
40 + 2 = 42 =>
10 + 4 = 14 =>
20 + 1 = 21 =>
5 + 2 = 7.
7 is divisible by 7! And 7*5 = 35 where this started.
7 is not divisible by 7! you'd get 1/6!
7! is divisible by 7 as well :v
Not to be that guy, but.... 7 isn't divisible by 7!
Came to the comments looking for this. I love how it jumps up and down.
The week after i first watched the james grime video, i also knocked together some terrible python code to find divisibility rules for every number up to 10000. To make the rules for composites i had it combine and simplify the divisibility rules for its prime factors into one function. Love the video as always, good stuff
My personal favorite divisibility test for 7 is the test in binary, where you split it up into chunks of three bits and add them up.
For example:
100101001001111011 = 152187
splits into
100|101|001|001|111|011
4 5 1 1 7 3
which, added up gets
100 +
101 +
001 +
001 +
111 +
011 =
10101 = 21 (base 10)
then
101 +
10 =
111 = 7
The reason I like it so much (besides the fact that it's easy for computers) is that it's functionally identical to the divisibility by 3 or 9 rule, but for binary. I was thinking about the 3 or 9 rule that we learn in elementary school when cutting cucumbers in my kitchen and was wondering about how it extended past those two numbers. I realized that my teachers never told us about how it also applies to 99, thus also 33 and 11 so long as you group the digits into pairs before adding them up. Likewise for 999, 333, 111, and so on for any 10^n-1 and its factors. It was about this point that I cut my finger and had to leave my cucumbers to get a bandaid.
oh no! wonderful story though
My favorite divisibility-by-7 test is in septimal, but quadrodecimal is quite okay too.
You get 10101, but then you add 101 and 10 as if you'd gotten 10110? What's going on?
For large decimal numbers, you can reduce them down to at most 6 digits by taking 6 digit chunks and summing them (padding one end of the original number with 0s to get enough digits if needed), which preserves divisibility by 7. It also preserves divisibility by all the other factors of 999999, though among other prime power factors, only 13 needs the full 6 digits - 27 and 37 each work with 3 digit chunks and 11 only needs 2.
@@KevinMcFlying
They included a zero at the left side to be able to split the number up into chunks of three without changing the value.
10101 =
010101
Splits into
010 | 101
Add them up
010 +
So what I’m going to take away from this is, when I hear a big number, I can just sagely remark in passing “divisible by one” and nod as if this was a singularly unique talent that I have cultivated.
23:32 that's the most unhinged thing I've ever heard. I'm gonna have to lie down for a bit
I like Matt's divisibility-by-7 rule the best as it preserves the remainder. So that, for example, if the final number is one off from being divisible by 7, then the original number is also one off from being divisible by 7.
You can preserve the remainder with the Michael/Grime tests for 7 by iterating them 6n times.
Terrible Python Code is the real star of this show
I want a Terrible Python Code t-shirt.
Fun fact, in seximal (base six), the units-based test will work for any prime greater than 3 out of the box, since all primes greater than 3 end in either 1 or 5 in base six (the 5 version works the same as the 9 version in decimal). Powers of primes other than 2 and 3 (six's factors) will also end in 1 or 5
I remember getting a homework problem as an undergrad to create divisibility tests for various numbers based on modular arithmetic. This leads to some different tests than the ones in the video and is also neat imo. Could be a followup vid.
I just only just now realized the similarity of "Matthew" and "Maths" because of the intro. So it's really, "Stand -up Math-ew"? I must be the last person to notice this.
Just only just now
omg me to
Another way to prove Michael's is that, at any step, the difference between applying each method is 7×units, so if one is a multiple, then so is the other
My test for is 2716 divisible by 7?
take away groups of 7: so let's subtract 2100 and we have 616 left
now let's divide by 2: 308
and again: 154
and I know that's divisible by 7 !!
voila !!
I just added 14, got to 2730, then added 70 to get to 2800. for large numbers, I find it easier to go up instead of down.
Congruent-ulations!!! 🎉
Even better, just subtract 2800 from 2716, which gives you -84. 84 is 14 more than 70, so it's a multiple of 7
My way : 2716 = 2016 + (700) ; 2016 = (2100) + 16 - 100 ; 16 - 100 = 16 - (98) -2 ; 16 - 2 = 14 = 7/2. Yay !
On the topic of fast prime tests, you should look into (or do a video on) the Miller-Rabin primality test. It's technically probabilistic for each individual witness test, but it is **extremely** fast (as in like basically instant for all 64-bit numbers), and it's fairly easy to implement and understand too. And heck, you _can_ make it be robust and polynomial time if you assume the generalized Reimann hypothesis or use the hand-selected witnesses for your test range.
I am a little surprise the 1001-trick wasn't mentioned. You capture three flies in one bang and it is fast for larger numbers since we don't do operations for every single digit, but instead just every third digit. Since 7•11•13=1001 you can actually check divisibility by both 7,11 and 13 in one nice swoop by utilizing this. Which is extra cool since they are three consecutive primes!
Here is how you do it. Example 1: I wonder if 11250057 is divisible by either 7,11 or 13.
1. Group the digit in groups of 3 (hey! That's how we normally write them anyway). So 11 250 057
2. Then make every other group negative (it's wise to choose so we get a positive sum but not necessary). So here -11+250-57 or simply 250-68 = 182.
3. Now all you have to do is to check whether 182 is divisible by either 7,11 or 13. We notice 182=7•26=7•2•13.
4. Cool 182 is divisible by both 7 and 13. Hence 11250057 is divisible by both 7 and 13 but not by 11.
Another example 2424737531233.
1. Group the digit in groups of 3 (hey! That's how we normally write them anyway). So 2 424 737 531 233
2. Then make every other group negative (it's wise to choose so we get a positive sum but not necessary). So here 2-424+737-531+233 = (2+737+233)-(424+531)=972-955=17
3. Now all you have to do is to check whether 17 is divisible by either 7,11 or 13. We notice 17 is prime.
4. Cool 2424737531233 is neither divisible by 7, 11 nor 13.
The explanation for how all this works is so much more easy and beautiful! It all comes down to modulo classes. Take Michael's approach. Split any number into two parts so that the number equals 10a+b. If that is divisible by 7, then 3a+b is as well, which if multiplied with 3 is still divisible by 7: 9a+3b. Subtract that from 10a+b and you get a-2b which gives the same rest as a+5b. And that's his formula. Using those calculations you can get super nice divisibility checks. E.g. for 7: Take the first digit. Multiply with 3. Add the next digit. Multiply with 3, add the next digit... Until you added the last digit.
E.g. 112: 1*3 = 3, +1 = 4, *3 = 12, +2 =14 which is divisible by 7, so 112 is as well.
And if you take -3 instead of 3 you get the divisibility rule for 13.
Hey Matt, Vsauce here 9:56 is how Michael does everything
wow i feel proud i was looking at your thumbnail and was like 'hey that reminds me of an old ding video' and i was instantly validated :D
thank you mr count binface counting agent parker
Ive always wanted a vid like this
This is a nice explainer. At the start of the video, I paused and proved the modulus 7 congruence of 10a+b and a+5b and a-2b.
This method turned out to be straightforward once I observed that 7a and 7b are both congruent to 0 modulo 7. It also required division by 3, so 3 must be coprime with 7. Which, yeah, no problem there.
Generalizing this method could be tricky for a non-prime modulus.
Other bases would be easy with this method. Instead of starting from 10a+b, just start from base*a+b, or raise the base to a greater power if you want to remove multiple digits at once.
Divisibility does rule!
divide and rule
I like to think about divisibility tests in terms of the number whose moduli the digital addition preserves, because doing so makes it clear why the tests work. Like, adding up the digits is the 9 test, or adding pairs of digits is the 99 test (useful for multiples of 11 obviously). I use the 98 test for 7, which is just the Matt method, but for long numbers I just break it up into two-digit pairs right off the bat, then multiplying the higher-order pairs by increasing powers of two.
I was once in a unique situation: at a competition where I knew I had ten minutes to answer a question about arithmetic mod 7. So before I started, I wrote down the multiples of 3 mod 7 for digits 0-9 so that I could start with the first digit and multiply by 3 and add the next digit all while taking mod 7, effectively evaluating the base-10 expansion of the number (10 mod 7 = 3). The interesting thing though is that this is generalizable-by simply starting with the first digit and continuously multiplying by 10 and adding the next digit all while taking the modulo of the number for which you want to test divisibility, you can compute any number modulo any other number without having to divide large numbers and test for divisibility by seeing if the result is 0 or not. It wouldn't be too far or a stretch to call this "the universal divisibility test".
Funnily enough I find basically just doing the division so much faster than almost any divisibility trick. Obviously there are exceptions for 2 or 3 or the really easy numbers but at any point where you have to do a calculation or add/subtract different parts of the number i just do it straight up
7889/7
-7000
889-700
189-140
49 is divisible by 7. If I slowed down I would see it’s 1127x7 but if I just want to know whether it’s divisible or not I can just skip the division part and do most of the method for short division in my head
The video example:
2716
-2100
616
-560
56 is divisible by 7
Divisibility does rule
“It’s terrible python code time” gave me a pretty good laugh 😄
19:40 so that's why I see 1312 graffitis everywhere
I am assuming this is referencing something completely unrelated to the video.
My curiosity is piqued. I would be most grateful if you would sate it.
1 = a, 2 = b, 3 = c and the rest is US politics
@@2001PiepsNo need for American exceptionalism, ACAB works just fine over here in Europe as well.
@@2001Pieps Officer Matt Thorton, among many others.
@@Antanana_Rivo Originated in the UK, in fact
I just want to say thank you Matt. That shelf behind you drives me absolutely bonkers being crooked in frame.
The "you can just subtract out batches" approach has led me to a divisibility test that I think I like in practice: Subtract out 5*10^n for the largest n that makes that less than the number you're testing, then add 10^(n-1). So for 2716, you'd remove 5 500s and add 5 10s; 2716-> 216 -> 266. You've removed 490 5 times, which is a multiple of 7. Then remove 50 5 times and add 5 1s; 266 -> 16 -> 21. You've removed 49 5 times. That's a multiple of 7 so we're done. It's nice because you are just working with multiples of 10, which I find easier to manipulate in my head, even if it is based on the same basic math as the Veritasium approach.
I use the engineer's method of divisibility testing. Pull out the calculator and look for a decimal.
But, what if the answer is 4.0
There's a decimal right there
10000000000001 is arguably divisible by 10
@@skyjoe55As an engineer, I responsibly declare: it is divisible by 10. The main thing is to be within the margin of error
Some other people who are not Matt Parker or Steve Mould also known as Bec Hill!
Who graciously loaned the dice used in this video!
loaner of the Dice Jar of 458 Dice
Matt's "but I didn't stop there", reminds me of a scene from a British sitcom called My Hero, where a doctor says "Apparently one dose is enough to bring a giraffe to its knees.... so I put in 4".
Ah! This is so cool, no more wobbling whiteboard held in one hand. The top camera view of the entire page on the desktop is so cool!
Thanks Matt.
This was the Masters Round question at the State MathCOUNTS competition when I was in 8th grade! I was the NH state champion that year, but I didn't really do well with this one at 12.
14:40 classic Parker multiplication… off by a 1.
IMO the first method shown is definitely better than the second, as Matt sort of nodded at the difference in effort/time/error opportunity of multiplying a single digit by 2 vs 5 is massively overwhelmed by the difference in effort/time/error opportunity of adding vs subtracting, especially if working in your head (this is not to say that either is particularly hard, but small differences can add up for larger numbers with this kind of iterative process)
"I called it the vsause method." We live in a bizarre world where, if Matt comes up with something that actually works, he can't call it the Parker method, because that would make people think there was something wrong with it!
Here is another one that converges to 7 by repeating the step.
Let’s denote the original number as ( N ). We can express ( N ) in terms of its digits. For example, if ( N = 308 ), we can write it as:
[ N = 10a + b ]
where ( a ) is the number formed by all digits except the last one (in this case, 30), and ( b ) is the last digit (in this case, 8).
1. Remove the last digit ( b ).
2. Multiply the remaining number ( a ) by 3.
3. Add back the last digit ( b ).
This gives us a new number 98
Repeat
(9 × 3) + 7 = 35
And again
(3 × 3) + 5 = 14
And finally
(1 × 3) + 4 = 7
3:49 I can already tell the reason these both work is related to modular arithmetic because the +5 and -2 relate to a position mod 7. If the last digit is a 1, then it’s saying that the remainder of the digits is congruent to 2 (mod 7), so adding 5 or subtracting 2 return you to 7.
If it doesn’t, then you can conclusively say that the remaining digits don’t maintain the property they need to be a multiple of 7 with the extra digit afterwards.
In fact, you can apply the same logic to the Matt test as far as I can tell. Multiply those first two digits by 5 and subtract the result from the last two. Yeah, you’ll end up with a negative number, but it’ll be divisible by 7.
Fun algorithm to make a list of primes: Make an array of bits and set it to all 1s. Iterate through the array: if 1, set every multiple of the prime index to 0. If 0, skip. What remains is an array where each prime index is 1, and each composite index is 0.
For whatever reason I really liked what you did with the intro :)
Hello Matt, thank you for keeping maths fresh. Also - good man for declaring the ownership of the dice, just as promised
I didn't realise how easy and interesting it was to prove the 7 divisibility rules. (I proved as you went through the divisibility rules.
Like I proved the simple ones, but honestly can't really remember the 7 divisibility rule because it's often easier to just use short division in my opinion...
I've been using a very similar algorithm since forever (I did prime factorization as a way to pass the time in school lol), subtracting large known multiples of 7, or subtracting the test number from them. It's slightly faster than removing small multiples and dividing by 10 I think, but your method is nicer.
Maybe I'll start doing factorizations again when work is slow, there are a lot more 4-digit numbers than 3-digit ones.[citation needed]
*does a convoluted test for multiples of 1009 when no one asked except him and calculators exist*
19:46
"MATHS!"
"Now that's applied useful mathematics."
I have the test for 8513.
Take the 10,000s, multiply by 1487, and add to the rest.
Multiply the units by 2554 and add.
Thanks for all the great videos Matt.
I love this because Matt is having a computer produce pen-and-paper arithmetic tricks.
Divisibility Rules! What does Divisibility rule? Was Divisibility elected? "Well, I didn't vote for you." "Help, I'm being repressed!"
That would have been funny a few years ago; now I just made myself sad again.
This "times 5 plus the rest" kinda reminds me of the 3x+1 problem.
If you continue the method after 35, you get 28, 42, 14, 21 and 7. And if you do this method one more time, 7*5+0, you loop back to 35 again.
23:38 is the best maths programming joke
luckily in binary every prime (>2) already ends in 1. 16:31
Dice on loan from the bec hill collection always amazing
Loving the call back to the regex prime test.
I’d definitely watch a livestream of Matt checking if really big numbers are divisible by 7. Its very satisfying
I've always used the 21 rule (james) myself, and never even considered using the 49 rule (michael). But your 98 rule is pretty good and i might start using it sometimes also.
Idk if it's more computationally efficient, but you can test for divisibility by a power of a prime just by first testing by that prime and if it succeeds, divide the number by the prime and try again. For instance, if you're trying to test if an arbitrary number is divisible by 9, you can just test for 3, then divide by 3 and test again.
I think this was one of the best maths videos on UA-cam, thoroughly enjoyed it! I've always wondered - of course, not so much as to look it up - how those divisiblity rules are created.
Now I wonder, are there any other generalizable methods besides summing/subtracting to a power of 10 🤔
A general rule I like to remember is that if the divisor's rightmost digit is co-prime to the base (1, 3, 7, and 9 in base 10), then each multiple from 0-9 of that divisor has a unique digit in the 1's place; this means that you can do some pretty simple "backwards" long division.
Let's say we want to see if 63893 is divisible by 7 (I have no clue if it is yet):
63893-63=63830
63830-630=63200
63200-4200=59000 (which is clearly not divisible by 7)
May not be the easiest mental math method, but can reasonably be done quickly with pencil and paper; just scratch out the multiples of the divisor from 1-9 to the side and subtract whichever one matches the current rightmost non-zero digit.
I've been trying to find some unexpectedly juicy simple ones, but for the most part the juicy ones are pretty expected, like this one:
4999 is a prime and has the 'Justin' tests:
Take the 10,000s, multiply by 2, and add to the rest.
Multiply the units by 500 and add.
Very easy, but also it's so close to 5k you probably wouldn't have had trouble to begin with. Still though, it's quite juicy.
If you have a subtract test, you can easily convert it to the add test by subtracting the multiplier from the factor. For example. let's say you have the subtract test for 7 in mind. The multiplier is 2. 7 - 2 = 5. Now you have the multiplier for the add test for 7. This works because any number that is 2n above a multiple of 7 will also be 5n below another multiple of 7.
2:55 you can continue that process even further. You will go trough some 2 digit numbers to finally land on an actual 7
6:31 "If I care that it is divisible by 7, I don't care about any other factor. I could actually divide-out other factors and that won't change if it is or is not divisible by 7."
> That's only true as long as the factors you divide-out by are not multiples of 7.
Thanks Matthew, great video, helps a lot! :)
The easiest method is taking your base10 number 1000x3+100x2+10x1+x0 and taking 6x3+2x2+3x1+x0. As 1000mod7, 100mod7, 10mod7 is 6,2,3. Reduces extremely fast. Best method by far.
20:45 "I put some upper and lower bounds"
Matt, you're getting dangerously close to losing your terrible python code license.
Now that this is the 3rd video in the community series on dividing by 7. I fully expect a @mathologer video using complex math that i dont understand
Parker's lema, the means to find any divisibility rule
23:35 simplest prime test for code up to a large enough threshold is to just download a list of X million prime numbers and do a lookup
I remember looking at powers of 11 and realising it resembles the pascals triangle. After thinking about it for a while i realised its because you can write powers of 11 as (10 + 1) ^ n. Which is known to resemble the pascals triangle. I always imagined that the divisibility rules have a similar proof requiring the decomposition of numbers but this is a little easier.
Loving this video, enjoyed the Ding video and will remember the method better much better now I have the Why.
(I'm sticking with the Ding method because mutiply by 5 and add a multiple of 5 is the easiest)
14:52 Should be all right, everyone knows their 53 times table, don't they?
The way I see the 6720 check:
6720 / 20 = 336
336 = 350 - 14
350 & 14 are divisible by 7 ✅
"Is the distance to an obvious multiple of X also an obvious multiple of X" is one of my essential go-to's.
proud to be the patron for the divisibility test for 12497
Ooh, big fan of the 7 Parker test
I always check the divisibility by seven (or any other number) by comparing to big multiples close to the number.
So for example, I'd do:
2716-2100 = 616
700-616 = 84
84-70 = 14
14 is divisible by seven, so 2716 is too!
matt, its 3am and i need to sleep. why did you have to do this to me
Fermat's little theorem by grouping digits 1 less than the prime
*OMG* Amazingly, this approach also proves the Reimann hypothesis. Allow me to explain...
Oh shoot, this comment box is just a bit too small. I'll get back to you.
On the Second Method you used, with "Double the Last then Subtract it" If you End up with Zero, You actually don't confirm the Multiple. Lol, I'm just being a stickler, but you said if you did happen to end with Zero it would confirm it. Just a flubb though You are Brilliant
I physically recoiled at that regexp reveal
so many rules i might become a math outlaw or worse, a physics maniac
1:00 - Matt! You misspelled divisibility!
Is it nominative determinism that Matthew runs a math(s) channel?
You can kind of get the test with modular arithmetic
you need 10x+y to be equivallent to x+a*y in mod 7 if they're equivallent to 0
10x + y = 0 (mod 7) -> y = -10x = 4x (mod 7)
x + a*y = 0 (mod 7) -> x = -ay (mod 7)
substitute one equation on the other and you get x = 10a*x = -4a*x (mod 7)
so you just need to find a value of a such that -4a = 1 (mod 7)
the solutions are 5 and -2 (which are equivallent)
-4*-2 = 8 = 7+1
-4*5 = -20 = -21 + 1
If you're using python you can get the solution straight away by doing pow(10,-1,7)