CORRECTION: When referring to digit rules where the digits need to "add to 0" to be a multiple of 3, or "add to 0" to be a multiple of 5, the digits could also just add to a multiple of those respective numbers, 3 and 5, and it would still indicate divisibility. In the case of 3 for example, the digits alternating sum doesn't necessarily have to be 0, but needs to be 0 (mod 3), which means whatever the sum is should be divisible by 3, just like with the rule discussed for 7. Also, yes 0 is divisible by 0. I would have included the definition of divisibility in this video (which has nothing in particular to do with 0/0), but that seemed like a big waste of time to clarify a point for a single number which isn't interesting in this discussion. To say 0 is divisible by 0 means there exists an integer k so 0*k is 0.
@@WrathofMath No, 0/0 isn’t 0, it’s indefinite, just like every other division by zero. Take your example 0 * k = 0, now apply your “0/0=0” logic to divide both sides by 0. (0*K)/0 = k and 0/0 = 0, ergo, k=0 implies that any number k =0. That’s why division by 0 is indefinite, for all values of k. There are a variety of situations in which you can show the limit is 0, 1, infinity, or various values, ergo, there is no universally defined value. You can explicitly define it to be a specific value based on the limit, for the purposes of treating a specific subset of functions as continuous over a range that includes 0.
@@WrathofMathusing that definition of divisibility, there exists an integer k for arbitrary n such that n*k = 0, implying that every number is divisible by zero? edit: it seems I have misunderstood n is the number you are dividing by, so I have actually just said 0 is divisible by any number
@@user-pr6ed3ri2k Not quite. A number p is divisible by q (written as q|p or "q divides p") if and only if there is some number k such that qk=p. This is the same as saying that p is a multiple of q. You noticed that every number n has a k=0 such that 0n=0. This doesn't mean that 0 divides n, it means n divides 0 (n|0 for any number n). This makes sense as 0 is the 0'th multiple of every number.
For 7, you could also convert to base 8 and do a non-alternating sum of the digits. If the result is divisible by 7, then so is the original. It's the same as how divisibility by 9 works in base 10 since 7 is 1 less than 8.
Note also that this gives an alternative strategy for divisibility by 3. Since 3 is 1 less than 4, convert to base 4 and do the non-alternating sum. Of course that rule applies also to 2-1=1, except that the fact that a binary number is divisible by 1 exactly if the sum of its digits is divisible by 1 is pretty useless (but still true).
That's kinda equivalent to what bro does already. The 1 2 4 thing is equivalent to grouping the bits in 3 as base 8 & summing them all up to see if it's divisible by 7
Also note that since 4 is equivalent to -3 mod 7, you could also use bit factors of 1, 2, -3, ... . This will tend to keep the running total with a smaller absolute value, and clearly shows how adding all three together results in a multiple of 7 due to the remainders canceling out.
Zero is by definition divisible by 0, that doesn't mean 0/0 is defined. But there exists an integer k so that 0*k=0, thus satisfying the definition of divisibility.
Not sure why 7 got its own section when it's strictly easier than divisibility by 9 (at least to me since I consider non-alternating sums easier than alternating sums). If 9 was simple enough to blaze through, 7 should be as well.
Divisibility rule for 1011 (eleven): Take your binary number and split it into groups of 5, then take the alternating sum of these numbers. This works because 2^5 + 1 = 3 * 11
Yes! This is as insightful a remark as the whole rest of the video. It opens up a whole class of divisibility rules base 2: namely for all the divisors of one less than any power of 2.
@@applimu7992 Same approach for 13, as 13*5 = 65, so use groups of 6 bits (aka base 64). 17*15 is 255, or one less than 2^8. 19*27=513… Starts to get unhelpful at that point
So, something completely random that occurred to me. Using only binary numbers, written in binary form, for any number, from 1 to n, what is the _smallest_ number that is divisible by any number, n, that contains "n" 1s with any 0s? Well, for the first 6 numbers, these are: 1 = 1 2 = 6 (110) 3 = 21 (10101) 4 = 60 (111100) 5 = 55 (110111) 6 = 126 (1111110)
In both of those cases, you can follow the iteration of the divisibility rule on the result. So if your alternating sum totals to 110, then (even though it’s trivial), you run through the divisibility algorithm again and you will always get an alternating sum of 0 in the end.
the rules for checking divisibility by 7 for binary numbers were VERY relevant in the 2023 Putnam problem B2, which involved finding the smallest number of binary 1s in a multiple of 2023. it was a pain
What an opportunity missed, to cover a far more comprehensive summary of general divisibility rules. 1) The standard divisibility rule for 11 is inherited from the fact 11 divides 99, and is a "shortcut" for adding the "centits" of the number in base 100. I prefer tp explicitly add the centits (as doing so mod 11 is sufficient), though others may choose differently. 2) Hence treating 3 as 2+1 is ***inherited*** from the fact that 3 divides 4-1. Thus one can test divisibility by 3 by treating the base 2 number as a base 4 number, and add (mod 3) the quartets of the number (pairs of bits from right to left). 3) Likewise 5 divides 15 = 16 - 1; so divisibility by 5 can be tested by adding the hexits (base 16 "digits") of the base two number (mod 5 of course). 4) Then 7 is directly equal to 8-1, so owe can "cast out" multiples of 7 directly from the octets of the base 2 number viewed as a base eight number, again performing our sums mod 7. For your first example of 10 111 001 = 271 base 8 it's as simple as calculating 2+7+1 = 10 which is not divisible by 7, so neither is our original number. For your second example, 110 001 = 61 base 8, and it's as simple as 6+1 = 7 to confirm divisibility by 7. 5) For a real kicker you could note that 999 = 1024 - 25 = 32^2 - 5^2 = 27 * 37 and thus one can "cast out 37s" to tests divisibility of a number by 37 through adding, mod 37, the "millits" of a base 10 number by collecting triples, from right to left - which, conveniently, is exactly how we write larger base 10 numbers.
I prefer your method for 11s: much easier to add digit pairs casting out 11s as you go. You can also use the fact that 1001 = 77×13 for dividing by 13. To cast out 13s in each three digit number, multiply the digit on the left by 4 and subtract the result from the remaining two digit number.
@@colinmunro2632 Thank you. Check your signs though. Testing 169 for example, we wish to go to 16 + 9*4 = 52 not 16 - 9*4 = -20. Only the former gives the correct result. To use subtraction for 13 we need a factor of 13-4 = 9, so that 169 goes to 16 - 9*9 = -65. These patterns are sometimes referred to as Vedic divisibility rules, and can be developed for any odd prime number.
@pietergeerkens6324 for 169 to cast out the 13s it's 69-1×4 =65 so divisible by 13. Or 945 is 45-9×4=9 not divisible by 13. 687,345,864 becomes 63;33;32 and we don't need to cast out any more 13s 63-33+32=62. So not divisible by 13. Did you study Vedic maths? I was teaching it for some time.
@@colinmunro2632 Ah! I misunderstood. I hadn't seen the left-to-right calculation before. No, I've not studied it; though I've run across it from time to time in divisibility rules.
@pietergeerkens6324 actually the right to left method works for for testing divisibilty by 13, but not for casting out 13s. For example 105 would give 10+20=30 i.e 4. But it is actually 1 which you get from the left to right method. For larger numbers the sutractions can be lumped together. 368,476,823 would give 68-76+23-(3-4+8)x4=-13 so divisible by 13.
Another way to test for divisibility by three: 1. If there are two equal consecutive digits, remove them. 2. If there's the digit sequence 101 anywhere, replace it by 010. 3. If there are any 0 digits at the beginning or end, remove them. 4. Repeat until none of the rules can be applied any more. Now you either have removed all digits, or are left with either 1 or 10. If no digit is left, the number is divisible by three, otherwise it isn't.
the problem I see with removing digits on the right is that you lose the phase of the alternating sum. by default it gives you the number mod 3 (how much it is more than a multiple of 3). you can still apply those steps as they don't change the phase but careful when removing non-leading zeros
@@neon_05 if you care about the remainder, the only thing you need to skip is the removing of single zeros at the end. All other transformations are equivalencies modulo 3.
For 11 you can take groups of 5 bits and convert them to base 10, it's sort of like converting the binary into base 32 but we use the base 10 representation of the base 32 digits instead of a single symbol. Then we do the alternating sum of the numbers we end up with. We're basicly testing for divisibility by 33(32+1) using this method and since 11 divides 33 then this trick also works for 11 too. It also works for 3 but it's far less convenient that other methods of divisibility by 3. For 12 we can test divisibility by 3 and 4. For 13 we can use a similar trick that we used for 11 but this time in base 64. This is because 64+1 = 65 = 5*13. And this method also works for 5, but you'd never use this for 5. For 14 we can test divisibility by 2 and 7. For 15 we can test divisibility by 3 and 5. For 16 the bynary number has to end in 0000. We can go even further, let's go to 32: For 17, 17*15 = 255 = 256-1. It's a little ridiculous of an ask to convert the number to base 256 but this method works so whatever. Tho this time 255 is one lower than our base instead of one higher so we use a non-alternating sum. For 18 we test 2 and 9. For 19, we're really entering ridiculous territory now, 19*27 = 513 = 512+1. Alternating sum in base 512. Digits in base 512 are represented by 9 bits meaning that they can no longer be contained within a single byte on a computer and thus require 2 bytes. However this time our seccond operand also doesn't have a convenient divisibility rule so this trick is usefull for both 19 and 27. 9 and 3 are also here. For 20 we test 4 and 5. 21 is 3 and 7. 22 is 2 and 11. For 23, 23*89 = 2047 = 2048-1. Non-alternating sum in base 2048. For 24 test 3 and 8. For 25, 25*41 = 1025 = 1024+1. Alternating sum in base 1024. For 26 test 2 and 13. 27 we've already disgissed, Alternating sum in base 512. For 28 test 4 and 7. For 29, 29*565 = 16385 = 16384+1 = 2^14 +1. Alternating sum in base 16384. For 30 test 2, 3 and 5, spooky. For 31, non-alternating sum in base 32 For 32, the binary number has to end in 00000 Other than 17, 19, 23, 25, 27 and 29, these rules are surprisingly manageable.
@@Nick-the-fox And for 13, you can use groups of 6 bits (64) as 13*5=65. Technically, you can extend that to 17 and 19, but it starts to get unhelpful. 12 is divisibility by 3&4, 15 is 3&5, and 16 is last 4 bits are 0000 There you have it, extended to 16, even 17 (15*17 = 255, so 2^8-1), 18 is 2&9, 19 is groups of 9 (27*19=513, one more than 2^9)., Good luck with doing the math for 17*19 in your head…as I said, not very useful beyond 16
you recognize 3 is one more than 2, so you could do alternate sum on each bit. But you didn’t realize 7 is one less than 8, so you could sum the bits straight up? (7+1)^n = 1 (mod 7)
Zero is divisible by 0 is a statement of relation, it has nothing to do with the expression 0/0. For a to be divisible by b means that a is an integer multiple of b. And indeed, 0 is an integer multiple of 0, thus 0 is divisible by 0.
A couple of thoughts on 3 and 7... For 3, the alternating sum doesn't necessarily need to add to 0 to be a multiple of 3. It might also add to a positive or negative multiple of 3. For example, 10101₂ gives 1-0+1-0+1 = 3. This is a multiple of 3, so the original number is a multiple of 3. (It's 21 in base ten.) Another example: 11010101₂ gives 1-1+0-1+0-1+0-1 = -3. Even though it's negative, it's still a multiple of 3, so the original number is a multiple of 3. (It's 213 in base ten.) For 7, perhaps an easier way to solve this is to write the digits in groups of three and total them. For example, the number 1101011₂ could be split like this (padding out extra zeroes at the start, so there's a multiple of 3 digits, to become 001101011): 001 101 011 Add these up without carrying, and you get 113. Then you could use the powers trick you showed. 1*4 + 1*2 + 3*1 = 9, which is not a multiple of 7, and therefore the original number is not a multiple of 7. (This number is 107 in base ten.)
it's true that you can do all of the numbers like that, but there is also a trick that you can do that notices that 111&1 are 1 less than a multiple of 10, then take that multiple (say where working with 111 for example) so that multiple of 10 is 1000, so you ground all of the digits into triples and add all of those triples, repeat until you get a three digit number if that number is 111 then the original number is a multiple of 111, this can also be done with 11 if you prefer you can do three by add pairs of numbers and repeating until you get a 10-digit number, if that number is 11 then you're original number was a multiple of 11, this also works for any multiple of 10-1 ( note, this entire thing was in binary, just to remove any confusion.)
also, if you really want to you can use that system on 1, just add all of the digits until you get a one digit number, it can not be 0 so it is 1 and therefore the number is a multiple of 1. p.s. if you like binary I'd suggest that you watch "the best way to count" a video on the benefits of binary, it is really well done and addresses all of the major problems with binary, while also giving the perks that are truly there.
An interesting consequence for the divisibility rule for 7 is that any positive integer needs at least three 1 bits to be a multiple of 7. So the last example, 1000010, is not divisible by 7 automatically.
for divisibility by 5, can't we check that the number ends with 0 or 5 (101)? more generally, if the check is "if it ends with X" then we can just write X in the base we are working with and apply it directly? in the video 45 ends with 101 so it worked there, whereas 23 ends with 111 which is neither 101 or xx0 so it's not and indeed the convert to base 4 -> alternating sum test yields the same result
No, and the reason is that if you have a number like XXXX101, you would need that the rest of the number XXXX000 is also a multiple of 5. This isn't always true! For example, the number 1101 in binary is not divisible by 5: this number is 13 in base 10. Why did your test fail? 1000 in base 2 is not a multiple of 5. This number is 8 in base 10.
@@DinoMomPlays interesting so it kinda works then in base 10 it's "if it ends with 5" OR "if it ends with 0" but in base 2 that's AND maybe just a coincidence
Divisibility-checks that only look at the last digit(s) ONLY work if the divisor is a factor of the base. Checking divisibility by five in base ten only requires looking at the last digit because five is a factor of ten (two times five is ten). In base two, there are countless exceptions with no rules because five is not a factor of two or any power of two. Examples of binary numbers that end with 101 (five in binary) but are not divisible by five: 1101 (13), 10101 (21), 11101 (29), 100101 (37), 110101 (53), 111101 (61), 1000101 (69). These are all numbers of the form "x times eight plus five", and the only numbers I have left out are 101 (5) and 101101 (45), which are 0*8+5 and 5*8+5 respectively. In other words, the only numbers that end with 101 in binary and are divisible by five, are numbers that are nothing but 101 repeated multiple times. That's like saying "every number in base ten that is just 13 repeated multiple times is divisible by 13", which is true, but not that helpful.
@@Tumbolisu the fact that we know when it works is already huge, only having to look at the last digit for all divisors that divides their base is crazy haha, ty for the explanations!
i have another rule for the 3 divisibility if for example you have 110110 this number is like a base 4 with the symbols 00 01 10 11 so you pick it up like 11 01 10 you sum it up 110 again it is 01 10 sum again 11 if you get 11 then you have a number divisible by 3 this rule for every number that is the base number^(natural number)-1
Lowkey divisibility by 7 feels more logical in base 2 than in base 10. Do you know what it is in base 10? If yes, you gotta think to yourself that it feels so weird! And if not, go find it!
Since you're already converting to base 8 for divisibility for 9, why not do the same for divisibility by 7? This would be equivalent to the divisibility rule by 9 in base 10. 11010100101_2 = 3245_8 3+2+4+5 = 14 = 2*7, so it is divisible by 7.
You REALLY overcomplicated te divisibility by 7. Just convert to base 8 and calculate a regular sum between the digits instead of an alternating sum like the one you did for 9. 3 has a similar rule relating to base 4, meaning that 3 has two distinct divisibility rules in binary which is neat so it's worth mentioning.
To think that I put off taking the easiest math when at Auburn. I love math, now, and even taught in high school for a year when I was subbing. There was a desperate need for a teacher when one took maternity leave. I wish I would have loved math earlier in life.
For 7 instead of adding 4 you can subtract 3 This will let you check if it’s 0 or not instead of it is divisible by 7 (edit: could still be a multiple of 7 (try 147)) Ex. 111 -> -3+2+1 = 0, 0 is divisible by seven Ex2. 100011 -> -3+2+1 =0
Just like was mentioned in @wrathofmath’s correction for 3 and 5 For my take of 7 by using -3 instead of +4 you still need to check if the value is a multiple of 7 not just if it’s 0 or not. Take 147 (the first example where this happens) 10010011 2+2+2+1= 7 This is still a multiple of 7 (actually twice over) 7*21 or 7*7*3
Removed my rule about bit counts from my initial post as it was wrong and actually figure that out with the 91 and 147 examples I initially hypothesized that the bit’s set count would need to be a multiple of 3, this is false.
77 (base ten) is 1001101 (binary) and has four 1s. 91 (base ten) is 1011011 (binary) and has five 1s. 105 (base ten) is 1101001 (binary) and has five 1s. 147 (base ten) is 10010011 (binary) and has four 1s. These are just the first four exceptions to your rule that all multiples of 7 must have a multiple of three 1s in their binary form. Even with a single exception, it is easy to generate infinitely many more such numbers, so this rule is pretty bad. Since you mentioned a number with 7 bits set, I decided to purposefully search for a multiple of 7 with 7 bits set: 623 (base ten) = 1001101111 (binary) = 89 * 7
Converting from base 2 to any power-of-2 base is so incredibly easy, you can do all the calculations without even having to Actually convert the base. Just pretent that "00" is the base-4 digit for 0, "01" is the base-4 digit for 1, "10" is the base-4 digit for 2 and "11" is the base-4 digit for 3. Write them grouped up in pairs to make it even easier and let the magic happen.
Wait a minute: zero is not divisible by zero. If it were, then 0/0 would equal 1, as does any other value of x in x/x. In fact, 0/0 is undefined, as is anything else divided by zero.
0 is divisible by 0 because there exists an integer k such that 0*k=0 that doesn't mean 0/0 is defined, of course it is not, but 0 is divisible by 0 by definition
And as for a counter-example of the opposite statement, "if there is an odd number of 1s digits, it can't be divisible by 3": 10101 (binary) = 21 (base ten) = 7 * 3
You make things complicated with all the base preconversion stuff. Simpler way is to calculate "weights" for each digit. For 7 test, units weight is 1. Next to the left is 2 x 1 = 2. Next to the left is 2 x 2 = 4 (which is also -3). Next to the left is 2 x (-3) = -6 (which is also 1). So weights (starting from units going to the left) are 1, 2, -3, 1, 2, -3,1... or 1, 2, 4, 1, 2, 4... For 2, weights are 1, 0, 0... 3: 1, -1, 1... 4: 1, 2, 0, ... 5: 1, 2, -1, -2, 1, 2, ... 6: do 3 & 2 tests 7: 1, 2, -3, 1, ... or 1, 2, 4, 1... 8: 1, 2, 4, 0, 0... 9: 1, 2, 4, -1, -2, -4, 1, ... 10 do tests for 2 & 5 Start with weight = 1 for units. Multiply by radix (in this case 2) for following weight taking the modulo divisor being tested. This scheme will calculate weights for ANY radix number. Once a weight is zero, all following will be zero. Once a weight repeats a previous weight (or its negative) weights repeat in loop.
good comment, but I was trying to avoid modular congruence in this video as long as possible to make it most easily accessible to anyone curious about bases and familiar with base 10 divisibility rules
Just a nitpick: there are no binary numbers, only binary representations of numbers. The number ten is always the same, no matter whether you represent it as 10 in base ten, as 12 in base eight, as 1010 in base 2, as X in Roman numerals or as the syllable "ten" in English.
"binary number" means "binary representation of a number". Since there are binary representations of numbers, there are binary numbers. That is an interesting quirk of language though. Maybe it's arguable the number ten (or 10 or 1010 or X) isn't always the same; for example, the binary divisibility rules.
Zero is divisible by zero and the result of division is not relevant in this context. When we say 14 is divisible by 7, for example, it is because there is an integer that we can multiply 7 by to obtain 14. See 7*2=14. Certainly there also exists an integer we can multiply 0 by to obtain 0, 0*k=0 for all integers, in fact.
How to check divisibility from 1 to 10 in binary: Divisibility by 01: It doesn't have a decimal point Divisibility by 10: It ends with a 0 Thanks for watching
@@enderyu I disagree with your first rule: 1.0 clearly has a decimal point and is divisible by 1. Well, strictly speaking it's no *decimal* point, but a binary point.
CORRECTION: When referring to digit rules where the digits need to "add to 0" to be a multiple of 3, or "add to 0" to be a multiple of 5, the digits could also just add to a multiple of those respective numbers, 3 and 5, and it would still indicate divisibility. In the case of 3 for example, the digits alternating sum doesn't necessarily have to be 0, but needs to be 0 (mod 3), which means whatever the sum is should be divisible by 3, just like with the rule discussed for 7.
Also, yes 0 is divisible by 0. I would have included the definition of divisibility in this video (which has nothing in particular to do with 0/0), but that seemed like a big waste of time to clarify a point for a single number which isn't interesting in this discussion. To say 0 is divisible by 0 means there exists an integer k so 0*k is 0.
@@WrathofMath No, 0/0 isn’t 0, it’s indefinite, just like every other division by zero. Take your example 0 * k = 0, now apply your “0/0=0” logic to divide both sides by 0. (0*K)/0 = k and 0/0 = 0, ergo, k=0 implies that any number k =0. That’s why division by 0 is indefinite, for all values of k. There are a variety of situations in which you can show the limit is 0, 1, infinity, or various values, ergo, there is no universally defined value. You can explicitly define it to be a specific value based on the limit, for the purposes of treating a specific subset of functions as continuous over a range that includes 0.
@@geoffstrickler i don't know who you're replying to but it definitely isn't me
@@WrathofMath I’m replying to the second paragraph of your comment.
@@WrathofMathusing that definition of divisibility, there exists an integer k for arbitrary n such that n*k = 0, implying that every number is divisible by zero?
edit: it seems I have misunderstood
n is the number you are dividing by, so I have actually just said 0 is divisible by any number
@@user-pr6ed3ri2k Not quite.
A number p is divisible by q (written as q|p or "q divides p") if and only if there is some number k such that qk=p. This is the same as saying that p is a multiple of q.
You noticed that every number n has a k=0 such that 0n=0. This doesn't mean that 0 divides n, it means n divides 0 (n|0 for any number n). This makes sense as 0 is the 0'th multiple of every number.
For 7, you could also convert to base 8 and do a non-alternating sum of the digits. If the result is divisible by 7, then so is the original. It's the same as how divisibility by 9 works in base 10 since 7 is 1 less than 8.
I came here to say this
Note also that this gives an alternative strategy for divisibility by 3. Since 3 is 1 less than 4, convert to base 4 and do the non-alternating sum. Of course that rule applies also to 2-1=1, except that the fact that a binary number is divisible by 1 exactly if the sum of its digits is divisible by 1 is pretty useless (but still true).
That's kinda equivalent to what bro does already.
The 1 2 4 thing is equivalent to grouping the bits in 3 as base 8 & summing them all up to see if it's divisible by 7
Also note that since 4 is equivalent to -3 mod 7, you could also use bit factors of 1, 2, -3, ... . This will tend to keep the running total with a smaller absolute value, and clearly shows how adding all three together results in a multiple of 7 due to the remainders canceling out.
@@ElliottLine I came here to say this
"7... and skip!"
Divisibility by 7 is always my favorite
Divisibility by 7 actually isn't so bad. ... Yes, the number was written in base 7 how did you know?
1:34 the power of twooooooooOOOOOOOOO! *TPOT intro starts*
2:08 zero is divisible by zero??
yep. :)
zero might not be divisible by zero, but zero is a multiple of zero
Zero is by definition divisible by 0, that doesn't mean 0/0 is defined. But there exists an integer k so that 0*k=0, thus satisfying the definition of divisibility.
Petition to define 0/0 = 0
You can't divide by 0, that's not how math works.
Not sure why 7 got its own section when it's strictly easier than divisibility by 9 (at least to me since I consider non-alternating sums easier than alternating sums). If 9 was simple enough to blaze through, 7 should be as well.
Also, a long complicated description instead of saying convert to base 8 like was done for 4 earlier without such drama.
Converting to base six makes more sense.
Divisibility rule for 1011 (eleven): Take your binary number and split it into groups of 5, then take the alternating sum of these numbers.
This works because 2^5 + 1 = 3 * 11
Yes! This is as insightful a remark as the whole rest of the video. It opens up a whole class of divisibility rules base 2: namely for all the divisors of one less than any power of 2.
@@applimu7992 Same approach for 13, as 13*5 = 65, so use groups of 6 bits (aka base 64). 17*15 is 255, or one less than 2^8. 19*27=513… Starts to get unhelpful at that point
So, something completely random that occurred to me.
Using only binary numbers, written in binary form, for any number, from 1 to n, what is the _smallest_ number that is divisible by any number, n, that contains "n" 1s with any 0s?
Well, for the first 6 numbers, these are:
1 = 1
2 = 6 (110)
3 = 21 (10101)
4 = 60 (111100)
5 = 55 (110111)
6 = 126 (1111110)
In both of those cases, you can follow the iteration of the divisibility rule on the result. So if your alternating sum totals to 110, then (even though it’s trivial), you run through the divisibility algorithm again and you will always get an alternating sum of 0 in the end.
the rules for checking divisibility by 7 for binary numbers were VERY relevant in the 2023 Putnam problem B2, which involved finding the smallest number of binary 1s in a multiple of 2023. it was a pain
The trick for 7 at the end has equivalents with the other factors. Here is the relevant sequence of powers of 2 mod n for each number n up to 17: (Edited to fix my mistake with 14)
#: (sequence from right to left)
2: 1, 0, 0, 0...
3: 1, 2, 1, 2...
or: 1, -1, 1, -1,...
4: 1, 2, 0, 0....
5: 1, 2, -1, -2,...
6: 1, 2, -2, 2, -2,...
7: 1, 2, 4, 1, 2, 4,...
8: 1, 2, 4, 0, 0, 0...
9: 1, 2, 4, -1, -2, -4,...
10: 1, 2, 4, -2, -4, 2, 4, -2, -4,...
11: 1, 2, 4, 8, 5, -1, -2, -4, -8, -5,...
12: 1, 2, 4, -4, 4, -4,...
13: 1, 2, 4, 8, 3, 6, -1, -2, -4, -8, -3, -6,...
14: 1, 2, 4, 8, 2, 4, 8, 2, 4, 8,...
15: 1, 2, 4, 8, 1, 2, 4, 8,...
16: 1, 2, 4, 8, 0, 0, 0, 0,...
17: 1, 2, 4, 8, -1, -2, -4, -8,...
why not for larger n?
@@vumixe Gotta stop somewhere, otherwise they'd be doing it for an eternity
@@vumixe I did a reply and went up to 23, but youtube ate it. You can continue if you want. It's not terribly difficult.
What an opportunity missed, to cover a far more comprehensive summary of general divisibility rules.
1) The standard divisibility rule for 11 is inherited from the fact 11 divides 99, and is a "shortcut" for adding the "centits" of the number in base 100. I prefer tp explicitly add the centits (as doing so mod 11 is sufficient), though others may choose differently.
2) Hence treating 3 as 2+1 is ***inherited*** from the fact that 3 divides 4-1. Thus one can test divisibility by 3 by treating the base 2 number as a base 4 number, and add (mod 3) the quartets of the number (pairs of bits from right to left).
3) Likewise 5 divides 15 = 16 - 1; so divisibility by 5 can be tested by adding the hexits (base 16 "digits") of the base two number (mod 5 of course).
4) Then 7 is directly equal to 8-1, so owe can "cast out" multiples of 7 directly from the octets of the base 2 number viewed as a base eight number, again performing our sums mod 7.
For your first example of 10 111 001 = 271 base 8 it's as simple as calculating 2+7+1 = 10 which is not divisible by 7, so neither is our original number.
For your second example, 110 001 = 61 base 8, and it's as simple as 6+1 = 7 to confirm divisibility by 7.
5) For a real kicker you could note that 999 = 1024 - 25 = 32^2 - 5^2 = 27 * 37 and thus one can "cast out 37s" to tests divisibility of a number by 37 through adding, mod 37, the "millits" of a base 10 number by collecting triples, from right to left - which, conveniently, is exactly how we write larger base 10 numbers.
I prefer your method for 11s: much easier to add digit pairs casting out 11s as you go.
You can also use the fact that 1001 = 77×13 for dividing by 13. To cast out 13s in each three digit number, multiply the digit on the left by 4 and subtract the result from the remaining two digit number.
@@colinmunro2632 Thank you. Check your signs though. Testing 169 for example, we wish to go to 16 + 9*4 = 52 not 16 - 9*4 = -20. Only the former gives the correct result. To use subtraction for 13 we need a factor of 13-4 = 9, so that 169 goes to 16 - 9*9 = -65.
These patterns are sometimes referred to as Vedic divisibility rules, and can be developed for any odd prime number.
@pietergeerkens6324 for 169 to cast out the 13s it's 69-1×4 =65 so divisible by 13. Or 945 is 45-9×4=9 not divisible by 13. 687,345,864 becomes 63;33;32 and we don't need to cast out any more 13s 63-33+32=62. So not divisible by 13.
Did you study Vedic maths? I was teaching it for some time.
@@colinmunro2632 Ah! I misunderstood. I hadn't seen the left-to-right calculation before.
No, I've not studied it; though I've run across it from time to time in divisibility rules.
@pietergeerkens6324 actually the right to left method works for for testing divisibilty by 13, but not for casting out 13s. For example 105 would give 10+20=30 i.e 4. But it is actually 1 which you get from the left to right method.
For larger numbers the sutractions can be lumped together. 368,476,823 would give 68-76+23-(3-4+8)x4=-13 so divisible by 13.
Another way to test for divisibility by three:
1. If there are two equal consecutive digits, remove them.
2. If there's the digit sequence 101 anywhere, replace it by 010.
3. If there are any 0 digits at the beginning or end, remove them.
4. Repeat until none of the rules can be applied any more.
Now you either have removed all digits, or are left with either 1 or 10. If no digit is left, the number is divisible by three, otherwise it isn't.
the problem I see with removing digits on the right is that you lose the phase of the alternating sum. by default it gives you the number mod 3 (how much it is more than a multiple of 3). you can still apply those steps as they don't change the phase but careful when removing non-leading zeros
wow, can't wait to use that rule on a number that's longer than 10 digits 😃
@@neon_05 if you care about the remainder, the only thing you need to skip is the removing of single zeros at the end. All other transformations are equivalencies modulo 3.
Should’ve made it for numbers 1-16
For 11 you can take groups of 5 bits and convert them to base 10, it's sort of like converting the binary into base 32 but we use the base 10 representation of the base 32 digits instead of a single symbol. Then we do the alternating sum of the numbers we end up with. We're basicly testing for divisibility by 33(32+1) using this method and since 11 divides 33 then this trick also works for 11 too. It also works for 3 but it's far less convenient that other methods of divisibility by 3.
For 12 we can test divisibility by 3 and 4.
For 13 we can use a similar trick that we used for 11 but this time in base 64. This is because 64+1 = 65 = 5*13. And this method also works for 5, but you'd never use this for 5.
For 14 we can test divisibility by 2 and 7.
For 15 we can test divisibility by 3 and 5.
For 16 the bynary number has to end in 0000.
We can go even further, let's go to 32:
For 17, 17*15 = 255 = 256-1. It's a little ridiculous of an ask to convert the number to base 256 but this method works so whatever. Tho this time 255 is one lower than our base instead of one higher so we use a non-alternating sum.
For 18 we test 2 and 9.
For 19, we're really entering ridiculous territory now, 19*27 = 513 = 512+1. Alternating sum in base 512. Digits in base 512 are represented by 9 bits meaning that they can no longer be contained within a single byte on a computer and thus require 2 bytes. However this time our seccond operand also doesn't have a convenient divisibility rule so this trick is usefull for both 19 and 27. 9 and 3 are also here.
For 20 we test 4 and 5.
21 is 3 and 7.
22 is 2 and 11.
For 23, 23*89 = 2047 = 2048-1. Non-alternating sum in base 2048.
For 24 test 3 and 8.
For 25, 25*41 = 1025 = 1024+1. Alternating sum in base 1024.
For 26 test 2 and 13.
27 we've already disgissed, Alternating sum in base 512.
For 28 test 4 and 7.
For 29, 29*565 = 16385 = 16384+1 = 2^14 +1. Alternating sum in base 16384.
For 30 test 2, 3 and 5, spooky.
For 31, non-alternating sum in base 32
For 32, the binary number has to end in 00000
Other than 17, 19, 23, 25, 27 and 29, these rules are surprisingly manageable.
@@Nick-the-fox And for 13, you can use groups of 6 bits (64) as 13*5=65. Technically, you can extend that to 17 and 19, but it starts to get unhelpful.
12 is divisibility by 3&4, 15 is 3&5, and 16 is last 4 bits are 0000
There you have it, extended to 16, even 17 (15*17 = 255, so 2^8-1), 18 is 2&9, 19 is groups of 9 (27*19=513, one more than 2^9)., Good luck with doing the math for 17*19 in your head…as I said, not very useful beyond 16
you recognize 3 is one more than 2, so you could do alternate sum on each bit. But you didn’t realize 7 is one less than 8, so you could sum the bits straight up?
(7+1)^n = 1 (mod 7)
Really creative topic for a video. Great presentation!
Thank you!
Gotta say this video is pretty based
true
2:10 Zero is divisible by zero? Is that equal to 0 or 1? This new math is hard. I my school they taught 0/0 was undefined.
Zero is divisible by 0 is a statement of relation, it has nothing to do with the expression 0/0. For a to be divisible by b means that a is an integer multiple of b. And indeed, 0 is an integer multiple of 0, thus 0 is divisible by 0.
THE CORRECTION OF 3: add the sum of digits and the end look if its divisible by there.
A couple of thoughts on 3 and 7...
For 3, the alternating sum doesn't necessarily need to add to 0 to be a multiple of 3. It might also add to a positive or negative multiple of 3. For example, 10101₂ gives 1-0+1-0+1 = 3. This is a multiple of 3, so the original number is a multiple of 3. (It's 21 in base ten.) Another example: 11010101₂ gives 1-1+0-1+0-1+0-1 = -3. Even though it's negative, it's still a multiple of 3, so the original number is a multiple of 3. (It's 213 in base ten.)
For 7, perhaps an easier way to solve this is to write the digits in groups of three and total them. For example, the number 1101011₂ could be split like this (padding out extra zeroes at the start, so there's a multiple of 3 digits, to become 001101011):
001
101
011
Add these up without carrying, and you get 113. Then you could use the powers trick you showed. 1*4 + 1*2 + 3*1 = 9, which is not a multiple of 7, and therefore the original number is not a multiple of 7. (This number is 107 in base ten.)
it's true that you can do all of the numbers like that, but there is also a trick that you can do that notices that 111&1 are 1 less than a multiple of 10, then take that multiple (say where working with 111 for example) so that multiple of 10 is 1000, so you ground all of the digits into triples and add all of those triples, repeat until you get a three digit number if that number is 111 then the original number is a multiple of 111, this can also be done with 11 if you prefer you can do three by add pairs of numbers and repeating until you get a 10-digit number, if that number is 11 then you're original number was a multiple of 11, this also works for any multiple of 10-1 ( note, this entire thing was in binary, just to remove any confusion.)
also, if you really want to you can use that system on 1, just add all of the digits until you get a one digit number, it can not be 0 so it is 1 and therefore the number is a multiple of 1. p.s. if you like binary I'd suggest that you watch "the best way to count" a video on the benefits of binary, it is really well done and addresses all of the major problems with binary, while also giving the perks that are truly there.
An interesting consequence for the divisibility rule for 7 is that any positive integer needs at least three 1 bits to be a multiple of 7. So the last example, 1000010, is not divisible by 7 automatically.
for divisibility by 5, can't we check that the number ends with 0 or 5 (101)? more generally, if the check is "if it ends with X" then we can just write X in the base we are working with and apply it directly?
in the video 45 ends with 101 so it worked there, whereas 23 ends with 111 which is neither 101 or xx0 so it's not and indeed the convert to base 4 -> alternating sum test yields the same result
No, and the reason is that if you have a number like XXXX101, you would need that the rest of the number XXXX000 is also a multiple of 5. This isn't always true!
For example, the number 1101 in binary is not divisible by 5: this number is 13 in base 10. Why did your test fail? 1000 in base 2 is not a multiple of 5. This number is 8 in base 10.
@@DinoMomPlays interesting so it kinda works then
in base 10 it's "if it ends with 5" OR "if it ends with 0" but in base 2 that's AND
maybe just a coincidence
Divisibility-checks that only look at the last digit(s) ONLY work if the divisor is a factor of the base. Checking divisibility by five in base ten only requires looking at the last digit because five is a factor of ten (two times five is ten). In base two, there are countless exceptions with no rules because five is not a factor of two or any power of two.
Examples of binary numbers that end with 101 (five in binary) but are not divisible by five: 1101 (13), 10101 (21), 11101 (29), 100101 (37), 110101 (53), 111101 (61), 1000101 (69).
These are all numbers of the form "x times eight plus five", and the only numbers I have left out are 101 (5) and 101101 (45), which are 0*8+5 and 5*8+5 respectively. In other words, the only numbers that end with 101 in binary and are divisible by five, are numbers that are nothing but 101 repeated multiple times. That's like saying "every number in base ten that is just 13 repeated multiple times is divisible by 13", which is true, but not that helpful.
@@Tumbolisu the fact that we know when it works is already huge, only having to look at the last digit for all divisors that divides their base is crazy haha, ty for the explanations!
i have another rule for the 3 divisibility if for example you have 110110 this number is like a base 4 with the symbols 00 01 10 11 so you pick it up like 11 01 10 you sum it up 110 again it is 01 10 sum again 11 if you get 11 then you have a number divisible by 3 this rule for every number that is the base number^(natural number)-1
Lowkey divisibility by 7 feels more logical in base 2 than in base 10.
Do you know what it is in base 10? If yes, you gotta think to yourself that it feels so weird!
And if not, go find it!
Since you're already converting to base 8 for divisibility for 9, why not do the same for divisibility by 7? This would be equivalent to the divisibility rule by 9 in base 10.
11010100101_2 = 3245_8
3+2+4+5 = 14 = 2*7, so it is divisible by 7.
You REALLY overcomplicated te divisibility by 7.
Just convert to base 8 and calculate a regular sum between the digits instead of an alternating sum like the one you did for 9.
3 has a similar rule relating to base 4, meaning that 3 has two distinct divisibility rules in binary which is neat so it's worth mentioning.
To think that I put off taking the easiest math when at Auburn. I love math, now, and even taught in high school for a year when I was subbing. There was a desperate need for a teacher when one took maternity leave. I wish I would have loved math earlier in life.
YouFeeAreIrr
YouFeeAreIrr
For 7 instead of adding 4 you can subtract 3
This will let you check if it’s 0 or not instead of it is divisible by 7 (edit: could still be a multiple of 7 (try 147))
Ex. 111 -> -3+2+1 = 0, 0 is divisible by seven
Ex2.
100011 -> -3+2+1 =0
Just like was mentioned in @wrathofmath’s correction for 3 and 5
For my take of 7 by using -3 instead of +4 you still need to check if the value is a multiple of 7 not just if it’s 0 or not.
Take 147 (the first example where this happens)
10010011
2+2+2+1= 7
This is still a multiple of 7 (actually twice over) 7*21 or 7*7*3
Actually the first example is 91 not 147
91=1011011
1+2+1+2+1=7
Removed my rule about bit counts from my initial post as it was wrong and actually figure that out with the 91 and 147 examples
I initially hypothesized that the bit’s set count would need to be a multiple of 3, this is false.
77 (base ten) is 1001101 (binary) and has four 1s. 91 (base ten) is 1011011 (binary) and has five 1s. 105 (base ten) is 1101001 (binary) and has five 1s. 147 (base ten) is 10010011 (binary) and has four 1s. These are just the first four exceptions to your rule that all multiples of 7 must have a multiple of three 1s in their binary form. Even with a single exception, it is easy to generate infinitely many more such numbers, so this rule is pretty bad.
Since you mentioned a number with 7 bits set, I decided to purposefully search for a multiple of 7 with 7 bits set: 623 (base ten) = 1001101111 (binary) = 89 * 7
@@Tumbolisuthat’s why I said it was wrong and removed it from my first post
Convert to base 7 and solve by inspection.
isnt there a way to do a 5 divisibility check without base conversion?
Converting from base 2 to any power-of-2 base is so incredibly easy, you can do all the calculations without even having to Actually convert the base. Just pretent that "00" is the base-4 digit for 0, "01" is the base-4 digit for 1, "10" is the base-4 digit for 2 and "11" is the base-4 digit for 3. Write them grouped up in pairs to make it even easier and let the magic happen.
7:40 QUaternary digIT or quit.
Just memorise the magic sequences. This was highlighted super clear in the video "the best way to count".
Wait a minute: zero is not divisible by zero. If it were, then 0/0 would equal 1, as does any other value of x in x/x.
In fact, 0/0 is undefined, as is anything else divided by zero.
X,2x+5=8[n3]
Correction for the divisible by 0 rule, 0/0 IS UNDEFINED, hence 0/0 does NOT equal 0
True, except it is actually indeterminate
0 is divisible by 0 because there exists an integer k such that 0*k=0
that doesn't mean 0/0 is defined, of course it is not, but 0 is divisible by 0 by definition
@@WrathofMath ok sure, but it still does not equal 0 as the video said.
the video didn't say that, the only thing I said about 0 is "the only number divisible by 0 is 0"
@@WrathofMath ah alright. that is mb
4:45 if the number has an even number of ones, then it is a multiple of 3
Even number of one digits*
101
And as for a counter-example of the opposite statement, "if there is an odd number of 1s digits, it can't be divisible by 3":
10101 (binary) = 21 (base ten) = 7 * 3
You make things complicated with all the base preconversion stuff. Simpler way is to calculate "weights" for each digit. For 7 test, units weight is 1. Next to the left is 2 x 1 = 2. Next to the left is 2 x 2 = 4 (which is also -3). Next to the left is 2 x (-3) = -6 (which is also 1). So weights (starting from units going to the left) are 1, 2, -3, 1, 2, -3,1... or 1, 2, 4, 1, 2, 4...
For 2, weights are 1, 0, 0...
3: 1, -1, 1...
4: 1, 2, 0, ...
5: 1, 2, -1, -2, 1, 2, ...
6: do 3 & 2 tests
7: 1, 2, -3, 1, ... or 1, 2, 4, 1...
8: 1, 2, 4, 0, 0...
9: 1, 2, 4, -1, -2, -4, 1, ...
10 do tests for 2 & 5
Start with weight = 1 for units. Multiply by radix (in this case 2) for following weight taking the modulo divisor being tested. This scheme will calculate weights for ANY radix number.
Once a weight is zero, all following will be zero.
Once a weight repeats a previous weight (or its negative) weights repeat in loop.
good comment, but I was trying to avoid modular congruence in this video as long as possible to make it most easily accessible to anyone curious about bases and familiar with base 10 divisibility rules
Just a nitpick: there are no binary numbers, only binary representations of numbers. The number ten is always the same, no matter whether you represent it as 10 in base ten, as 12 in base eight, as 1010 in base 2, as X in Roman numerals or as the syllable "ten" in English.
"binary number" means "binary representation of a number". Since there are binary representations of numbers, there are binary numbers. That is an interesting quirk of language though. Maybe it's arguable the number ten (or 10 or 1010 or X) isn't always the same; for example, the binary divisibility rules.
as a circuit, decimal is weirder.
Ok… but what about hex?
I wouldn't say binary's rules are all that quirky, in fact, they're kinda intuitive,
Division by zero is undefined, even if the other operand is zero. So, zero is not divisible by zero.
Zero is divisible by zero and the result of division is not relevant in this context. When we say 14 is divisible by 7, for example, it is because there is an integer that we can multiply 7 by to obtain 14. See 7*2=14. Certainly there also exists an integer we can multiply 0 by to obtain 0, 0*k=0 for all integers, in fact.
@@WrathofMath Actually, the "result" of that division is precisely why 0/0 is undefined, because the value you get depends on how you approach it.
How to check divisibility from 1 to 10 in binary:
Divisibility by 01: It doesn't have a decimal point
Divisibility by 10: It ends with a 0
Thanks for watching
@@enderyu I disagree with your first rule: 1.0 clearly has a decimal point and is divisible by 1. Well, strictly speaking it's no *decimal* point, but a binary point.
Best base is 6
jan misali agrees
First