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!

@RandellHeyman

7 жыл бұрын

It's great to hear when one of my videos makes it all ``click''. Thanks for letting me know.

@naixinzong5449

6 жыл бұрын

i still dont understand

@andrewxc1335

6 жыл бұрын

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

@RandellHeyman

6 жыл бұрын

Jordan Shepardson I'm glad it helped so much.

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.

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!

@RandellHeyman

7 жыл бұрын

Glad you liked it. I have a few other discrete mathematics videos you might find useful (kzread.info). Good luck at Berkeley.

@64_bit80

Жыл бұрын

studying for the 70 final right now and im fucking dying lmao 100% agree

@2000Chess

Жыл бұрын

@@64_bit80 studying for the summer 70 quiz rn LOL

@carolynwang8338

6 ай бұрын

taking cs70 now and my brain is exploding LMAOO

Why not directly from 3(mod 4) to 2(mod 4) ? Can't we multiply the former by 2 and make that happen ?

@angelnajera7169

7 жыл бұрын

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.

@patricio26262626

7 жыл бұрын

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.

@selanavot1630

2 жыл бұрын

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

Thank you! Thank you! Thank you! Made learning how to use this theorem for my assignment so much easier! :D

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.

@RandellHeyman

Жыл бұрын

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

The most clear and structural explanation without just using the usual steps without reason like other videos!!! Thank you !😇

@RandellHeyman

9 ай бұрын

Thanks. Appreciate such positive feedback.

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 :)

@RandellHeyman

2 жыл бұрын

Thanks.

Thank you for this video! It helped me get past a block in my thinking.

Very good explanation. I never bothered to know the intuition behind crt but this video explains it perfectly.

Mr. Heyman, you just saved me hours of precious time!

Oh god it's so simple now, thank you very much !!!

Awesome, learnt how to do this now. Pretty cool vid.

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!

@RandellHeyman

6 ай бұрын

Thanks for the positive feedback.

Fantastic, I've seen this method on other videos but no good explanations as clear as this! thanks!

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

@RandellHeyman

7 жыл бұрын

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-vi2cj

6 жыл бұрын

what falls into the category of "big" numbers? when do i know that i need to first go to the 1st remainder?

@iisgray

6 жыл бұрын

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])

@LarryRuane

3 жыл бұрын

@@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.

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.

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?

@RandellHeyman

8 жыл бұрын

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.

Bloody Brilliant!! I'm sure your Math Prof would be extremely proud of you :D!

This makes perfect sense. Excellent repetition before exam compared to just staring at the formulas.

@RandellHeyman

7 жыл бұрын

Thanks for the thoughtful feedback.

Literally a better explanation than my pointlessly expensive university courses. Thank you.

@RandellHeyman

5 жыл бұрын

Thanks for the nice comment

Great !!! The best explanation I found !!! Thanks a lot !!!

Thanks, man! Taking an online class and didn't quite understand what the instructor was saying. This video helped out a ton!

@RandellHeyman

2 жыл бұрын

I'm glad it helped.

Thank you so much! You're video was very clear and direct.

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.

@RandellHeyman

6 жыл бұрын

Md kaif Khan Thanks for the comment. There is a video of mine on modular inverse if you ever need it.

Wow!! phenomenal explanation making this crystal clear!

out of every video I've had to watch to understand my math classes so far, this was one of the most helpful

@RandellHeyman

6 жыл бұрын

Thanks. I appreciate you letting me know. Lots of other math videos at kzread.info

@RacecarsAndRicefish

6 жыл бұрын

Randell Heyman next time I'm trying to find help I'll look through your channel first :)

extremely informative content out here, would've never figured out how it worked if not your help. Thanks you

@RandellHeyman

9 ай бұрын

Thanks for commenting. Great to hear that my 10 year old video is still helping people.

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 !!!

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.

@RandellHeyman

3 жыл бұрын

Thanks for feedback.

Truly amazing! Thank you.

OMG THIS WAS AMAZING, it was easy to follow and understand, and i like that

absolutely clear description thanks a lot

The explanation was very lucid.Thanks a lot!

Thank you! Very clear and simple :)

i know this is an older video, but it was super helpful. thanks for the great explanation!

That was super-easy to follow! Thank you.

@RandellHeyman

Жыл бұрын

Thanks for the positive feedback.

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.

@RandellHeyman

8 жыл бұрын

+Umar Akhtar Thanks. It is nice to hear from people I have helped. Good luck with the exam.

The best explanation! I finally get it :)

When the "made easy" video is too hard to understand too. It's like the draw an owl meme.

Great video which actually explains it better than any professor or textbook would!

@RandellHeyman

2 жыл бұрын

Thanks.

Lovely explanation, the moment you started explaining the first bit ( using product of remaining numbers for each term ), everything became clear.

@RandellHeyman

5 жыл бұрын

Thanks for the positive feedback.

Very helpful and easy to understand. Thanks!

Nice explanation. I finally understood the logic. Thanks :)

Joyful how easy you made this. Thanks!

@RandellHeyman

Жыл бұрын

Glad it was helpful!

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. :)

@RandellHeyman

9 жыл бұрын

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.

@airtonishimori4684

9 жыл бұрын

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 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. :)

Bless this man

Loved it, you hacked it completely.

You are a hero!

Very nice explanation, thank you for sharing this !

you made it easy indeed, thanks for the explanation.

You made it easy. thanks !

thank you so much....you showed the way for finding solution ,simultaneously giving reasons for why we are doing the steps....appreciate your work!!👌👌

@RandellHeyman

4 жыл бұрын

Thanks Aayush.

Amazing video, really well explained 👍🏽

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.

@RandellHeyman

8 жыл бұрын

+Hong W Glad it helped!

Very well explained thank you. For the life of me I don't get why textbooks can't put things as simply.

Very well explained, thank you !

That is very intuitive! thanks a lot !

@RandellHeyman

3 жыл бұрын

I'm glad it helped you.

Thank you sir, the explanation made complete sense, kinda surprising how this theorem is found like hundreds of years ago :O

@RandellHeyman

7 жыл бұрын

Yes. About 2,000 years old and it's still true!

@benjaminhanson6137

7 жыл бұрын

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.

@RandellHeyman

7 жыл бұрын

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.

@andrewxc1335

6 жыл бұрын

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.

I finally understand it. Thanks!

Great video! Thank you!

what to do if you have numbers like 79 mod 68? how to you get it to become mod 1?

@RandellHeyman

Жыл бұрын

79 mod 68 is equal to 11 mod 68. Then proceed as in the video. But note my comments at the end of the video. When the numbers are too big to just guess and check to get 1 you need other techniques. These are covered in my video Modular inverse made easy and RSA code made easy.

Thanks a lot for this video. You're a saviour

THANK YOU SO MUCH

What happens if we apply this Remainder Theorem to equations that don’t have a gcf of 1?

@RandellHeyman

5 жыл бұрын

If the gcd of any two modulii is not equal to 1 you can't apply the Theorem directly. But you can solve it with a few extra steps. See my reply to Katie 8 months ago.

Very nice... Thank you very much.

at 5:51, shouldn't that be x is congruent to 26mod60? with the 3 lines instead of 2?

@RandellHeyman

9 жыл бұрын

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.

Thank you for making the video! saves me lots of time

@RandellHeyman

4 жыл бұрын

I'm glad it helped.

Nice job good to understand!

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 :)

@RandellHeyman

7 жыл бұрын

+Mate Profe Luis Felipe Thanks, I am better at mathematics than Spanish!

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)?

@RandellHeyman

Жыл бұрын

Yes. That's right. I think I edited in a comment on the video saying that.

So clear! THANK YOU SO MUCH

@RandellHeyman

6 жыл бұрын

Glad it helped. Lots of videos on other subjects in the made easy playlist at kzread.info

Many thanks. This was very clear.

Nice explanation. Much less headache-inducing than Wikipedia!

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

@RandellHeyman

9 жыл бұрын

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.

@RandellHeyman

3 жыл бұрын

Thanks. I have lots of other videos on Modular inverse, Euler's theorem, Finite fields, Modular exponentiation etc.

Thanks sooo much.... good technique easy to remember :)

That was great.

where did you get 29 and 48 at the end? the 3 numbers were 20, 36 and 90?

@RandellHeyman

7 жыл бұрын

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.

purely amazing!!!!!

this video a blessing

Thank you for the amazing video

Thank you. You just saved my Discrete Mathematics grade.

@RandellHeyman

3 жыл бұрын

Thanks. I'm glad you will get through Discrete Mathematics.

You are a life saver ! Thank you so much! :)

@RandellHeyman

7 жыл бұрын

Thanks for the very positive feedback.

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.

@RandellHeyman

2 жыл бұрын

Thanks.

A nice way to explain. You may give a more compact tabular solution, seems logical.And thank you again.

@RandellHeyman

4 жыл бұрын

Thanks for the comment

Thank you!

Sir your video was super super easy to understand.its neat and clean.keep up the good work.

@RandellHeyman

6 жыл бұрын

shubham singh thanks.

nice explanation, happy subscriber!

@RandellHeyman

7 жыл бұрын

Thanks and welcome!

Expert and clear explanation- thank you.

@RandellHeyman

4 жыл бұрын

Glad it helped. I wish there had been a video like mine when I was studying the Chinese Remainder Theorem!

super helpful, thanks!

at 04:22 why do we go from 3 mod 4 to 1 mod 4 to 2 mod 4 ?? i just couldnt keep up with the flow, why dont we multiply by 2 and just stop.

@RandellHeyman

7 жыл бұрын

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

the idea is to get the lowest possible number that solves it right? because larger numbers can sometimes solve the problem

great job!!

thank you!

very clear explanation, thank you

This video might be 6 years old, but it is amazing! Thank you so much!

@RandellHeyman

4 жыл бұрын

Thanks. More of my videos at kzread.info