Divisibility Tricks - Numberphile
Vložit
- čas přidán 16. 01. 2019
- Featuring Tony Padilla... Check out Brilliant (and get 20% off their premium service): brilliant.org/numberphile (sponsor)
More links & stuff in full description below ↓↓↓
Extra footage and trick from this interview: • Divisible by Seven (wo...
Card trick and shuffling videos on Numberphile: bit.ly/Cards_Shuffling
Belphegor's Prime: • The Most Evil Number (...
Numberphile playing cards (limited and occasional supply): bit.ly/NumberphileCards
I Love Norrie stickers (created just to annoy Tony): teespring.com//i-love-norrie-...
Tony is a professor at the University of Nottingham.
Numberphile is supported by the Mathematical Sciences Research Institute (MSRI): bit.ly/MSRINumberphile
We are also supported by Science Sandbox, a Simons Foundation initiative dedicated to engaging everyone with the process of science. www.simonsfoundation.org/outr...
And support from Math For America - www.mathforamerica.org/
NUMBERPHILE
Website: www.numberphile.com/
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Subscribe: bit.ly/Numberphile_Sub
Videos by Brady Haran
Patreon: / numberphile
Numberphile T-Shirts: teespring.com/stores/numberphile
Brady's videos subreddit: / bradyharan
Brady's latest videos across all channels: www.bradyharanblog.com/
Sign up for (occasional) emails: eepurl.com/YdjL9 - Věda a technologie
What I love about these tricks is that they aren't actually properties of the numbers themselves, but of their relationship to the base of notation. For instance, 3 and 9 can be tested for by checking the sum of digits because they both have a multiple that is one less than 10. If we were working in hexadecimal, this would work for 3, 5 or F (fifteen in decimal), but not for 9. In octal, it could test for multiples of seven.
This exactly! It generalises in any given notation, I was so excited when I found that out, and so sad when I realised that converting into a different notation is harder than long division...
Math is cool. And I’m glad you can see patterns like that. Amazing!
I like it! So you're saying that the easiest divisibility test for 7 is to convert the number to octal and then use the cross-sum 😎
@@stevieinselby It is if you are a computer.
If you're a computer, it's easier to just do a long division.
That 749 thing was funny and proves that the more advanced in your field you get, the more easy things seem hard
Yes; you’ll lose touch with the basics, and just over-complicate everything 😅.
In the divisibility rule for 11, you don't need to reverse the number before taking the alternating sum. It works just fine with the given order of digits.
As for the 7. I do not see why to reverse the order, absolute value of the alternating sum is the same.
yes going from the left should be the same as -1x going from the right and -1 multiplication means it keeps its divisors.
@@ruben307 It depends on if you have an odd or even number of digits. If its an even number, you'll get the negative but if its an even number of digits then the alternating sum will be the same. But either way, it doesn't make a difference to the divisibility.
A quick test for divisibility by 11: You don’t, of course, need to add and subtract alternately, remembering that addition is commutative. Add the digits in the even columns, call this x. Add the columns in the odd columns, call this y. If x-y is a multiple of 11, so is the original number. Simple example: 5346: x-y = (5+4) - (3+6) =. 0 = 11*0. And, in fact, 5436/11 = 486.
@@BarryMagrew
You can speed it up still further by dropping 11s as you go - 2596506 gives 2+9+5+6=11+5+6'='0+5+6=5+6=11'='0 and 5+6+0=11+0'='0+0=0 for the two sums; 0=0 so the original number is divisible by 11 (236046*11 in fact).
If you add up all the cards you get -1/12
Only if you have a REALLY full deck.
R/woosh?
@@josedanielherrera1552 r/notawoooosh
I still can't believe that.
@@AkhilSinghKhyalia You shouldn't believe it, because it isn't factual.
You can test if a number is divisible by 8 with a sligntly simpler method (it needs no multiplication)
1. you look at the 3 last digits
2.1 If the left digit is even, the 2 last digits must be a multiple of 8
2.2 If the left digit is odd, the 2 last digits must be a multiple of 4 but not a multiple of 8
sketch of proof:
200 is a multiple of 8, so every 3-digits multiple of 8 starting with an even digit can be written as 200n + 8m
100 is a multiple of 4 but not a multiple of 8. It means that it has an offset of 4 compared to a multiple of 8
So every 3-digits multiple of starting with an odd digit can be written as (200n + 100) + (8m + 4)
Nice. I noticed this, in slight, but i only recognized that 400 was a stable divisible factor rather than 200.
Thanks for helping me improve.
Dividing a 3-digit number by 2 isn’t too hard imo, then you can check if you get a multiple of 4 (or divide again and check the last digit)
I just see whether the last 2 digits are an even or odd multiple of 4
I thought of the same thing, though I worded 2.2 as "The last two digits must be two offset from a multiple of 8; ie, 62 & 66 are 64 ± 2."
I thought the same, but you can make 2.2 a little simpler still by saying it needs to be 4 away from a multiple of 8. (Not a big difference I grant, but its a slightly quicker process for my mind...)
I like how Tony was humble enough to admit that he lost sight of the "beauty of math". Sometimes we trip ourselves up when the answer is to just step back and go simple :)
19:48 Is 749 divisible by 7? That's a bit hard, beyond my mental arithmetic.
Nice to see fellow astro-particle physicists struggle as well.
It's easy if you understand 749 as 700+49, which is 7×(100+7).
@@DaniPhii 749 was easier for me than 56 :D
As 700 is definitely divisible by 7. Only need to work out if 49 is.
@@DaniPhii sorry didn't see your comment when i placed mine
@@j_vasey No problem!
I learned all these tricks by reading H.G. Wells, The Divisible Man.
Ah, that explains a lot! My copy came with a manufacturing error. The title was misspelled The Invisible Man and all the pages were blank...
@@zeikjt H.G. Wells wrote The Invisible Man, not The Divisible Man.
@@Falithlosar I know, the pages aren't really blank either, get it? :)
@@zeikjt That's just a Whirl of the Words...
@@Falithlosar woooosh
I actually learned this in school
same, but we were never told a reason for this property of multiples of 9.
@שחר א. No you are wrong.
I was never told the reason, but I knew 2, 3, 4 and 5 when I was 10 or 11. (Much) Later I understood 6 and 8. 9 and 7 and the rest was completely new.
The teacher told us that there is no rule for 7. Then I told him a rule. Why does he say that there is no rule? Why doesn't he say that there is one, it's just a little complicated, so we don't bother studying it?
@@gabor6259 Because he doesn't know the rule, or, like you say, it's way too complicated.
I didn't know the rule for 7.
Love the energy in this guy, you can tell he's loving his job!
If this guy has energy, then Mr. Klein...
@@gabor6259 …has hypernergy.
Someone in the comments probably brought it up already, but there is an alternate test for 11: You remove the last digit and subtract it from the remaining number (similar to the second test for 7, but without doubling the last digit). If the result is divisible by 11, then the original number is, as well.
For example: 121 -> 12 - 1 = 11
If you encounter larger numbers, you can just continue this process multiple times:
72,435 -> 7,243 - 5 = 7,238 -> 723 - 8 = 715 -> 71 - 5 = 66
There is yet another way, which is basically just a different method of taking the alternating cross sum shown in the video, but I find this method easier to do in my head:
You subtract the first digit from the second, then subtract the result from the next digit, and so on, and then check the result:
96,410,985 -> 6 - 9 = -3 -> 4 - (-3) = 7 -> 1 - 7 = -6 -> 0 - (-6) = 6 -> 9 - 6 = 3 -> 8 - 3 = 5 -> 5 - 5 = 0
This also works in reverse by subtracting the second to last digit from the last and continuing towards the left:
96,410,985 -> 8 - 5 = 3 -> 9 - 3 = 6 -> 0 - 6 = -6 -> 1 - (-6) = 7 -> 4 - 7 = -3 -> 6 - (-3) = 9 -> 9 - 9 = 0
With some practice, this can make checking whether large numbers are divisible by 11 almost trivial... as long as you can see the number, that is.
My way for checking most annoying primes is to subtract multiples of the prime until it is easy. For example, with the 7 case: 872123. I subtract 840000, which is 12x7x10000. Once left with 32123 I subtract 28000, then I have 4123, I subtract 4200, then I have 77 and that is obviously divisible by 7
I love how Mo Salah popped up in his thought bubble when he was thinking about dividing by 11, because of course he wears the #11 shirt.
27 mins of Numberphile. Yes. Yes. Yes!
+
3^3
Is this a jojo reference
Hiiiiiiiiii!!!!!!
Weird Al strikes again!
I first discovered the pattern in the 9's when I was in first grade, and I remember thinking that I had discovered something truly amazing. Later I learned that it was already known - by most people even.
I wouldn't again feel that bittersweet feeling of a major revelation that had already become commonplace until 9th grade.
This has proved to be one of those times where watching a video on something I already knew has never the less proved valuable. Somehow, in my math education, the idea that a proof tells you *how* a thing works never stuck, if it was ever mentioned at all. Thanks, folks!
I'm not great at maths, but I knew 464 was divisible by 8 bc it's 400 and 64 which are both easily recognisable as being divisible by 8.
Yeah. 200, 400f, 600, and 800 are all divisible by 8 so you just have to worry about the last two if it's even. I think they should have mentioned you only have to do that extra work if it's it's in the 100, 300, 500, 700, or 900.
@@kranklg2s Actually, I think a much simpler trick is (after the even hundreds, which you explained), for the uneven hundreds, you'll get your answer by taking the last two digits + 4 and test if they are divisible by 8. So, 384164, you check by (64 + 4) / 8, so it is not div. by 8. Likewise, 859776, check by (76 + 4) / 8, so that is devisable.
I like to think that that is much easier than the rather complex trick in the video, because all you ever deal with is a two-digit number to find the divisor of 8.
@@Misteribel Yeah, you're right. I wasn't thinking about that when I commented - I was more focused on excluding the other half - but I read a comment about that further down later and facepalmed a bit ^^
- Slinger - One thing to know... 100 is not divisible by 8.
And that's how you simplify something like that. Remembering also that 1,000 is divisible by 8, all you need at that point is the last three digits.
26:23 Primes squared: 4,9,25,49,121,169
But can a grid of 10x10 squares be filled with 25 1x4 pieces? My gut says no, but I haven't actually tested it.
@@Pr1est0fDoom yeah you can't
But can you prove that?
@@gcewing it's proof by induction. try it
I'm late for the 10x10 grid but the simplest proof I can think of involves a 5x5 checkerboard. I'll leave y'all thinking now
22:58 nice
Gotta love the way he says it
nice
nice
25:16
The divisible by 7 test can be heavily streamlined
The number given is: 872,123
You can take out consecutive digits that are multiples of 7 and replace them with 0s
7 can be replaced with 0
> 802,123
21 can be replaced with 0
>800,023
Now the test has easier numbers.
the test would now be 23 - 800
Also when subtracting your numbers just swap so the bigger number to the left as of course most people find 800 - 23 a lot easier than 23 - 800
using this method makes it a lot easier to do this trick in your head and impress your fellow nerds
Yes. In that case, the result is very easy: -777/7 = -111. Yes, 802 123 is, indeed, divisible by 7.
Check out Brilliant: brilliant.org/numberphile (sponsor)
Extra footage and trick from this interview: czcams.com/video/ZWeUNUCf2rI/video.html
Card videos on Numberphile: bit.ly/Cards_Shuffling
Numberphile playing cards (limited and occasional supply): bit.ly/NumberphileCards
I Love Norrie stickers (these are designed to annoy Tony): teespring.com/en-GB/i-love-norrie-numberphile
1st reply
For the divisibility of 8 why can't we do what we did for 6 I mean if it's divisibile by 4 & 2 it should be divisibile by 8 right?
@@sahasananth987 Not quite. Imagine the number 4, it's divisible by four and 2, but not eight. The trick with the 2&3 is that 2&3 don't divide each other. Another example 12 is divided by 4&2 but not 8.
By the way, the 7s test is amazing. It can be used for 11s test and 13s test.
That means this method can be used in divisibility tests for 7, 11, 13, 77, 91, 143 and 1001.
This was by far my most favourite divisibility test. 😄
Also, the 27s test is like the 7s test, except you add up the groups of 3, instead of alternatively adding and subtracting them...
@@sahasananth987 It does not work like that.
For eg. 100 is divisible by 2 and 4, but that doesn't mean that it is divisible by 8.
so in base 13 then the cross-sum rule would apply with 2,3,4 and 6!
and 14, but you'd have to do the alternating cross-sum for that one.
I don't know if the cross sum rule applies to 720 :^)
Also works for 1 (as in base 10), though that information isn't helpful, the same proof applies.
also: in base 21 you get easy cross-sum rules for divisibility check by 2,3,5,11 on top of the fact that this base already has an easy way to check for divisibility by 3 & 7 from itself (because 21 = 3 * 7) so you can check against the first five primes (& their products) really easy: 2,3,5,7,11
If you want to check for the first six primes 2,3,5,7,11,13 easily (& also 19 & their combinations) one need numbers in base 209
@@FrankHarwald base 6 has easy tests (and radix numbers) for 2, 3, 5, and 7.
I have the same gift as Norrie except I can tell if something is a multiple of 2.
I have that, for multiples of 1 😎.
Get Norrie on this channel or I RIOT!
I'll make some calls.
@@numberphile Excellent. No one wants a one-man riot on their hands.
@@KevinVanOrd A riot has a statutory minimum of 12 participants and a common-law minimum of three participants, I'm afraid. You could still _incite_ a riot, of course.
Norrie stickers available... teespring.com/en-GB/i-love-norrie-numberphile
@@Tevildo it takes 7 to cause a riot.
With 3 and 9 it’s not just divisibility but also the sum of the digits has the same remainder divided by 3 or 9 as the original number (i.e. the sum of the digits equals the original number modulo 3 or 9). So 527 for example has sum of digits 14. 14 has remainder 5 divided by 9 so 527 is also remainder 5 divided by 9. Likewise 14 divided by 3 and 527 divided by 3 both have remainder 2. Divisibility is simply the special case where the remainder is zero.
Also to simplify the remainder calculation you can cast out digits which sum to 3 or 9 for whichever test you are doing. Again, 527 has 7+2 in the digits so you can ignore those in the test since they have remainder 0 divided by 9 and 3. Thus 527 equals 5 mod 9 = 5 and it equals 5 mod 3 = 2
This is true, but the proof is less direct. The proof given is that when the sum is divisible by 3/9, the number is also divisible by 3/9.
@@andymcl92 All the proofs of this video would be easier using reminders/modulos
andymcl92 The modular arithmetic proof is simple. 10 = 1 mod 3 or 9. So 10 to any power is also 1 mod 3 or 9. Thus a * 10^k = a * 1 = a mod 3 or 9 . So a number mod 3 or 9 is thus the sum of its digits mod 3 or 9.
P.S. This is also the reason for the alternating +/- sum when looking at divisibility by 11. 10 = -1 mod 11, so a*10^k = a * -1^k mod 11, so a number mod 11 is just the sum of its digits with signs alternating.
Olivier Massicot Yeah, if they could give a quick summary of mods or direct to a video that does, they could easily make so many of these proofs shorter and more digestible.
Thank you. What fun! Have been fascinated with these "divisibility rules" since I was young, yet I could never remember the 7 and 11 ones for long after I learned them.
For divisibility by any number n, you can also simply check the sum
sum a_i * (10^i mod n)
for divisibility by n (or calculate it in mod n directly). The (10^i mod n) is independent of the number used, so you can derive the divisibility trick.
E.g. for divisibility by 7, you'd need to remember: 1,3,2,6,4,5,1,3,2,6,4,5... repeating. So to check 6976984 for divisibility by 7 you'd do:
6*1 + 8*3 + 9*2 + 6*6 + 7*4 + 9*5 + 4*1 mod 7
= 6 + 3 + 4 + 1 + 0 + 3 + 4 mod 7
= 0 mod 7
Not really useful, but it recreates the tricks for all the other numbers too.
This is the best numberphile ever! I can make people think I can see factors of huge numbers now. Incredible. I needed this in calculus
The cross sum trick for 3 and 9 is one of the first things we learn about divisibility. You didn't think of it on the huge prime check because it was so simple.
True 😅.
For once, Numberphile goes over a concept I was already familiar with! :D
now apply it to polynomials ...
Same
a neat thing about the proof for the 7’s trick: not only is 142857 related to cyclic numbers, but it is also the repeated decimal expansion of 1/7, which is related to the proof that 0.999999… = 1
This is why I love math. I swear sometimes I see more when I learn things like this. I feel like I acquire a diluted version Norrie's skill. I need more.
I said before I need to watch all the numberphile videos from first video to recent video, I hope I follow through sometime soon.
Those tricks are cool, but divide by zero then I’ll be impressed
f(x) = 1/x = y
f(x) lim x->0 = y->±oo
Now where's my cookie?
Defining n/0 = infinity, -n/0 = -infinity, and leaving 0/0 undefined is the natural thing to do.
@@cyclingcycles7953 that's literally *not* a division by zero.
@@dank3k Well that's technically the closest you can get. Can I at least have x where x approaches a cookie?
@@EpicMathTime 0/0 can be any number you like, it just depends on how fast you tend to it. (ksin(x)/x=k for x=0)
Divisibility by 37 :
Separate the number in blocks of 3 like for 7. On the left of each block, write the left digit one more time, then separate this block of now 4 in two blocks of 2.
Do the alternating sum of all blocks of 2.
If the final result is divisible by 37, so was the original number.
6,203,346
006 203 346
0006 2203 3346
00-06+22-03+33-46 = 0*37
=> 37 | 6,203,346.
Also note that if a 3k digit number is divisible by 37, all its circular permutations are also.
The more you know.
Cool 😎👍🏻!
Also: Take a regular calculator keyboard (- the 0-key). Type out the digits in any row, column, or diagonal, in either order, and then, in the other order. There are 16 numbers you can obtain, this way; and they’re all divisible by 37. For example:
123 321 / 37 = 3333
741 147 / 37 = 20 031;
and so on. This is slightly related to your 3k-digit-numbers and all their circular (or cyclic) permutations being divisible by 37.
Thank you for the video! All of you friends are super awesome!
I love how making it a card trick makes it more attractive than writing it on paper... - it immediately looks like magic, just because it involves you and you can touch it: it’s no longer just about playing with numbers, but playing with you - the curiosity shoots up.
I think you can actually generalize the tests for evenness, divisibility by 4, divisibility by 8, and so on. For any potential divisor 2^N, you only need to determine if the number formed by the last N digits is divisible by that divisor. So you'd need to look at 4 digits to test for divisibility by 16, 5 digits to test for divisibility by 32, etc.
Yep. I’m pretty sure of that, too; because 10 (= 10^1) has exactly 1 factor of 2
(= 2^1), 10^n has a factor of 2^n; and the rest is explained, in the video 🤔.
I have never inverted the numbers when checking divisibility by 11 and it has always worked well.
Yeah, that part of it seemed pretty pointless.
The reason they invert is that need to compensate for starting from the left. If you start from the right and go left, you need no inversion and concern for number of digits.
@@bpark10001 You don't need to compensate though if you just care about divisibility.
I noticed a slide rule on the desk - Great! Another already forgotten “trick”. I had been missing mine for years, but recently bought a new one myself. Happy days are here again...
The 11's trick doesn't need to reverse order (the only difference is a possible sign change), making it a little easier to do in your head. Also, the first part of the 7's trick also works for 11's and 13's. Also, when you said the two facts you need are that 1001=7*11*13, and the second fact is that 999,999 is divisible by 7, the second fact actually follows from the first since 999,999=1001*999.
For divisibility by 8, I'd just halve the last 3 digits and check if that's divisible by 4 (check last 2 digits).
I learned a bunch of divisibility tests in elementary school and they haven't been mentioned anywhere since. Crazy to think if not for then I wouldn't even know of any until now
The version of the trick you showed for divisibility by 7, also works for 11 and for 13!! That is, the first step, where you alternately add/sub 3-digit groups.
Because it boils down to the "1001" trick - which you sort of allude to later along.
That 3-digit +&- (repeated enough to get down to a 3-digit result) ends with a 3-digit number that preserves divisibility by 7, 11 and 13, because it amounts to subtracting multiples of
1001 = 7·11·13.
Fred
I've been having quite a lack of Numberphile for the past 4 weeks so this was nice :D
One of the best videos in a while on this channel! That 749 was funny though.
I tend to like t - nq instead (where n = [Divisibility number] - m), so the number I have to divide by is smaller.
Example: Instead of 103 + 7(5 464 + 13(4) = 516 which is 43 * 12. But you could just as easily use 4644 -> 464 - 30(4) = 344, which is 43 * 8. I can't really remember two-digit multiplications of two-digit numbers, but I could intuitively recognise that 344 is smaller than 430 by 86, so it's an advantage in my case. (It's also easier to multiply by 30 than it is by 13.)
I always love a Dr.Padilla video!
That Proof Flew straight over my head so quickly, I honestly felt like I was spinning!!! Made exactly 0.00 since to me... I do enjoy knowing that this little trick is possible though! Thank you for that at least.
There's a fairly straight forward way to derive these rules using remainders of dividing powers of ten. So 10^n mod 7 gives us {1, 3, 2, -1, -3, -2, 1, 3, 2, ...}. The alternating signs tell us that we can take these in blocks of 3 and do alternating sum. But further, for a 3-digit number, 100*a_2 + 10*a_1 + a_0, it's clear that it's divisible by 7 if a_0 + 3*a_1 + 2*a_2 is. Which, to me, is a simpler test, but your mileage may vary. For 11, same pattern of remainders is {1, -1, 1, -1...}, so we have a simple alternating sum. And for 3 and 9 it's {1, 1, 1, ...}, so that's the simplest case. In general, for any N not multiple of 2 or 5, this will produce a pattern at most (N-1) elements long, which might include some creative sign alterations, and can then be massaged into a practical rule.
So if you want a harder one, lets do 13. The remainders are {1, -3, -4, -1, 3, 4, 1, -3, ...}. This one happens to repeat in just 6 elements instead of maximum possible 12, which is fortunate. Also, there is a pattern with signs creating groups of 3, but it's shifted by 1 from beginning. So taking a number like 847,559,388 the way you'd test it is by making groups of 3, but padding one's place with zeroes: 84 755 938 800. And do an alternating sum (right to left or left to right doesn't actually mater for any of these, since negative of a number has same divisors.) 800 - 938 + 755 - 84 = 533. So the whole number is divisible by 13 if 533 is. And again, {1, -3, -4} portion of the pattern can be used to test 3 digit numbers. 3 - 3*3 - 4*5 = -26, which is clearly divisible by 13. So the number was, in fact, divisible by 13. Overall, not any harder than test by 7, even if the rule itself looks stranger.
this is great
There's a generalization you can do about divisibility by 2, 4 and 8 - number is divisible by 2^n if last n digits of a number are divisible by 2^n. Not quite useful on higher n values but still it is a valid rule that I think should've been mentioned.
Also, second method of divisibility by 7 that Tony explains is appliable not to just 3 digit numbers but to any amount of digit numbers, and what's more interesting - it's recursive. Let's take that 6976984 as example: 6976984 -> 697698 - 2*4 = 697690, 697690 -> 69769 - 2*0 = 69769, 69769 -> 6976 - 2*9 = 6958, 6958 -> 695 - 2*8 = 679, 679 -> 67 - 2*9 = 49, 49 is divisible by 7, therefore 6976984 is divisible by 7. I find this one to be easier doing mental arithmetic than 'blocks by 3' one, because you only really need to keep track of one number and make simple operations of doubling and subtracting.
Thanks a lot :(
I had my brother calculate if a number is divisible by 8 with your method and now he is stuck in a loop.
Not to mention that the 7 test can be extended to any number relatively prime to 10, if you understand how it works.
Basically, imagine starting with a number we’ll express generally as abcdefg, or as x for short; taking the last digit results in abcdef, which you can get by subtracting g (abcdef0), and then dividing by 10, so the result is (x-g)/10. Subtract twice the removed digit and the result is (x-g)/10 - 2g, or (x-g)/10 - 20g/10, or (x-21g)/10.
As you can see, since 21g is 7*3g, subtracting it from x doesn’t affect if it’s divisible by 7; similarly, since 10 is relatively prime to 7, dividing by it also doesn’t affect that divisibility. As such, if this result is divisible by 7, so is the original number. Repeat until it’s easy to figure the divisibility out by hand.
This can easily be extended to other numbers by finding multiples of them that end in 1. For example, 7*13 is 91, so you can test something for divisibility by 13 by removing the last digit and subtracting 9 times the removed digit; repeat until you can figure it out by hand.
This also can work for numbers that end in 9, by adding the removed digit instead of subtracting. For example, 3*13 is 39; working the old logic backwards, (x+39g)/10=(x-g)/10 + 40g/10, which is (x-g)/10 + 4g. As such, we can also test a number for divisibility by 13 by removing the last digit and adding 4 times that to the remaining number.
Ahh, the moment when you downloaded the C. C. Briggs first 1,000 divisibility rules for primes two months before the actual Numberphile video and know exactly what they're talking about even before they begin
9 is the largest single digit in Base 10, and 3 is a factor of 9, so that all makes sense.
Given the proof for cross sums, It would appear that the same thing should work for other number bases. For example: that you can do a cross sum to check for divisibility of the number 5 in Base 6, or the number 12 in Base 13. And if it works for 12, it should also work for 2 or 3 or 4 in base 13.
A quick check of my programming calculator, and the cross sums divisibility check works for 7 in octal, and 3 and 5 and 15 in hexadecimal.
This is the first time I've seen the 7 trick. I have seen more than one book in which the author states there is no divisibility test for 7.
in most cases it's easier to to check divisibility for 7 by dividing
Actually every number has a divisibility test.
There is no divisibility test using just the last two digits, which means you still have to memorize or compute reasonably large multiples of 7.
@@@EebstertheGreat Or you use the 3-digit test he gave in the video.
as it gets longer and longer it just comes to what you consider to count as a test that you're going to try and do in your head, if you're in practice only going to put it in a calculator then you might as well just divide by 7.
4:54 There's only one explanation for missing something that obvious - he must've had a Parker thought XD
The Padilla test for divisibility by n: Show the number to Tony Padilla. If he can't tell at a glance, then it obviously is.
I've been using these to trick people for years, but I never tried to prove it. It's just something I intrinsically understood.
This is magic ASMR which puts me to sleep. Not because it's boring, but because it's really interesting. My overworked brain shuts up so it can listen.
At 11:43
Isn't it easier if you just do 46 + 4/2 = 48 and check if 48 is a multiple of four? The way he does in the video implies a multiplication and a final check of divisibility by 8, which is much more demanding than a sum and check of divisibility by 4. You can simplify the whole thing just by dividing everything by two
Yes, that is, indeed, easier; by quite a lot, I would argue.
Still waiting for a follow up to the Feigenbaum Constant video...
Thank you for these conversations
Fun carnival tricks, but you can imagine that these methods may have been pretty important before we all walked around with small supercomputers in our pockets.
With regard to that featured brilliant question, there are exactly six numbers less than 200 that have exactly three divisors. The solution for this one is simple: it is the set of the squares of prime numbers p such that p^2 < 200:
2^2 = 4
2x3 = 6 < Not in our set because 6 has 4 divisors, so we must ignore composite numbers that are not squares
3^2 = 9
4^2 = 16 < Not in our set because 16 has 5 divisors, so we must ignore squares of composite numbers
5^2 = 25
7^2 = 49
11^2 = 121
13^2 = 169
17^2 = 289 < Not in our set because 289 is obviously greater than 200, therefore it does not count
And thus we have reached the end of the solution algorithm. Six numbers less than 200 with exactly three divisors. The rationale for this is that for a number n to have exactly three divisors, its prime factorization MUST be p^2 such that p is prime. Thus, the only three divisors of n will be 1, p, and n, and nothing else.
And a quick proof by exhaustion:
1) If n is of the form q^2 for some composite number q, even if q is of a form p^2, then n will have more than one divisor, specifically: 1, p, q, pq (or p^3), and n. Five divisors, not three.
2) But if q is of a form ab such that a
An easier check for the 3 digit number for 8s would be if the hundreds digit is even just check the last 2, if the hundreds is odd, subtract 4 from the last 2 and then check it
These tests extend to all prime numbers. 2,3,5,7,11 were covered explicitly, and numbers ending in 1,3,7,9 are covered generally. This general set includes every prime number greater than 5.
A 27 min numberphile video? I've been blessed.
Sounds as though Norrie has synesthesia, an overlapping of senses
That our hallucinations xD
I’d say some form of autism.
For multiples of 8, can you take the last 3 digits, divide them by two, and then do the check for 4; if that number is divisible by 4, then original is divisible by 8?
Pel Thain
If the last two digits make a number divisible by 4 but not 8, and the number before that is odd, or if the last two digits are divisible by 8 and the number before is even, the whole number is divisible by 8.
I think if the 'hundredth' digit is an even, then we can only check if its divisible by 4. If its not, then do the 8's check as they show in the video.
Asad Zaidi
No, if the hundreds is odd the last two digits have to be divisible by 4 but NOT by 8, whereas if the 100s digit is even the last two digits have to be divisible by 8.
Yes.
Here's an easy trick I use on checking if a number is divisible by 8. If the hundreds place digit is even and the last two numbers are divisible by 8, then the number is divisible by 8. If the hundreds digit is odd, then if the last two digits plus 4 is divisible by 8, then the number is divisible by 8. Thanks for making awesome videos!
i'm just... in love with this video
749 divisible by 7 - "it's hard, beyond my mental arithmetic"
Me: bro it's just 700 and 49. That's cake lol
For divisibility test you don't need to reverse the digit just take sum of digits at odd places and subtract it from sum of digits at even places...if it is a multiple of 11 the number is multiple of 11.... There is no need of reversing 🙃
I always had a fascination about numbers. When I was 10-11, there was a weekly math competition organized by the teacher to help us learn and gain speed, especially for multiplication and division. That's how I figured out the divisibility tricks up to 10 and their compounds, except for 7
I love these videos. They are fun and educational.
You shuffled the cards in the graphic. The cards displayed are 42135 and the graphic is 42315
Yes. This changed the answer from the correct 5 to a 9.
Who cares...
@@brokenwave6125 **Literally** everyone here. How these divisibility tricks work is the entire point of this video.
Not sure if this is covered already in the Numberphile, but this is essentially the concept of congruence.
10 = 1 (mod 3)
10 = 1 (mod 9)
10 = 2 (mod 4)
10 = 2 (mod 8)
10 = -1 (mod 11)
10 = 3 (mod 7) or 1/10 = -2 (mod 7) & 1000 = -1 (mod 7*11*13)
And
1/10 = 7 (mod 23)
Norr7e you legend! Great video thanks for sharing with us!
The last trick is the best! U rock as always!
For the 8 test isn't it easier to check if half the number is divisible by 4 ?
Half a big number (lots of digits) is a bit of a grind.
@@ubertoaster99 You can just half the last 3 digits to get the last 2 from its half
@@Noukkis that's what I do, and it seems simpler to me than the method shown here...
@@Noukkis True. I still think I'd rather skip halving it at all though. You can see if a three-digit number divides by 8 without too much trouble. It'll be some figure on the eight times table away from 80, 160, 240, 320, 400 etc. That's why 464 is easy... 400 + 64.
Really what you do is: take the last 3 digits and then modulo 200. Meaning, if the 3 digit number is 949, make it 149. This is because 200 is a multiple of 8, so the only reason you need the hundreds digit in at all is to know whether it's even or odd.
I do /3 on licence plates while driving all the time
Are you my brother? I check divisibility by 9.
There is a bit simpler rule (at least for mental calculations) for divisibility by 8. Start with the last 3 numbers just as shown if the first of those is odd, then add or or subtract (whichever is easier) 4 from the last 2 digits
Now if the last 2 digits are divisible by 8, then the number is divisible by 8. I’ll give a few examples:
Using the example in the video, last 3 digits are 464. The first digit is even, so just check if the last 2 are divisible by 8. Which they are, so it’s divisible by 8.
Xxx,324. First digit of last 3 is odd, so add (or subtract) 4 from 24 to get 28 (or 20). 28 (or 20) is not divisible by 8 so the number is not divisible by 8.
1536, first digit of last 3 is odd, so add or subtract 4 to get 40 or 32. 40 (32) is divisible by 8 so the number is divisible by 8.
It does not matter whether you add 4 or subtract 4, just whichever is easier for you using those numbers. For instance, if the last two digits are 28, it may be easier for you to subtract 4 than to add 4.
a nice thing about the cross sum that's divisible by 9, you can keep taking the cross sum until you get a single digit number, and it will be 9.
The 7's second divisibility rule can be made for all primeslarger than 3 : take a prime (say 23), multiply with some number to get the last digit to be 1 (23*7=161). The rule is to subtract the number of this product without the last digit (16) times the last digit of the number under consideration from the number formed by the rest of the digits of that number. This process can be continued indefinitely: if the number obtained is divisible by the prime, so is the original one.
As an example: 2323->232-16*3=184->18-64=-46 and 23|-46 so 23|2323.
Actually, sometimes it is easier to use another very similar rule: instead of subtracting 16*last digit, one can add (23-16)=7 (that is -16(mod 23)) times the last digit and this rule works as well.
As one more example, let's generate a rule for dividing by 37. 37*3=111 so -11 is one fitting number and 37-11=26 is the other. Check 3959=107*37. With -9: 3959->296->-37. With 26: 3959->629->296 and 37|-37 and 37|296.
To complete your method, you have to considere primes that have a multiple ending with a 9 instead of a 1 sooner that it has a multiple ending with 1 (basically primes ending with a 9). In that case you dont subtract the number, but you ADD it, using your same approach.
Ex: Divisibility by 19. With your method, 19*9 to have a 1. But 19*1 to have a 9. So adding is a slightly easier method. We also need to increment that multiple by one.
Let's try with 8664 / 19. 19*1 = 19, ends with 9, so it's going to be an addition. We used a factor by 1. We need to increment by 1 (you dont need that with subtraction). So the last digit factor is going to be 2. The last digit is 4, so 2*4 = 8. 866 + 8=874. 87 + 8 = 95. 95 is 19*5. 8664 is divisible by 19.
+Martin This method is almost the same as the method starting around 23:00, where the video choses a positive inverse of 10 modulo 23:
70 = 23*3 + 1
7 * 10 ≡ 1 (mod 23)
And you chose a negative but equivalent inverse of 10 modulo 23:
160 = 23 * 7 - 1
(-16) * 10 ≡ 1 (mod 23)
+Martin The video mentions that this method is also applicable to all numbers N ending with 1, 3, 7, 9, i.e. those N coprime with 10. Because 10 has a multiplicative inverse modulo N.
I prefer doubling the last digit then subtracting from the rest of the number for divisibility by 7. Rinse and repeat until you get down to 2-3 digits
That divisibility rule for 3 and 9 ultimately stems from the fact that we use base-10 numbers. There is a corresponding "divisibility by base-1" rule for every system; e.g. divisibility by15 in the hexadecimal system or by 7 in the octal scheme.
What's interesting is that, once you think about it, it makes sense that this also works in all other bases. So in hexadecimal, if a number's cross sum is divisible by [f (15), 3, or 5], the number is divisible by [f, 3, or 5].
Let's call multiples of 3 "threeven" from now on.
In high school I did a math contest that did exactly that! And 3k+1 were "oddup" and 3k-1 were "odddown"
@@Gold161803 I was calling them "long", "short", and "threeven", but I like "oddup" and "odddown" better. And all primes but 3 can be divided into "oddup" and "odddown" primes.
Principia 🙏
Finally, my dream numberphile video!!
I love a man that easily admits and, even better, learns from a mistake. Nice 😃
749 = 700+49 (both divisible by 7, thus the whole number is also a multiple of 7).
yep I dunno how he struggled with that
Same with the 464 .. 400 is divisible by 8, so is 64. Done. Both them (and you) missed that one it seems.
@@fatsquirrel75 suppose so
I think he was just doing his script of this number is to hard to divide in my or your head so we have to use the trick I am here to show you.
@@joryjones6808 not for some of us.. As he said, though, different ppl have different strengths.
Well I knew the first trick when I was 6.
One of my fave videos of yours
I'm currently studying for the ARML competition. Even if you can't do it in your mentally, these tricks are still so helpful.
I was shown these tricks in elementary school. Are these not common knowledge elsewhere or have you dang kids just been using calculators so much that no one uses them anymore?
I learnt them as well but just 2-10 (except 7) but I never knew the proofs
I learned it when I was 9 years old, 3rd grade.
And the proofs? Wow.
@@numberphile without the proofs. I think. But the rules were elementary.
I learned that in 6th grade. Are you from Romania, Calin?
im not trying to be an asshole, just adding a data point: Yeah, the proofs were in my high school textbook.
@@gabor6259 yes
5:52, and you can even add the 1 and 5 in 15 to make a 6 which is divisible by 3 to make the multiplication in your head simpler. I just think it’s astonishing.
Great video! I have an bit of a nicer proof for the 3 and 9 rule.
1. The cross sum of any number N will be 1 more than the cross sum of N -1 or will be 1
2. With this, you can picture a circle of numbers from 1 to 9, and each consecutive number takes on step around the circle.
3. Since there are 9 numbers on the circle, taking 9 steps around brings you right back to where you started, and taking 3 steps at a time will have you always land on the same 3 spots.
4. This means this trick works for different numbers in different bases! In base B, this trick works for B-1. Base 8 would mean that any number whose cross sum is 7 is divisible by 7. In base 13, this trick would work for 2,3,4,6, and 12!
7:54 (Pontifically): “Let it henceforth be known that the term ‘whole bunch of’ shall be defined as exactly, with no more and no less, equal to n-1 ! Well... Whatever n is...”
Why is there calendar for 2012 on the wall?
Maybe he has a massive backlog of videos?
Because he's posting videos via an inter-dimensional portal.
I'm confused about what you're referring to. I can see two calendars. The Liverpool FC one slightly behind him is hard to read but looks to be a 2019 one. From the pattern on the first month it definitely seems to be a 'Tuesday regular' calendar anyway [though admittedly you can't tell 'regular's from 'leap's in January], as you'd expect for 2019 (whereas 2012 was a 'Sunday leap'). The other calendar is the light blue one with a hand painted butterfly on, which is clearly kept for it's sentimental value, because his child (or nibling etc) drew it, but the print on the calendar bit at the bottom doesn't seem to come into full focus at any point, so not sure what year that one was (I didn't rewatch an entire half hour video again to check it out, but a quick glance at the points where the wall comes into shot, as far as I can tell from hovering over the scroll bar at the bottom and moving along, suggests it didn't anyway).
I only saw the calendar in the top right 25:05
@@Jako1987 Oh fair enough. I never even noticed that one! Looking at about 16:35 it looks like there are child's drawings (or handprints?) on that one, so it's presumably the same explanation as the blue one I mentioned.
I learned this whilst I was studying to take the GMAT. Fascinating stuff, especially 7 and 11.
You don't have to reverse the 11 one, hope this helps
One of my favourite tricks is to ask people to factor 899. For reference, it factors into 29 x 31. That is, of course, a ridiculous ask, unless you realise that 899 can be expressed as 900-1. And both 900 and 1 are perfect squares. Factor the difference of squares to get:
899
= 900 - 1
= (30 + 1)(30 - 1)
= 29 * 31