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.
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.
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.
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!
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.
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.
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.
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.
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)?
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.
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.
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 :)
Hi, nice talk! Thanks! and I'd like to ask you some questions. Given a system of congruences of the form "x = a mod n" and after finding the CRT value x; in order to check the correctness, I think I can do "x mod n" to get back "a" values. For instance, in your example, 26 mod {3,4,5} would give us "a" numbers {2,2,1}. My question is, is this always true? I mean, if we find the solution "x" for the congruences, would we always get the exact "a" values by doing "x mod n"? For instance, I did an example for the system of congruences below: x = 21 mod 2 x = 245 mod 3 x = 198 mod 5 x = 245 mod 7 The solution that I found is x = 203. However, by doing (for example) "203 mod 2" I get 1, instead of 21. Similarly, for others congruences of the system above. I know that "21 mod 2" is 1, and "203 mod 2" is also 1. With 203, I can get the remainder of the congruences, but I'm not able to retrieve the values {21,245,198,245}. Am I missing something? Do you know a way to figure out those values from x? Thank you in advance, and I apologize for the long question. :)
Airton Ishimori You have started with 4 equations and the Chinese remainder theorem has given you a solution (really it's the proof of the theorem that gives you the solution but let's not be too picky). Since you start with the four equations there is no need to work them out. Another way of looking at your question is to realise that you would get the same solution with x=1 mod 2, x= 2 mod 3, x=3 mod 5 and x= 0 mod 7. One of my lecturers used to say that when you are working in, say, mod 2 then it's like putting on a pair of glasses that can't distinguish between odd and even numbers, When you look at 21 what you see through the glasses is 1. Hope that helps.
Randell Heyman Hi, I'm not sure if I totally understood you, but thanks for the response I look at the CRT more carefully. Many references that I've seen in the Internet, they present the CRT properties for the system of congurences of the type "x = a mod n", in which "n" values must be a pairwise coprime and "a" values may be any integer. However, to get what I've been trying to figure out, I guess "a < n" should always holds true for each pair (a, n) to retrieve "a" value from the solution "x". I'm not sure about this assertion and if this is true for all cases. I haven't seen this particularity (if I'm not missing any) in the many references that I took a look at, but in all of them "a" is always less than "n". Going back to my previous example, I changed the "n" values to a number bigger than any "a". So: x = 21 mod 271 x = 245 mod 277 x = 198 mod 281 x = 245 mod 283 The solution that I found for "x" is 2360196473. Now, I'm able to retrieve the exact number "a" by doing "x mod n" for each congruence. I think, I undertood when you said that there wasn't need to work them out. I'd like to thank you again. You really helped me. :)
You have to be very careful dividing. E.g. 4x=2 (mod 6) has solutions (such as x=2). Dividing by 2 gives 2x=1 (mod 6) which has no solutions. Better to think of division as multiplication by the inverse. So, in the example division by 2 = multiplication by the inverse of 2 modulo 6. But 2 has no inverse modulo 6, so you can't do it.
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.
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.
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.
Question sir. How do you know what number is going to be multiplied for example in 12, how is it to be multiplied by 3? And also for 15, and how is it multiplied by both 2 and 3?
I used trial and error to find the 3. I just tried various numbers until I got what I wanted. This works well for small numbers like in this problem. When the numbers are bigger we need to use another method. See my video Modular Inverse Made Easy which explains this other method.
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.
At around 5 minutes I have 20 36 and 90 being added. This gives 146 and then I go on to show that anything which has the same remainder when divided by 60 is also an answer.
I think without matrices? I think there are 2 ways of using chinese reminder theorem to solve system linear congruences, one way is using the method used in this video, another way is using back substitution. It is introduced in Discrete Mathmatics and its application(i think), but my professor asks me to use back substitution method to solve system linear congruences.
I'm just finishing one now on inclusion-exclusion principle. Then I could maybe do it. It's hard to think of a good title that will allow people to find it easily.
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.
The Chinese Remainder Theorem says that if the gcd of the modulii equals 1 then there will always be one answer modulo the product of the modulii. In the video the gcd of 3,4 and 5 equals 1 so there will be one answer modulo 60. By one answer I mean all numbers that are equivalent to 26 mod 60.
Yes. It should have 3 lines instead of 2. I wasn't that good using the animation software when I made this video. Equivalence signs have to be imported.
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).
Why not just multiply by 2 in the last step to go from 15=3 (mod 4) to 30=6=2 (mod 4)? I don't see the need to do this in 2 steps. The difference between 6x15 (your step) and 2x15 (my step) is, off course, zero (mod 60).
Great question John, for problems with small numbers that is fine. But for large numbers you will not have the time and/or inclination to use trial and error. To get an equivalence to 1 is simply working out the modular inverse. This can be done for large, even very large numbers quickly. See my video modular inverse made easy.
At 4:17, what's the point of doing it in two stages? You can go straight from 3 mod 4 to 2 mod 4 by multiplying by two to get 6 = 2 mod 4. Multiplying by three first is unnecessary and doesn't do anything to make it easier.
I explain this towards the end of the video. For problems with small numbers like in the video you can go straight to 2. But if the numbers are large you need to go via 1. This involves calculating an inverse for which we can use the extended euclidean algorithm. Watch to the end and if you still have problems ask me again.
What I dont understand is you multiply the x congruence 1 mod(4) by 2 where gcd (2 , 4) isnt 1. I thought it isnt allowed. But it still works though when I check it.
In general it is ok to add, subtract and multiply both sides of a congruence equation by a number n. But you need to be careful dividing. It is better to think of division by m as being multiplication by the inverse, if it exists, of m.
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 (ua-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.
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
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.
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.
This was awesome, there needs to be more math videos like this
This makes perfect sense. Excellent repetition before exam compared to just staring at the formulas.
Thanks for the thoughtful feedback.
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.
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.
Literally a better explanation than my pointlessly expensive university courses. Thank you.
Thanks for the nice comment
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 ua-cam.com/users/randellheyman
Randell Heyman next time I'm trying to find help I'll look through your channel first :)
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.
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.
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.
Bloody Brilliant!! I'm sure your Math Prof would be extremely proud of you :D!
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.
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.
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 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.
Thank you! Thank you! Thank you! Made learning how to use this theorem for my assignment so much easier! :D
The explanation was very lucid.Thanks a lot!
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.
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.
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.
Great video which actually explains it better than any professor or textbook would!
Thanks.
When the "made easy" video is too hard to understand too. It's like the draw an owl meme.
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!
Bless this man
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.
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.
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!
That was super-easy to follow! Thank you.
Thanks for the positive feedback.
Very good explanation. I never bothered to know the intuition behind crt but this video explains it perfectly.
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 !!!
Mr. Heyman, you just saved me hours of precious time!
Fantastic, I've seen this method on other videos but no good explanations as clear as this! thanks!
Joyful how easy you made this. Thanks!
Glad it was helpful!
Thank you for this video! It helped me get past a block in my thinking.
Oh god it's so simple now, thank you very much !!!
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.
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!
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.
Awesome, learnt how to do this now. Pretty cool vid.
Hi, nice talk! Thanks! and I'd like to ask you some questions.
Given a system of congruences of the form "x = a mod n" and after finding the CRT value x; in order to check the correctness, I think I can do "x mod n" to get back "a" values. For instance, in your example, 26 mod {3,4,5} would give us "a" numbers {2,2,1}. My question is, is this always true? I mean, if we find the solution "x" for the congruences, would we always get the exact "a" values by doing "x mod n"? For instance, I did an example for the system of congruences below:
x = 21 mod 2
x = 245 mod 3
x = 198 mod 5
x = 245 mod 7
The solution that I found is x = 203. However, by doing (for example) "203 mod 2" I get 1, instead of 21. Similarly, for others congruences of the system above. I know that "21 mod 2" is 1, and "203 mod 2" is also 1. With 203, I can get the remainder of the congruences, but I'm not able to retrieve the values {21,245,198,245}. Am I missing something? Do you know a way to figure out those values from x?
Thank you in advance, and I apologize for the long question. :)
Airton Ishimori You have started with 4 equations and the Chinese remainder theorem has given you a solution (really it's the proof of the theorem that gives you the solution but let's not be too picky). Since you start with the four equations there is no need to work them out. Another way of looking at your question is to realise that you would get the same solution with x=1 mod 2, x= 2 mod 3, x=3 mod 5 and x= 0 mod 7. One of my lecturers used to say that when you are working in, say, mod 2 then it's like putting on a pair of glasses that can't distinguish between odd and even numbers, When you look at 21 what you see through the glasses is 1. Hope that helps.
Randell Heyman Hi, I'm not sure if I totally understood you, but thanks for the response I look at the CRT more carefully. Many references that I've seen in the Internet, they present the CRT properties for the system of congurences of the type "x = a mod n", in which "n" values must be a pairwise coprime and "a" values may be any integer. However, to get what I've been trying to figure out, I guess "a < n" should always holds true for each pair (a, n) to retrieve "a" value from the solution "x". I'm not sure about this assertion and if this is true for all cases. I haven't seen this particularity (if I'm not missing any) in the many references that I took a look at, but in all of them "a" is always less than "n". Going back to my previous example, I changed the "n" values to a number bigger than any "a". So:
x = 21 mod 271
x = 245 mod 277
x = 198 mod 281
x = 245 mod 283
The solution that I found for "x" is 2360196473. Now, I'm able to retrieve the exact number "a" by doing "x mod n" for each congruence. I think, I undertood when you said that there wasn't need to work them out.
I'd like to thank you again. You really helped me. :)
Thank you. You just saved my Discrete Mathematics grade.
Thanks. I'm glad you will get through Discrete Mathematics.
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.
Hi, thanks for the vid.... can you answer, that if you correct a value by multiplying values, can we also divide?
You have to be very careful dividing. E.g. 4x=2 (mod 6) has solutions (such as x=2). Dividing by 2 gives 2x=1 (mod 6) which has no solutions. Better to think of division as multiplication by the inverse. So, in the example division by 2 = multiplication by the inverse of 2 modulo 6. But 2 has no inverse modulo 6, so you can't do it.
@@RandellHeyman thanks for your reply! I played around with it and got the concept :)
A nice way to explain.
You may give a more compact tabular solution, seems logical.And thank you again.
Thanks for the comment
can you redo the sound for this video please. I understand it's from 2013 but this is such a great video even today
Ohh thanks.... It was really useful for revising my ISI exam tomorrow.... :)
+Subham Chakravarti good luck !
Wow!! phenomenal explanation making this crystal clear!
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!
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.
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.
@randell heyman
TYSM..
one question.. can we say 206 mod 60 is also an answer?
and also how can 26,86,146 are *multiple* of 60 as you said at 5:35 .. aren't the multiples of 60 are 60,120,180,240,300,360,420,480 and so on?
I've uploadeda video on this question.
Maybe I should have said the difference between any two of ...-34,26,86,... is a multiple of 60.
@@RandellHeyman Thanks for your reply :)
Sir your video was super super easy to understand.its neat and clean.keep up the good work.
shubham singh thanks.
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.
absolutely clear description
thanks a lot
Thank you so much! You're video was very clear and direct.
Can you stop talking from behind me?
i know this is an older video, but it was super helpful. thanks for the great explanation!
Loved it, you hacked it completely.
you made it easy indeed, thanks for the explanation.
Question sir. How do you know what number is going to be multiplied for example in 12, how is it to be multiplied by 3? And also for 15, and how is it multiplied by both 2 and 3?
I used trial and error to find the 3. I just tried various numbers until I got what I wanted. This works well for small numbers like in this problem. When the numbers are bigger we need to use another method. See my video Modular Inverse Made Easy which explains this other method.
@@RandellHeyman thank you sir. I got it now. Thanks for your vids about number theory. These help me alot.
Great !!! The best explanation I found !!! Thanks a lot !!!
the idea is to get the lowest possible number that solves it right? because larger numbers can sometimes solve the problem
This video might be 6 years old, but it is amazing! Thank you so much!
Thanks. More of my videos at ua-cam.com/users/randellheyman
Thanks a lot for this video. You're a saviour
At the end, didnt you mean to say that 26 is 146 (mod 60) ?
I think he accidentally said 142...
@@edwardparish6621 yh
That is very intuitive! thanks a lot !
I'm glad it helped you.
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.
Nice explanation. Much less headache-inducing than Wikipedia!
Nice explanation. I finally understood the logic. Thanks :)
Thank's a lot ! I have a math contest tomorrow and this will help me a lot !
I'm glad it helped.
where did you get 29 and 48 at the end? the 3 numbers were 20, 36 and 90?
At around 5 minutes I have 20 36 and 90 being added.
This gives 146 and then I go on to show that anything which has the same remainder when divided by 60 is also an answer.
Very helpful and easy to understand. Thanks!
Thank you for making the video! saves me lots of time
I'm glad it helped.
Clear and succinct. Thank you very much.
OMG THIS WAS AMAZING, it was easy to follow and understand, and i like that
This video is so helpful!! thank you!!
could you do a video on using back substitution to solve system of linear congruences?
Yanru Chen do you mean using matrices? Or without matrices.
I think without matrices? I think there are 2 ways of using chinese reminder theorem to solve system linear congruences, one way is using the method used in this video, another way is using back substitution. It is introduced in Discrete Mathmatics and its application(i think), but my professor asks me to use back substitution method to solve system linear congruences.
sorry, I googled it and its official name is called successive substitution, back substitution is an unofficial name
I'm just finishing one now on inclusion-exclusion principle. Then I could maybe do it. It's hard to think of a good title that will allow people to find it easily.
Best explanation so far.
Thanks. I'm glad it helped you.
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.
is there a minimum number of given equations that would give us a unique solution ?
The Chinese Remainder Theorem says that if the gcd of the modulii equals 1 then there will always be one answer modulo the product of the modulii. In the video the gcd of 3,4 and 5 equals 1 so there will be one answer modulo 60. By one answer I mean all numbers that are equivalent to 26 mod 60.
at 5:51, shouldn't that be x is congruent to 26mod60? with the 3 lines instead of 2?
Yes. It should have 3 lines instead of 2. I wasn't that good using the animation software when I made this video. Equivalence signs have to be imported.
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.
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?
So clear! THANK YOU SO MUCH
Glad it helped. Lots of videos on other subjects in the made easy playlist at ua-cam.com/users/randellheyman
Thank you! Very clear and simple :)
best explanation of this i've seen.
Thanks, appreciate you taking the time to let me know. Great that it's still helping people.
Why not just multiply by 2 in the last step to go from 15=3 (mod 4) to 30=6=2 (mod 4)? I don't see the need to do this in 2 steps. The difference between 6x15 (your step) and 2x15 (my step) is, off course, zero (mod 60).
Great question John, for problems with small numbers that is fine. But for large numbers you will not have the time and/or inclination to use trial and error. To get an equivalence to 1 is simply working out the modular inverse. This can be done for large, even very large numbers quickly. See my video modular inverse made easy.
this video a blessing
Truly amazing! Thank you.
At 4:17, what's the point of doing it in two stages? You can go straight from 3 mod 4 to 2 mod 4 by multiplying by two to get 6 = 2 mod 4. Multiplying by three first is unnecessary and doesn't do anything to make it easier.
I explain this towards the end of the video. For problems with small numbers like in the video you can go straight to 2. But if the numbers are large you need to go via 1. This involves calculating an inverse for which we can use the extended euclidean algorithm. Watch to the end and if you still have problems ask me again.
Randell Heyman okay, that makes more sense now
Many thanks. This was very clear.
What I dont understand is you multiply the x congruence 1 mod(4) by 2 where gcd (2 , 4) isnt 1. I thought it isnt allowed. But it still works though when I check it.
In general it is ok to add, subtract and multiply both sides of a congruence equation by a number n. But you need to be careful dividing. It is better to think of division by m as being multiplication by the inverse, if it exists, of m.
Very nice explanation, thank you for sharing this !