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!
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.
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.
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.
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.
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 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 :)
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.
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.
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 !!!
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.
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 :)
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.
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).
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.
+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'm still new to this concept and at this point...I don't understand anything, so I plead with you to vividly explain everything 🥺 maybe in another video
@@jeremyfang1624 Hope you find some useful videos on my channel. For the last year of so I have been making videos to specifically help people during the corona virus. So there's about 60 videos made with animation software and about 170 made with a graphics tablet.
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!
11x ≡ 1 (mod 7171). Since 7171 ≡ -1 (mod 11), 11x ≡ 7172 (mod 7171) is divisible by 11, so x ≡ 652 (mod 7171). No need for the extended Euclidean algorithm here.
Yes. That works. Well done. But are you claiming you never need the euclidean algorithm? If so try to solve 123456789x=1 (mod123456779101112131415) without Euclid's algorithm in under ten minutes.
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.
multiplying 15 by 3 is unnecessary... it is enough to multiply 15 by 2 and get 30 (30=2 mod4) so you will have 20 + 30 + 36 = 86 if multiplying 15 by 3 is necessary can somebody explain me why?
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 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.
thank you, I am studying Cybersecurity right now and cryptology is giving me lot of pain since its pure math. Its a very interesting subject, but learning the theorems is bleh. Thank you for helping me understand the concept!
Thanks for the feedback. I have another video RSA code made easy when you get to that crypto method. Also How encryption works which is an easier video that doesn't cover as much as RSA code made easy. You might also study error correction. I have a video Hamming code made easy for 1 of these correction techniques.
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 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.
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 (ruclips.net/user/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
The most clear and structural explanation without just using the usual steps without reason like other videos!!! Thank you !😇
Thanks. Appreciate such positive feedback.
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.
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.
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.
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.
Literally a better explanation than my pointlessly expensive university courses. Thank you.
Thanks for the nice comment
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 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.
When the "made easy" video is too hard to understand too. It's like the draw an owl meme.
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 ruclips.net/user/randellheyman
Randell Heyman next time I'm trying to find help I'll look through your channel first :)
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.
Can you stop talking from behind me?
This was awesome, there needs to be more math videos like this
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.
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.
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.
The explanation was very lucid.Thanks a lot!
Bloody Brilliant!! I'm sure your Math Prof would be extremely proud of you :D!
Great video which actually explains it better than any professor or textbook would!
Thanks.
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!
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.
Very well explained thank you. For the life of me I don't get why textbooks can't put things as simply.
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!
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 !!!
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.
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.
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! Thank you! Thank you! Made learning how to use this theorem for my assignment so much easier! :D
That was super-easy to follow! Thank you.
Thanks for the positive feedback.
Ohh thanks.... It was really useful for revising my ISI exam tomorrow.... :)
+Subham Chakravarti good luck !
Very good explanation. I never bothered to know the intuition behind crt but this video explains it perfectly.
Bless this man
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. You just saved my Discrete Mathematics grade.
Thanks. I'm glad you will get through Discrete Mathematics.
Fantastic, I've seen this method on other videos but no good explanations as clear as this! thanks!
Sir your video was super super easy to understand.its neat and clean.keep up the good work.
shubham singh thanks.
Joyful how easy you made this. Thanks!
Glad it was helpful!
This video might be 6 years old, but it is amazing! Thank you so much!
Thanks. More of my videos at ruclips.net/user/randellheyman
A nice way to explain.
You may give a more compact tabular solution, seems logical.And thank you again.
Thanks for the comment
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.
Nice explanation. Much less headache-inducing than Wikipedia!
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!
Thank you for this video! It helped me get past a block in my thinking.
Thanks a lot! I never did got it until now
It's very pleasing when someone finally gets one of these great mathematical theorems.
Oh god it's so simple now, thank you very much !!!
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.
Wow!! phenomenal explanation making this crystal clear!
Mr. Heyman, you just saved me hours of precious time!
Loved it, you hacked it completely.
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?
Awesome, learnt how to do this now. Pretty cool vid.
Thank's a lot ! I have a math contest tomorrow and this will help me a lot !
I'm glad it helped.
Nice explanation. I finally understood the logic. Thanks :)
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.
i know this is an older video, but it was super helpful. thanks for the great explanation!
Thank you so much! You're video was very clear and direct.
you made it easy indeed, thanks for the explanation.
best explanation of this i've seen.
Thanks, appreciate you taking the time to let me know. Great that it's still helping people.
Great !!! The best explanation I found !!! Thanks a lot !!!
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.
Thanks a lot for this video. You're a saviour
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 ....
Best explanation so far.
Thanks. I'm glad it helped you.
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.
Thank you for making the video! saves me lots of time
I'm glad it helped.
OMG THIS WAS AMAZING, it was easy to follow and understand, and i like that
I'm still new to this concept and at this point...I don't understand anything, so I plead with you to vividly explain everything 🥺 maybe in another video
Tell me when on the video you first don't understand something and I'll try to help.
@@RandellHeyman Wow, you still reply to comments on a video that's 8 years old? Imma sub cause of that
@@jeremyfang1624 Hope you find some useful videos on my channel. For the last year of so I have been making videos to specifically help people during the corona virus. So there's about 60 videos made with animation software and about 170 made with a graphics tablet.
@@RandellHeyman bro...your the best
@@RandellHeymanI'll just watch it again
Very helpful and easy to understand. Thanks!
Very nice explanation, thank you for sharing this !
can you redo the sound for this video please. I understand it's from 2013 but this is such a great video even today
Amazing video, really well explained 👍🏽
It is a very good explanation.
Thank you so much, I’m here before my Midterm❤
Good luck with it.
That is very intuitive! thanks a lot !
I'm glad it helped you.
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!
absolutely clear description
thanks a lot
11x ≡ 1 (mod 7171). Since 7171 ≡ -1 (mod 11), 11x ≡ 7172 (mod 7171) is divisible by 11, so x ≡ 652 (mod 7171). No need for the extended Euclidean algorithm here.
Yes. That works. Well done. But are you claiming you never need the euclidean algorithm? If so try to solve 123456789x=1 (mod123456779101112131415) without Euclid's algorithm in under ten minutes.
the idea is to get the lowest possible number that solves it right? because larger numbers can sometimes solve the problem
The best explanation! I finally get it :)
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.
Many thanks. This was very clear.
multiplying 15 by 3 is unnecessary... it is enough to multiply 15 by 2 and get 30
(30=2 mod4) so you will have 20 + 30 + 36 = 86
if multiplying 15 by 3 is necessary can somebody explain me why?
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.
Randell Heyman Berat Anıl Berber I was wondering about exactly this. Thanks for clearing it up, fellas.
Randell Heyman but surely the answer would be different to 146?
Randell Heyman nevermind, i realised that this adds to 86, which is still 146 - 60 :)
You are a life saver ! Thank you so much! :)
Thanks for the very positive feedback.
Nice job good to understand!
nice explanation, happy subscriber!
Thanks and welcome!
this video a blessing
Clear and succinct. Thank you very much.
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.
thank you, I am studying Cybersecurity right now and cryptology is giving me lot of pain since its pure math. Its a very interesting subject, but learning the theorems is bleh. Thank you for helping me understand the concept!
Thanks for the feedback. I have another video RSA code made easy when you get to that crypto method. Also How encryption works which is an easier video that doesn't cover as much as RSA code made easy. You might also study error correction. I have a video Hamming code made easy for 1 of these correction techniques.
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.
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.
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.
Thank you! Very clear and simple :)