I have tried numerous times to understand the Chinese Remainder Theorem to no avail. This explanation, however, was so simply put and made it all "click". Thank you!
It's not super easy; don't feel bad. Grab a random number of objects and try to arrange them into rows. If they fit into even rows of 3, 4, and 5, with 2, 2, and 1 remaining (respectively), you have a physical analog of this problem. This works nicely, in general, for solving any problem of this type, but has drawbacks.
I have been trying to understand this for hours and this is the only video that I have found so far that actually made it make sense, especially the part about simplifying it down to 1mod first and then turning it into what you need, thank you
I'm taking discrete mathematics and probability theory at UC Berkeley (CS 70). Your explanation of the Chinese Remainder Theorem is far superior to everything I have heard so far. Well done!
Just wanted to say thanks for making this, quite easy to pick up on and very well explained. This saved my ass twice this year, so you should know your videos are well appreciated.
Good job, sir. This explanation does leave out some understanding of why exactly this works, but will certainly work for those who simply want to be able to go through the motions with the CRT.
You can do that and that's what I did too. It works, but probably the reason why he said that is because by going to 1 (mod whatever) you are finding the inverse and there are methods for finding the inverse. It's much more helpful to do that for really large numbers, and that's what he should have explained.
Indeed, Angel is correct. Calculating the multiplicative inverse modulo n is much, much more efficient than brute forcing it for many scenarios with larger numbers. This is what he was referencing with the Extended Euclidean Algorithm comment.
You indeed can, just like the comment replies above also say, because it's easier to have a standard operation than guess, especially at large numbers. But your method indeed works, which gives x= (20+30+36) = 86. As you can see, 86 is also in the set of solutions. Since 26 is also one of the solution, I believe means that you could have multiplied any of the other solutions by a smaller solution.
I've read Strayer, Rosen, and watched Michael Penn's CRT videos and none of them presented the subject in as practical a way as you did here. Excellent job, dude.
For small numbers, like this problem, you can go directly to, in this case, 2. For larger numbers you need to go via 1. Watch towards the end of the video where I explain.
Farah, from my personal experience before watching this video, and with my improved understanding afterward: it depends on you personally. As he says in the video, he was sort of using trial and error. You can skip to the correct number if you know off hand that it'll give you the modulus you want is what it boils down to. That number will be larger than or equal to 2 and less than the number you're trying to get the modulus for. So, since we were getting (mod 4) it would either be 2 or 3. And you can use basic math to know that 3 * 2 is 6 which is 2 (mod 4). But, if you're dealing with say (mod 14), maybe you have those numbers memorized, maybe you don't, but your options are from 2 - 13 and trial and error isn't going to work out so hot for you if you don't already know what numbers are going to give you what answer. If you do, then even up to (mod 14) you can just mental math it. Otherwise, it'll be easier to aim for 1 (mod 14). BTW the number right below the modulus squared will always be 1 (mod x). So, for 14, if you have 13 (mod 14), you can multiply it by 13 and get 1 (mod 14). Tl;dr: There's a couple other tricks, but the point is, the answer to your question is that it varies based on you. And as you'll also notice, even that trick, while easier, still can get pretty hard with bigger numbers, so eventually, you'll want to settle for the Extended Euclidean Algorithm (which is easier if you've done the Euclidean algorithm [ which is easy])
@@Farah-vi2cj Note there is a shortcut (relative to the extended euclidean algorithm) using exponentiation for finding the inverse IF the mod is prime (3 and 5 in this case). The inverse of x is x ^ (p-2) (mod p). This works well for large numbers -- although you need yet another algorithm to tell if a large number is prime (search "primality test")! So for large numbers, such as those used by cryptography (typically around 78 decimal digits), it's probably best to just go ahead and use the EEA every time.
Thanks so much! I was looking at some examples online but none made as much sense as this. I also checked the recent comments and saw you're still replying 8 years later, so props to you :)
Another great explanation - this is a fantastic resource. RH is a great educator, someone who breaks it down simply for students, rather than some academics who seem to take pleasure in showing how clever they are by describing things in a complex way!
thank you for such a great explanation. I was able to write a program in c++ after watching this video. The best part was introducing modular multiplicative inverse at the last moment so that anyone can understand easily without knowing extended euclid algorithm.
what if the x has coeffecients to solve? Like i have this question that goes: 2x congruent 6 mod 14 3x congruent 9 mod 15 5x congruent 20 mod 60 Just confused a little bit, anyways the video was very helpful thank you!
In this case you can divide the first equation by 2 to get x congruent to 3 mod 7 (you might like to prove that it is ok to do this). Do the same for the other equations and then use my video.
Found 2000 years ago? Was it also proved 2000 years ago? Or was it proved later? Thanks for the video. Your videos are very clear and concise and this one helped me complete a task for my Master's Degree.
Glad the videos are helping with your degree. The theorem was not proven 2000 years ago. It took longer. Have a look at Chinese Remainder Theorem and go to the history section as a starting point.
Good lord thank you so much, I spent hours trying to figure out a simple way to do this, and I found this video just in time for my linear algebra exam tomorrow.
+Mystical Miner Yes I did mean to say 146. At around 5:43 you should see an annotation `I say 142. I mean 146'. It's on the left hand side. If you can't see the annotation please let me know.
Hi, Your video was very helpful but I had a query. Was hoping you could help out. When solving for the mod 4 section of the problem(at about 04:25), you first reduce the remainder to 1 then multiply by 2 instead of trying to directly get 2. Is there any particular reason for that besides it being an easier way to process it?
For small numbers you can go directly to, in this case, 2. For larger numbers you need to go via 1. Watch towards the end of the video where I explain.
thank you very much , you are a talented teacher , and you are a man of your word you wrote in the title chineasetheorem made easy , and you kept your promise , coz your explanation was very clear and you did it skilllfully !!!
Definitivamente mucho mejor que la versión en español. Whatever, I really appreciate you made this video in both languages and, in general, the way you explain math is excellent, he aprendido mucho viendo tus videos :)
Yet is the easiest and simplest explanation I have ever come across. Thank you. By the way I just wonder what your targeting audiences are. I absolutely love all of you videos. Thank you
Man la Thanks very much for the positive feedback. The `made easy' videos are mainly for 1st and 2nd yr university/college. The `how things work' videos are for everyone. The other videos are mainly for high school students although anyone interested in mathematics might find them interesting. Thanks again.
I really appreciate the video that you made here. This is just amazing. I am reading Elementary Number Theory by David M. Burton and I got stuck here. The book is amazing but it fails to do justice to the Chinese Remainder Theorem. This video is simply amazing. May god bless your soul.
ThisIsTheTrue word In some ways my videos are not suited to generating lots of subs... a new video on say, line integrals made easy, is not going to be published at the right time for most people. But I am very pleased that I have over 200,000 views and many of my videos are top in a youtube search of the topic. Thanks for the comment.
yeah. less people come here to learn something, people are more into lame pranks and stuff. but as a math lover i must say, the way you are representing and clearing things is outstanding. keep up the good work!
At around 4:06, why can't you just multiply by 2? 3*2=6, which is 2 mod 4. This would make the answer 86. However at the end, the answer is 26 mod 60, which both 146 and 86 satisfy.
For large moduli you will not be able to use trial and error. You will need to get to your answer via the inverse, using the extended Euclidean algorithm. This is why I suggest at 4 min 30 that you do the calculations in 2 stages. Also see my comments at the end of the video.
video is awesome. It's 3:30 a.m. so I'm gonna watch your extended euclidean video tomorrow but before I go just wanted to ask: You say that finding the inverse is hard when the numbers are big. At the end you give the example: 11y = 1(mod 7171) Can't you just say: 1.) 11n = 7172 2.) n = 652 3.) 11(652) = 1(mod 7171) ??? All the "="s are meant to be congruences of course.
mmmmSmegma Thanks for the extremely positive feedback. Here is another example of what I was trying to say. Try finding the inverse of 7 modulo 1,000,001 with trial and error; it takes a long time. But with the Extended Euclidean algorithm is can be done very quickly.
the numbers shown in the video is not so large as compared to the problem define above. So if such problem comes up them how to solve it? Please explain :)
+Gyanendro Loitongbam Everything works in the same way. It's hard to explain well in these comments but I'll try to explain. First we check that the gcd of 7919 and 12553 is 1. To do this use the Euclidean algorithm. Then repeat for the gcd of 12553 and 17389. Then finally for 7919 and 17389. This will show that the gcd of any of the two modulos are 1. So we can use the Chinese remainder theorem . Next set up x = 17389(12553) + 7919(17389) + 12553(17389) like I do in the video. Consider the first part. We have 17389(12553) modulo 7919. So x= 4801 mod 7919. We need to multiply by the inverse of 4801. To find this use the extended Euclidean algorithm to see that 4801(3736)-2265(7919)=1. So the inverse is 3736. So the first part is now x=3736(4801). Modulo 7919 this will give 1 but we want 3346. So our first part is 3346(3736)(4801). Now repeat for the middle part (i.e. modulo 12553) and the final part (i.e. mod 17389). Add up the three parts and this will be the answer modulo 7919(12553)(17389).
fair dinkum how'd you know haha I love how you cut through the crap and get straight to the gist. Have you thought about doing a video on modular exponentiation, for stupid big numbers? I think it's something that boggles a lot of people, but if you can have it explained simply, its perfectly doable.
If you go to my video Hamming code made easy there is a question about 2 years ago about something like what is 7^7^7^..... mod 5. You might find that interesting. Also have a look at my video The largest number which has served any useful purpose in mathematics.
Question: why does 15 need to be multiplied by 3? Having that term be 30=15.2 lands you 86, which is a correct answer. Why not just observe that 30=2mod4 and call it good? Loved the video, btw.
Hi Alexander, trial and error works well for small numbers. If you are given a problem with larger numbers in an exam your method will likely take too long. See my reply (below) to Berat Amil Berber 10 months ago, who asked the same question.
Thanks for a really clear explanation of this. Just to check I am not losing my mind: around 5'40'' in when you say "equivalent to 142 mod 60" this was a slip of the tongue right? you surely meant 146 mod 60 (which is of course really 26 mod 60)?
I have tried numerous times to understand the Chinese Remainder Theorem to no avail. This explanation, however, was so simply put and made it all "click". Thank you!
It's great to hear when one of my videos makes it all ``click''. Thanks for letting me know.
i still dont understand
It's not super easy; don't feel bad.
Grab a random number of objects and try to arrange them into rows.
If they fit into even rows of 3, 4, and 5, with 2, 2, and 1 remaining (respectively), you have a physical analog of this problem.
This works nicely, in general, for solving any problem of this type, but has drawbacks.
I have been trying to understand this for hours and this is the only video that I have found so far that actually made it make sense, especially the part about simplifying it down to 1mod first and then turning it into what you need, thank you
Jordan Shepardson I'm glad it helped so much.
I'm taking discrete mathematics and probability theory at UC Berkeley (CS 70). Your explanation of the Chinese Remainder Theorem is far superior to everything I have heard so far. Well done!
Glad you liked it. I have a few other discrete mathematics videos you might find useful (th-cam.com/users/randellheyman). Good luck at Berkeley.
studying for the 70 final right now and im fucking dying lmao 100% agree
@@64_bit80 studying for the summer 70 quiz rn LOL
taking cs70 now and my brain is exploding LMAOO
cs70 fall '24 midterm here
Just wanted to say thanks for making this, quite easy to pick up on and very well explained. This saved my ass twice this year, so you should know your videos are well appreciated.
Good job, sir. This explanation does leave out some understanding of why exactly this works, but will certainly work for those who simply want to be able to go through the motions with the CRT.
Why not directly from 3(mod 4) to 2(mod 4) ? Can't we multiply the former by 2 and make that happen ?
You can do that and that's what I did too. It works, but probably the reason why he said that is because by going to 1 (mod whatever) you are finding the inverse and there are methods for finding the inverse. It's much more helpful to do that for really large numbers, and that's what he should have explained.
Indeed, Angel is correct. Calculating the multiplicative inverse modulo n is much, much more efficient than brute forcing it for many scenarios with larger numbers. This is what he was referencing with the Extended Euclidean Algorithm comment.
Also in this case 3 is congruent to -1 (mod 4), and therefore it is its own inverse, so it does not require any guessing nor algorithms to find
You indeed can, just like the comment replies above also say, because it's easier to have a standard operation than guess, especially at large numbers. But your method indeed works, which gives x= (20+30+36) = 86. As you can see, 86 is also in the set of solutions. Since 26 is also one of the solution, I believe means that you could have multiplied any of the other solutions by a smaller solution.
When the "made easy" video is too hard to understand too. It's like the draw an owl meme.
The most clear and structural explanation without just using the usual steps without reason like other videos!!! Thank you !😇
Thanks. Appreciate such positive feedback.
I've read Strayer, Rosen, and watched Michael Penn's CRT videos and none of them presented the subject in as practical a way as you did here. Excellent job, dude.
Thanks for commenting. It is always pleasing to know that someone has found one my videos useful.
To get 2(mod4) from 3(mod4) you need only have multiplied by 2.
3*2=6=2(mod4)
15*2=30=2(mod4)
There was no need to first multiply by 3
For small numbers, like this problem, you can go directly to, in this case, 2. For larger numbers you need to go via 1. Watch towards the end of the video where I explain.
what falls into the category of "big" numbers? when do i know that i need to first go to the 1st remainder?
Farah, from my personal experience before watching this video, and with my improved understanding afterward: it depends on you personally. As he says in the video, he was sort of using trial and error. You can skip to the correct number if you know off hand that it'll give you the modulus you want is what it boils down to. That number will be larger than or equal to 2 and less than the number you're trying to get the modulus for. So, since we were getting (mod 4) it would either be 2 or 3. And you can use basic math to know that 3 * 2 is 6 which is 2 (mod 4). But, if you're dealing with say (mod 14), maybe you have those numbers memorized, maybe you don't, but your options are from 2 - 13 and trial and error isn't going to work out so hot for you if you don't already know what numbers are going to give you what answer. If you do, then even up to (mod 14) you can just mental math it. Otherwise, it'll be easier to aim for 1 (mod 14). BTW the number right below the modulus squared will always be 1 (mod x). So, for 14, if you have 13 (mod 14), you can multiply it by 13 and get 1 (mod 14).
Tl;dr: There's a couple other tricks, but the point is, the answer to your question is that it varies based on you.
And as you'll also notice, even that trick, while easier, still can get pretty hard with bigger numbers, so eventually, you'll want to settle for the Extended Euclidean Algorithm (which is easier if you've done the Euclidean algorithm [ which is easy])
@@Farah-vi2cj Note there is a shortcut (relative to the extended euclidean algorithm) using exponentiation for finding the inverse IF the mod is prime (3 and 5 in this case). The inverse of x is x ^ (p-2) (mod p). This works well for large numbers -- although you need yet another algorithm to tell if a large number is prime (search "primality test")! So for large numbers, such as those used by cryptography (typically around 78 decimal digits), it's probably best to just go ahead and use the EEA every time.
Literally a better explanation than my pointlessly expensive university courses. Thank you.
Thanks for the nice comment
Thanks so much! I was looking at some examples online but none made as much sense as this. I also checked the recent comments and saw you're still replying 8 years later, so props to you :)
Thanks.
This makes perfect sense. Excellent repetition before exam compared to just staring at the formulas.
Thanks for the thoughtful feedback.
Another great explanation - this is a fantastic resource. RH is a great educator, someone who breaks it down simply for students, rather than some academics who seem to take pleasure in showing how clever they are by describing things in a complex way!
Thanks for the positive feedback.
out of every video I've had to watch to understand my math classes so far, this was one of the most helpful
Thanks. I appreciate you letting me know. Lots of other math videos at th-cam.com/users/randellheyman
Randell Heyman next time I'm trying to find help I'll look through your channel first :)
Can you stop talking from behind me?
Thanks, man! Taking an online class and didn't quite understand what the instructor was saying. This video helped out a ton!
I'm glad it helped.
This was awesome, there needs to be more math videos like this
Bloody Brilliant!! I'm sure your Math Prof would be extremely proud of you :D!
extremely informative content out here, would've never figured out how it worked if not your help. Thanks you
Thanks for commenting. Great to hear that my 10 year old video is still helping people.
Bless this man
thank you for such a great explanation. I was able to write a program in c++ after watching this video. The best part was introducing modular multiplicative inverse at the last moment so that anyone can understand easily without knowing extended euclid algorithm.
Md kaif Khan Thanks for the comment. There is a video of mine on modular inverse if you ever need it.
what if the x has coeffecients to solve?
Like i have this question that goes:
2x congruent 6 mod 14
3x congruent 9 mod 15
5x congruent 20 mod 60
Just confused a little bit, anyways the video was very helpful thank you!
In this case you can divide the first equation by 2 to get x congruent to 3 mod 7 (you might like to prove that it is ok to do this). Do the same for the other equations and then use my video.
@@RandellHeyman oh thank you!
Thank you sir, the explanation made complete sense, kinda surprising how this theorem is found like hundreds of years ago :O
Yes. About 2,000 years old and it's still true!
Found 2000 years ago? Was it also proved 2000 years ago? Or was it proved later? Thanks for the video. Your videos are very clear and concise and this one helped me complete a task for my Master's Degree.
Glad the videos are helping with your degree. The theorem was not proven 2000 years ago. It took longer. Have a look at Chinese Remainder Theorem and go to the history section as a starting point.
My source says posed by Sun Tzu in 3rd century CE, and solved by the 6th century CE, as they were using it to help calculate positions of planets.
Thank you! Thank you! Thank you! Made learning how to use this theorem for my assignment so much easier! :D
Great video which actually explains it better than any professor or textbook would!
Thanks.
The explanation was very lucid.Thanks a lot!
Very well explained thank you. For the life of me I don't get why textbooks can't put things as simply.
Good lord thank you so much, I spent hours trying to figure out a simple way to do this, and I found this video just in time for my linear algebra exam tomorrow.
+Umar Akhtar Thanks. It is nice to hear from people I have helped. Good luck with the exam.
Wow, this is so simple. I had mod 7, mod 13, mod 16. All I had to do was use the first step you showed us and obtained 411 after adding them up.
+Hong W Glad it helped!
Lovely explanation, the moment you started explaining the first bit ( using product of remaining numbers for each term ), everything became clear.
Thanks for the positive feedback.
At 5:53 Did you mean to say 146? If you meant 142, then how did you end up getting that? By the way, this was very very helpful, thanks so much!
5:43*
+Mystical Miner Yes I did mean to say 146. At around 5:43 you should see an annotation `I say 142. I mean 146'. It's on the left hand side. If you can't see the annotation please let me know.
I was getting crazy trying to figure out where did 142 came from.
This is great video. It's really intuative and easy to follow. Most other explanations make it seem a lot more complicated then it actually is.
Thanks for feedback.
Hi, Your video was very helpful but I had a query. Was hoping you could help out. When solving for the mod 4 section of the problem(at about 04:25), you first reduce the remainder to 1 then multiply by 2 instead of trying to directly get 2. Is there any particular reason for that besides it being an easier way to process it?
For small numbers you can go directly to, in this case, 2. For larger numbers you need to go via 1. Watch towards the end of the video where I explain.
thank you very much , you are a talented teacher , and you are a man of your word
you wrote in the title chineasetheorem made easy , and you kept your promise ,
coz your explanation was very clear and you did it skilllfully !!!
Round of Applause to this man for explaining CRT
Thanks for the positive feedback
Mr. Heyman, you just saved me hours of precious time!
Definitivamente mucho mejor que la versión en español. Whatever, I really appreciate you made this video in both languages and, in general, the way you explain math is excellent, he aprendido mucho viendo tus videos :)
+Mate Profe Luis Felipe Thanks, I am better at mathematics than Spanish!
That was super-easy to follow! Thank you.
Thanks for the positive feedback.
Fantastic, I've seen this method on other videos but no good explanations as clear as this! thanks!
Very good explanation. I never bothered to know the intuition behind crt but this video explains it perfectly.
Yet is the easiest and simplest explanation I have ever come across. Thank you. By the way I just wonder what your targeting audiences are.
I absolutely love all of you videos. Thank you
Man la Thanks very much for the positive feedback. The `made easy' videos are mainly for 1st and 2nd yr university/college. The `how things work' videos are for everyone. The other videos are mainly for high school students although anyone interested in mathematics might find them interesting. Thanks again.
Joyful how easy you made this. Thanks!
Glad it was helpful!
Thanks a lot! I never did got it until now
It's very pleasing when someone finally gets one of these great mathematical theorems.
Ohh thanks.... It was really useful for revising my ISI exam tomorrow.... :)
+Subham Chakravarti good luck !
Wow. Excellent explanation. Made it quite easy.
Thanks. I have lots of other videos on Modular inverse, Euler's theorem, Finite fields, Modular exponentiation etc.
Thank you. You just saved my Discrete Mathematics grade.
Thanks. I'm glad you will get through Discrete Mathematics.
Loved it, you hacked it completely.
thank you so much....you showed the way for finding solution ,simultaneously giving reasons for why we are doing the steps....appreciate your work!!👌👌
Thanks Aayush.
A nice way to explain.
You may give a more compact tabular solution, seems logical.And thank you again.
Thanks for the comment
Oh god it's so simple now, thank you very much !!!
Wow!! phenomenal explanation making this crystal clear!
Thank you so much. I felt like I was about to figure it out myself, but this really helped me get the last of it.
Nice explanation. Much less headache-inducing than Wikipedia!
Great !!! The best explanation I found !!! Thanks a lot !!!
Thank you for this video! It helped me get past a block in my thinking.
This video might be 6 years old, but it is amazing! Thank you so much!
Thanks. More of my videos at th-cam.com/users/randellheyman
I really appreciate the video that you made here. This is just amazing. I am reading Elementary Number Theory by David M. Burton and I got stuck here. The book is amazing but it fails to do justice to the Chinese Remainder Theorem. This video is simply amazing. May god bless your soul.
Thanks.
absolutely clear description
thanks a lot
Sir your video was super super easy to understand.its neat and clean.keep up the good work.
shubham singh thanks.
you made it easy indeed, thanks for the explanation.
Thanks a lot for this video. You're a saviour
Expert and clear explanation- thank you.
Glad it helped. I wish there had been a video like mine when I was studying the Chinese Remainder Theorem!
Nice explanation. I finally understood the logic. Thanks :)
That is very intuitive! thanks a lot !
I'm glad it helped you.
Thank you so much! You're video was very clear and direct.
Clear and succinct. Thank you very much.
Thank you for making the video! saves me lots of time
I'm glad it helped.
can you redo the sound for this video please. I understand it's from 2013 but this is such a great video even today
you deserve more subs!
ThisIsTheTrue word In some ways my videos are not suited to generating lots of subs... a new video on say, line integrals made easy, is not going to be published at the right time for most people. But I am very pleased that I have over 200,000 views and many of my videos are top in a youtube search of the topic. Thanks for the comment.
yeah. less people come here to learn something, people are more into lame pranks and stuff. but as a math lover i must say, the way you are representing and clearing things is outstanding. keep up the good work!
Awesome, learnt how to do this now. Pretty cool vid.
i know this is an older video, but it was super helpful. thanks for the great explanation!
X = 60t + 26 ; cong = congruent
X cong (2 mod 3) --> X = 3m + 2 ; (3m + 2) cong (2 mod 4) --> 2 cancels out --> 3m cong (0 mod 4) --> X = 4*(3m) + 2 = 12m + 2
(12m + 2) cong 1 mod 5 --> 12m cong (-1 mod 5) = 12m cong (4 mod 5) --> m cong (inverse of 12 * 4 mod 5)
inverse of 12 cong 1 mod 5
Using the extended Euclidean's algorithm:
i) 12 = 5(2) + 2 --> 1 = 5 - 2(2)
ii) 5 = 2(2) + 1 1 = 5 - (2)[12 - 5(2)]
iii) 2 = 1(2) + 0 1 = 5(5) - 2(12) therefore, inverse of 12 = -2 which is congruent to 3 mod 5
Now, m cong (3 * 4 mod 5) = m cong (12 mod 5) = 2, therefore m = 2
m = 5t + 2 --> X = 12(5t + 2) + 2 --> X = 60t + 26
t 0 1 2 3 4 5 6 7 8 9 10 ...
X 26 86 146 206 266 326 386 446 506 566 626 ....
At around 4:06, why can't you just multiply by 2? 3*2=6, which is 2 mod 4. This would make the answer 86. However at the end, the answer is 26 mod 60, which both 146 and 86 satisfy.
For large moduli you will not be able to use trial and error. You will need to get to your answer via the inverse, using the extended Euclidean algorithm. This is why I suggest at 4 min 30 that you do the calculations in 2 stages. Also see my comments at the end of the video.
OMG THIS WAS AMAZING, it was easy to follow and understand, and i like that
video is awesome. It's 3:30 a.m. so I'm gonna watch your extended euclidean video tomorrow but before I go just wanted to ask: You say that finding the inverse is hard when the numbers are big. At the end you give the example: 11y = 1(mod 7171)
Can't you just say:
1.) 11n = 7172
2.) n = 652
3.) 11(652) = 1(mod 7171) ???
All the "="s are meant to be congruences of course.
mmmmSmegma Thanks for the extremely positive feedback. Here is another example of what I was trying to say. Try finding the inverse of 7 modulo 1,000,001 with trial and error; it takes a long time. But with the Extended Euclidean algorithm is can be done very quickly.
So clear! THANK YOU SO MUCH
Glad it helped. Lots of videos on other subjects in the made easy playlist at th-cam.com/users/randellheyman
Superb Lecture..:)
BTW how to find for large no. eg
x = 3346 (mod 7919)
x = 2096 (mod 12553)
x = 730 (mod 17389)
+Gyanendro Loitongbam There should be no problems using what is shown in the video for large numbers.
the numbers shown in the video is not so large as compared to the problem define above. So if such problem comes up them how to solve it? Please explain :)
+Gyanendro Loitongbam Everything works in the same way. It's hard to explain well in these comments but I'll try to explain. First we check that the gcd of 7919 and 12553 is 1. To do this use the Euclidean algorithm. Then repeat for the gcd of 12553 and 17389. Then finally for 7919 and 17389. This will show that the gcd of any of the two modulos are 1. So we can use the Chinese remainder theorem .
Next set up x = 17389(12553) + 7919(17389) + 12553(17389) like I do in the video.
Consider the first part. We have 17389(12553) modulo 7919.
So x= 4801 mod 7919.
We need to multiply by the inverse of 4801. To find this use the extended Euclidean algorithm to see that
4801(3736)-2265(7919)=1. So the inverse is 3736. So the first part is now
x=3736(4801). Modulo 7919 this will give 1 but we want 3346. So our first part is 3346(3736)(4801).
Now repeat for the middle part (i.e. modulo 12553) and the final part (i.e. mod 17389).
Add up the three parts and this will be the answer modulo 7919(12553)(17389).
thank you so much I got it... Thumbs up!!!
+Randell Heyman how did you get x= 4801 mod 7919? and why multiply by the inverse of 4801?
Very helpful and easy to understand. Thanks!
Thank you! Very clear and simple :)
love your work mate: bloody brilliant
Chris Swan Thanks for the feedback. Australian?
fair dinkum how'd you know haha
I love how you cut through the crap and get straight to the gist.
Have you thought about doing a video on modular exponentiation, for stupid big numbers?
I think it's something that boggles a lot of people, but if you can have it explained simply, its perfectly doable.
If you go to my video Hamming code made easy there is a question about 2 years ago about something like what is 7^7^7^..... mod 5. You might find that interesting. Also have a look at my video The largest number which has served any useful purpose in mathematics.
Thank's a lot ! I have a math contest tomorrow and this will help me a lot !
I'm glad it helped.
I finally understand it. Thanks!
Question: why does 15 need to be multiplied by 3? Having that term be 30=15.2 lands you 86, which is a correct answer. Why not just observe that 30=2mod4 and call it good? Loved the video, btw.
Hi Alexander, trial and error works well for small numbers. If you are given a problem with larger numbers in an exam your method will likely take too long. See my reply (below) to Berat Amil Berber 10 months ago, who asked the same question.
Best explanation so far.
Thanks. I'm glad it helped you.
Thanks for a really clear explanation of this. Just to check I am not losing my mind: around 5'40'' in when you say "equivalent to 142 mod 60" this was a slip of the tongue right? you surely meant 146 mod 60 (which is of course really 26 mod 60)?
Yes. That's right. I think I edited in a comment on the video saying that.
Thank you so much, I’m here before my Midterm❤
Good luck with it.
Many thanks. This was very clear.
You are a life saver ! Thank you so much! :)
Thanks for the very positive feedback.
best explanation of this i've seen.
Thanks, appreciate you taking the time to let me know. Great that it's still helping people.
that was a amazing video , I had ever seen for this topic
Thanks for such positive feedback. I have a few recent videos on the CRT in my Corona help- Discrete Mathematics playlist.
Nice job good to understand!
It is a very good explanation.
Amazing video, really well explained 👍🏽
Great video, but the audio is horrendous
Thanks. A few people have pointed out the poor audio. I now have a Blue Yeti microphone. Seems to be a lot better on my recent videos.
awesome content, keep it up! lots of students really appreciate you
The audio terrifies me.
The best explanation! I finally get it :)
You made it easy. thanks !
Truly amazing! Thank you.
Very well explained, thank you !
Great video! Thank you!