@@terryendicott2939 accuracy is not the same as pickiness in maths. 91 is not congruent to 0 modulo 37. If someone were to try to show that it is then they would have an awful lot of trouble since it is incongruent. A proof is a proof, not an approximation.
At 23:17, proof of the following statement: If a ≡ b (mod n), then a^m ≡ b^m (mod n), m∈ℕ Suppose a ≡ b (mod n) ⇒ a - b = nk, for some k∈ℤ ⇒ a = nk + b ⇒ a^m = (nk + b)^m Using the binomial expansion, we get a^m = (m 0)*(nk)^m + (m 1)*(nk)^(m-1)*b + … + (m m)*b^m, where (x y) means x choose y. If we reduce the equation mod n, all of the terms on the RHS reduce to (m m)*b^m (mod n), since every term containing an n is ≡ 0 (mod n). Also in the video it is proven that if a ≡ b (mod n) and c ≡ d (mod n), then a + b ≡ c + d (mod n). Using this fact, we get that a^m ≡ (m m)*b^m (mod n), but we know (m m) = 1 ⇒ a^m ≡ b^m (mod n). Q.E.D. Please correct me if my proof is wrong.
Professor Michael Penn, this is a solid and well-organized video/lecture on Modulo Arithmetic in Number Theory Eight. These mathematical topics has been around forever.
Thank you so much for making this, I like number theory problems a lot, I watch a lot of those you post on your channel, and while I was able to understand the concept of modular arithmetic by watching those videos mostly some things I always wondered about. I was hoping you would make a video explaining all this
Hi Michael, great series. I was recently studying number theory independently (with the help of your old series among other things) and I came across a beautiful fact I suggest you include in the current series : the equivalence of CRT and Lagrange interpolation. #suggestion
Wish you speedy recovery from the ailment and surgery Mike. With the best wishes from 🇮🇳 India. All the best for your dedication to Maths and teaching skills.
I always find it incongruous (pardon the pun) that when using the congruence relation one always states the modulus explicitly pretty much each time, but when using the [x] equivalence class notation, the modulus is rarely stated except as an overall context to a whole bunch of math, rather than, say, having it be a subscript to the [x] syntax e.g. [x]_n.
Wouldn't the "equivalence relation" thing be much shorter by using the "congruent when having the same remainder when dividing" proven just before?! Any relation based on "having the same something" is an equivalence relation because "being the same" is one, trivially!
-1(mod 4) is congruent to 3(mod 4). The set covers the integers if there are 4 terms and the terms are congruent to 0(mod 4), 1(mod 4), 2(mod 4), and 3(mod 4)
@@whiskymac3103 Thanks. I can see now that by definition its completely correct -1-3=-4 (divisible by 4) this -1 congruent to 3 mod 4. What got me confused is that I don't understand modulo with negatives.
For the last exercise, you need to calculate some successive factorials mod n, that's fairly easy to do, considering that k! is congruent to k (k-1)! (mod n), so you just take the previous factorial that you already calculated mod n and multiply by k, and try to reduce large numbers to their negative (mod n) which will make it much easier. For example 3! + 4! = 6 + 4! ≡ -1 - 4 (mod 7) ≡ 2 (mod 7)
around 20:50 you claim 7=3(mod 4) and 2 divides 4 so 7=3(mod 2). However, 3 can't be mod 2 since it can only be 0 or 1 and 7 = 1(mod 2). Of course we can go a further step and reduce 3(mod 2) to 1 (mod 2). d dividing n partitions the remainders into larger equivalence classes. e.g. 5 = 1(mod 4) but is also 1 (mod 2) so 5 is then equivalent to 7. Anyway, seems odd (no pun intended) that you just left it as 3(mod 2) w/o further comment.
You're confusing the remainder from the division algorithm with congruence (mod n). Computer programming calls the operator the produces the remainder "mod", but the math notation is about two numbers having the same remainder, and is not an operator at all: you put (mod n) at the right end of a line to say that all your triple equals signs on that line mean that the two sides have the same remainder from division by n.
@@cinemonini those are unlisted but can be seen thru the playlists but people usually don't look up for the playlists so yeah less views until they are listed
23:17 End of the proof left for the viewer
25:32 Homework
25:35 It should be 111 ≡ 0 (mod 37)
26:26 Good Place To Stop
Three times 3 is nine and seven times 3 ends in one. You're just being picky.
@@terryendicott2939 😂what
@@terryendicott2939 accuracy is not the same as pickiness in maths. 91 is not congruent to 0 modulo 37. If someone were to try to show that it is then they would have an awful lot of trouble since it is incongruent. A proof is a proof, not an approximation.
At 23:17, proof of the following statement: If a ≡ b (mod n), then a^m ≡ b^m (mod n), m∈ℕ
Suppose a ≡ b (mod n)
⇒ a - b = nk, for some k∈ℤ
⇒ a = nk + b
⇒ a^m = (nk + b)^m
Using the binomial expansion, we get
a^m = (m 0)*(nk)^m + (m 1)*(nk)^(m-1)*b + … + (m m)*b^m, where (x y) means x choose y.
If we reduce the equation mod n, all of the terms on the RHS reduce to (m m)*b^m (mod n), since every term containing an n is ≡ 0 (mod n).
Also in the video it is proven that if a ≡ b (mod n) and c ≡ d (mod n), then a + b ≡ c + d (mod n).
Using this fact, we get that a^m ≡ (m m)*b^m (mod n), but we know (m m) = 1
⇒ a^m ≡ b^m (mod n).
Q.E.D.
Please correct me if my proof is wrong.
he proved the multiplication though so exponentiation is just doing that a bunch of times if the exponent is a natural number
Idk
you're my new teacher and figurative father figure.
Idem
fff
Professor Michael Penn, this is a solid and well-organized video/lecture on Modulo Arithmetic in Number Theory Eight. These mathematical topics has been around forever.
Thank you so much for making this, I like number theory problems a lot, I watch a lot of those you post on your channel, and while I was able to understand the concept of modular arithmetic by watching those videos mostly some things I always wondered about. I was hoping you would make a video explaining all this
Hi Michael, great series.
I was recently studying number theory independently (with the help of your old series among other things) and I came across a beautiful fact I suggest you include in the current series : the equivalence of CRT and Lagrange interpolation.
#suggestion
Does CRT mean the Chinese remainder theorem? If so, how is it equivalent to Lagrange interpolation? That sounds cool
Bro's a magician when it comes to explaining mathematics to dumb kids like me.
Wish you speedy recovery from the ailment and surgery Mike. With the best wishes from 🇮🇳 India.
All the best for your dedication to Maths and teaching skills.
The property that ab (mod n) is congruent to ( a mod n) (b mod n) is widely used, but not mentioned in your series.
I like the art on his t-shirt, we really need someone who will save the earth from anyone who will harm it.
I always find it incongruous (pardon the pun) that when using the congruence relation one always states the modulus explicitly pretty much each time, but when using the [x] equivalence class notation, the modulus is rarely stated except as an overall context to a whole bunch of math, rather than, say, having it be a subscript to the [x] syntax e.g. [x]_n.
last question . I got = 5 mod (7) and 13 mod(25)
Me too
+1
great job! That's a really nice property :)
The 1st question of the warm up is wrong, I think.
yes, but I think it's wrong on purpose. There should be said "state wether the followings are true"
27 equiv 5 (mod n) -->
22 equiv 0 (mod n) -->
n | 22 ---> n in {1, 2, 11, 22}
But we can ignore 1 and 2 as the have no remainder 5. So n=11 or 22.
Can’t ignore 1 and 2 since the presence of remainder is not a requirement for congruence
@@Zoulou602 true
Can you proof that every combination and permutation is an integer?
Warning: listening to this with headphones on causes motion sickness.
lol
Your lectures and problems always interesting, inspiring, rigorously proven, very useful, informative, beautiful and pleasantly unpredictable.
We could go much further and give examples about cyclic groups and such structures.
Wouldn't the "equivalence relation" thing be much shorter by using the "congruent when having the same remainder when dividing" proven just before?! Any relation based on "having the same something" is an equivalence relation because "being the same" is one, trivially!
What did you do to your arm?
16:35 it is unclear how the set {-2,-1,0,1} give enough remainders mod 4 to cover the integers. The set of [3] is missing.
-1(mod 4) is congruent to 3(mod 4). The set covers the integers if there are 4 terms and the terms are congruent to 0(mod 4), 1(mod 4), 2(mod 4), and 3(mod 4)
@@whiskymac3103 Thanks. I can see now that by definition its completely correct -1-3=-4 (divisible by 4) this -1 congruent to 3 mod 4.
What got me confused is that I don't understand modulo with negatives.
Greetings proffesor, great class!..
thanks!
Sir for warm up exercise answer for question 2nd is n=2and 11 right???
well that should be all the divisors of 22, therefore 1,2,11 and 22
For the last exercise, you need to calculate some successive factorials mod n, that's fairly easy to do, considering that k! is congruent to k (k-1)! (mod n), so you just take the previous factorial that you already calculated mod n and multiply by k, and try to reduce large numbers to their negative (mod n) which will make it much easier. For example 3! + 4! = 6 + 4! ≡ -1 - 4 (mod 7) ≡ 2 (mod 7)
Watching from Nigeria!
oof hope your hand is ok!
What happened to your hand? :(
Dupuytren's contracture surgery
He was falling and saw the ground rushing towards him and thought that's not a good place to stop so put his hand out and it wasn't great.
Some conjecture
@@samharper5881 😂😂
@@goodplacetostop2973 Feel better soon
around 20:50 you claim 7=3(mod 4) and 2 divides 4 so 7=3(mod 2). However, 3 can't be mod 2 since it can only be 0 or 1 and 7 = 1(mod 2). Of course we can go a further step and reduce 3(mod 2) to 1 (mod 2). d dividing n partitions the remainders into larger equivalence classes. e.g. 5 = 1(mod 4) but is also 1 (mod 2) so 5 is then equivalent to 7. Anyway, seems odd (no pun intended) that you just left it as 3(mod 2) w/o further comment.
You're confusing the remainder from the division algorithm with congruence (mod n). Computer programming calls the operator the produces the remainder "mod", but the math notation is about two numbers having the same remainder, and is not an operator at all: you put (mod n) at the right end of a line to say that all your triple equals signs on that line mean that the two sides have the same remainder from division by n.
@@iabervon ok thanks. Yes it is about congruence. My bad.
MMO 1988 GB?
Hi why it has so less views
I think it might not have been public. I just got a notification now, two days after you wrote this comment.
@@iooooooo1 ohhh
@@iooooooo1 you can get every video in a playlist of number theory
@@cinemonini those are unlisted but can be seen thru the playlists but people usually don't look up for the playlists so yeah less views until they are listed
Because this is not what usually kids watch..?
nice
🎁🎁🎁🎁