12:14 wouldn't that be much, much easier if we start with 5? the larger prime you can get rid of the smaller the remaining number would be for you to check, and 5 is rather obvious from the ending digits of 375 (1000 = 125*8 so numbers ending with 375 is divisible by 125 or 5^3 at the very least) and from 14:11 it's not like you are doing it in ascending primes either.
2:46 The divisibility by 3 and 9 rules are actually special cases of the fact that the sum of the digits of a number are equal to that number modulo 3 or 9. For example, 26 = 2 mod 3 and (2+6) = 2 mod 3. Likewise 26 = (2+6) = 8 mod 9. So the divisibility rules are just special cases where N = 0 mod 3 or 9. (The proof is basically the same as the divisibility proof in the video.) P.S. This isn’t true for 11. For example, 12 = 1 mod 11 but (1-2) = -1 mod 11.
Many thanks for your teaching, especially for a math major who did not take a number theory class back in college. This is still some fun math stuff for me. And those AIME problems as well!
My solution to the last problem was a bit different: We start with 101a + 10b ≡ 0 (mod 33) Since 33 | aba. Then because 101 ≡ 2 (mod 33), we have 2a + 10b ≡ 0 (mod 33) And sice 2 and 33 are coprime we can divide both sides of the equivalence by two, and write like a + 5b = 33n, n∈Z And now the equation is even less trivial than before, therefore we'll apply mod 5 on both sides of the equation a ≡ 3n (mod 5) And we can express it in equation form again a = 3n + 5k, k∈Z And substituting in the a + 5b = 33n equation b = 6n - k Where we can easily see that n = 1, and k ∈ {0,1}, therefore aba ∈ {363, 858}
As a bit of a side result, if you want to test a number for divisibility mod prime p, you can always first reduce it by summing its digits in groups of p-1, thanks to Fermat’s Little Theorem.
@@alexkonopatski429 Sure. Because 10^(p-1) = 1 mod p, then if you have a number that’s, for example, Ax10^(2p-2)+Bx10^(p-1)+C then mod p that’s congruent to A+B+C. So for example to test for divisibility by 7 you can reduce it to a 6-digit number first.
Damn, modular arithmetic makes the proofs of the digit sums so much more elegant and easy than drawing out by hand that part of N that's divisible by the respective number leaving the respective digit sum.
I have a warm-up 👌 assume there is a dice with faces (x,y,*2,*2,*3,*5) where x and y are real numbers and *2 or *3 or *5 are multipliers and dice works in this way 1)the goal is to get the biggest number as possible 2)the multipliers itself hasn't any value lonely 3)the value of x and y lonely are x and y 4)if x or y rolled after a multiplier had rolled, the value of x or y will be multiplied by the result multiplier (RM for short) then RM is back to one 5)if multiplier rolled, the result multiplier (RM) is a multiplier that equal the previous rolled one(if it was a multiplier and 1 if it was x or y) times the current the question is what is the biggest number and expected value after N rolls?
so if I rolled *2 then rolled *3 I get RM = *6 right? is that what you are saying. and if I rolled *2 then I rolled y I get 2*y and if I rolled x after wards I will add x to 2*y am I correct?
Divisibility by 11 : I am going to illustrated with one example 123458 * 11 = 1358038 .take the 2 alternated (even/odd rank) sums of the number 1358038 : S1 = 8 +0+5 +1 = 14 and S2 = 3+8+3 =14 you remark that S1=S2 A number is divisible by 11 if the 2 alternated sums of its digits are equal
@@CTJ2619 that is what I meant - divisibility bij 1001 is done in the same way as the 11 rule - and similarly to 999 being a multiple of 37, you can use this to determine divisibility by 7, 11, or 13 by getting the alternating sum of groups of 3 digits
(Edited) You sure about that? 4 divides 12, but 12 -> a1 + a0 = 1 + 2 = 3 -> 2 * 3 = 6, and 4 does not divide 6. Did I mess something up? EDIT: Lol, yup, I did mess something up, I added before I multiplied. In the case of 12, it should be 2*a1 + a0 = 2*1 + 2 = 2 + 2 = 4, and 4 divides 4 so it's not a counterexample.
@@DouglasZwick Actually, I think that you may have interpreted his comment wrong, since 4 divides 12, and for 12 we have (2 * a1) + a0 = (2 * 1) + 2 = 2 + 2 = 4, which does also divide 4. Additionally, here's my proof of that: If we let N = 10^M * aM + . . . + 10^2 * a2 + 10 * a1 + a0, then we have the following: N = 10^M * aM + . . . + 10^2 * a2 + 8 * a1 + [ (2 * a1) + a0 ], and since 10^M * aM + . . . + 10^2 * a2 + 8 * a1 = 4 * 25 * 10^(M-2) * aM + . . . + 4 * 25 * a2 + 4 * 2 * a1 = 4 * [ 25 * 10^(M-2) * aM + . . . + 25 * a2 + 2 * a1 ], which is obviously divisible by 4, and we would like N to be divisible by 4, then (2 * a1) + a0 must be divisible by 4.
Here's a much simpler rule for 7 from this video: th-cam.com/video/YvJvz0NqU20/w-d-xo.html. Note that the following proof of this rule is from Michael Empeigne, who commented this on that video 6 months ago: """ n = 10a + b n = 10a + b + 20b - 20b n = 10a - 20b + 21b n = 10* ( a - 2b ) + 21b since 21b is divisible by 7 and we would like n to be divisible by 7, then a - 2b must be divisible by 7. """
7:14 Homework
12:03 Proof left for the viewer
16:01 👶
25:10 I think we can throw the 22 away
26:31 Homework
26:53 Good Place To Stop
25:10 Michael Penn always hides a mistake to take us on an egg hunt ... and be proud
like a child who finds
on the divisibility of n by 37 he takes mod 11 instead of 37 why?
anyone knows
12:14 wouldn't that be much, much easier if we start with 5? the larger prime you can get rid of the smaller the remaining number would be for you to check, and 5 is rather obvious from the ending digits of 375 (1000 = 125*8 so numbers ending with 375 is divisible by 125 or 5^3 at the very least) and from 14:11 it's not like you are doing it in ascending primes either.
very nice, but you can not get 2a-b = 22
hmmm.. thought i was getting something wrong. but seems impossible to me given the constraints that a,b must be >=0 and
21:08 we can immediately deduce that both a and b have to be odd, since 5ab=even+even+odd=odd.
So later on we don't need to check the case where b=2
@ 10:08 Should be mod 37, not mod 11.
quick check for 37 divides 999 : 37 * 3 = 111 and since 999 is a multiple of 111; it is divisible by 37
2:46 The divisibility by 3 and 9 rules are actually special cases of the fact that the sum of the digits of a number are equal to that number modulo 3 or 9. For example, 26 = 2 mod 3 and (2+6) = 2 mod 3. Likewise 26 = (2+6) = 8 mod 9. So the divisibility rules are just special cases where N = 0 mod 3 or 9. (The proof is basically the same as the divisibility proof in the video.)
P.S. This isn’t true for 11. For example, 12 = 1 mod 11 but (1-2) = -1 mod 11.
Thumbnail foolled me that I am gonna listen to Ed Sheeran, but that's better
How? Was the thumbnail different when you first watched the video
Many thanks for your teaching, especially for a math major who did not take a number theory class back in college. This is still some fun math stuff for me. And those AIME problems as well!
My solution to the last problem was a bit different:
We start with
101a + 10b ≡ 0 (mod 33)
Since 33 | aba. Then because 101 ≡ 2 (mod 33), we have
2a + 10b ≡ 0 (mod 33)
And sice 2 and 33 are coprime we can divide both sides of the equivalence by two, and write like
a + 5b = 33n, n∈Z
And now the equation is even less trivial than before, therefore we'll apply mod 5 on both sides of the equation
a ≡ 3n (mod 5)
And we can express it in equation form again
a = 3n + 5k, k∈Z
And substituting in the a + 5b = 33n equation
b = 6n - k
Where we can easily see that n = 1, and k ∈ {0,1}, therefore aba ∈ {363, 858}
As a bit of a side result, if you want to test a number for divisibility mod prime p, you can always first reduce it by summing its digits in groups of p-1, thanks to Fermat’s Little Theorem.
It doesn't work for p=2, 5 because they are divisor of 10
@ConManAU Could you please explain that a little more, 'cause I don't quite understand what you mean. Thanks in Advance!
@@alexkonopatski429 Sure. Because 10^(p-1) = 1 mod p, then if you have a number that’s, for example, Ax10^(2p-2)+Bx10^(p-1)+C then mod p that’s congruent to A+B+C. So for example to test for divisibility by 7 you can reduce it to a 6-digit number first.
The screech at 18:06 tho
Damn, modular arithmetic makes the proofs of the digit sums so much more elegant and easy than drawing out by hand that part of N that's divisible by the respective number leaving the respective digit sum.
At 13:00, it is obvious that 25 | N; I would have started there.
Yes, that's best way to start.
858 in addition to 363 for last problem
I have a warm-up 👌
assume there is a dice with faces (x,y,*2,*2,*3,*5)
where x and y are real numbers and
*2 or *3 or *5 are multipliers
and dice works in this way
1)the goal is to get the biggest number as possible
2)the multipliers itself hasn't any value lonely
3)the value of x and y lonely are x and y
4)if x or y rolled after a multiplier had rolled, the value of x or y will be multiplied by the result multiplier (RM for short) then RM is back to one
5)if multiplier rolled, the result multiplier (RM) is a multiplier that equal the previous rolled one(if it was a multiplier and 1 if it was x or y) times the current
the question is what is the biggest number and expected value after N rolls?
hope Micheal Penn make video about it 😊
so if I rolled *2 then rolled *3 I get RM = *6 right? is that what you are saying. and if I rolled *2 then I rolled y I get 2*y and if I rolled x after wards I will add x to 2*y am I correct?
@@humamsebai8604 yes
Great video.
How about the 7s and 11s divisibility rules
7 * 11 * 13 = 1001, you mean? That is my favourite divisibility rule...
Divisibility by 11 : I am going to illustrated with one example 123458 * 11 = 1358038
.take the 2 alternated (even/odd rank) sums of the number 1358038 : S1 = 8 +0+5 +1 = 14 and S2 = 3+8+3 =14 you remark that S1=S2
A number is divisible by 11 if the 2 alternated sums of its digits are equal
@@voorth no I meant do you know how to determine if a number is divisible by 7? th-cam.com/video/YvJvz0NqU20/w-d-xo.html
@@WahranRai thanks but i know the divisibility rule for 11 did you know there is a rule for 7 as well?
@@CTJ2619 that is what I meant - divisibility bij 1001 is done in the same way as the 11 rule - and similarly to 999 being a multiple of 37, you can use this to determine divisibility by 7, 11, or 13 by getting the alternating sum of groups of 3 digits
@16:02 ish very big mouse was scared by the math?😂
LOL!
4 divides N if and only if 4 divides (2 times a1 + a0).
(Edited) You sure about that? 4 divides 12, but 12 -> a1 + a0 = 1 + 2 = 3 -> 2 * 3 = 6, and 4 does not divide 6. Did I mess something up? EDIT: Lol, yup, I did mess something up, I added before I multiplied. In the case of 12, it should be 2*a1 + a0 = 2*1 + 2 = 2 + 2 = 4, and 4 divides 4 so it's not a counterexample.
@@DouglasZwick Actually, I think that you may have interpreted his comment wrong, since 4 divides 12, and for 12 we have (2 * a1) + a0 = (2 * 1) + 2 = 2 + 2 = 4, which does also divide 4. Additionally, here's my proof of that:
If we let N = 10^M * aM + . . . + 10^2 * a2 + 10 * a1 + a0, then we have the following:
N = 10^M * aM + . . . + 10^2 * a2 + 8 * a1 + [ (2 * a1) + a0 ], and since 10^M * aM + . . . + 10^2 * a2 + 8 * a1
= 4 * 25 * 10^(M-2) * aM + . . . + 4 * 25 * a2 + 4 * 2 * a1 = 4 * [ 25 * 10^(M-2) * aM + . . . + 25 * a2 + 2 * a1 ], which is obviously divisible by 4, and we would like N to be divisible by 4, then (2 * a1) + a0 must be divisible by 4.
@@megauser8512 Heh, yeah, I caught my mistake as soon as I reread my comment after your reply :)
-- Mr. Hitler, do you like jews?
-- 9:09.
LOL!
858
Here's a much simpler rule for 7 from this video: th-cam.com/video/YvJvz0NqU20/w-d-xo.html.
Note that the following proof of this rule is from Michael Empeigne, who commented this on that video 6 months ago:
"""
n = 10a + b
n = 10a + b + 20b - 20b
n = 10a - 20b + 21b
n = 10* ( a - 2b ) + 21b
since 21b is divisible by 7 and we would like n to be divisible by 7, then a - 2b must be divisible by 7.
"""
75³⁰⁷ = ? mod 735
V
Number theory is confusing
응
응
I like kimbap