HomeОбразованиеRelated VideosMore From: Randell Heyman

The Chinese Remainder Theorem made easy

1970 ratings | 270782 views
A solution to a typical exam question. See my other videos https://www.youtube.com/channel/UCmtelDcX6c-xSTyX6btx0Cw/.
Html code for embedding videos on your blog
Text Comments (269)
kshitij mishra (18 hours ago)
i didnt get it
Nasser_Omar (4 hours ago)
Please give me a simple answer because I get confused please 😣
Nasser_Omar (4 hours ago)
+Randell Heyman dear Dr. I understood that we must do the reduction in two stages if we deal with large numbers but why we did this two stages only when we on mod 4 part ???????? This thing that I did not understand from the video please help me ,please .
Randell Heyman (14 hours ago)
Let me know where you first got stuck and I'll try to help you understand better.
Bianca M (3 days ago)
Randell Heyman (3 days ago)
shawn koo (3 days ago)
I got 86 and this works as well. Is there other steps that I need to take?
shawn koo (2 days ago)
+Randell Heyman I watched the last part! I understand why you did that now! Thank you!
Randell Heyman (3 days ago)
Depends on the exact question you are asked. For this question I would accept x=86 mod 60. Sometimes you might be asked for an x between 0 and 60 that solves the question. Then you woukd need to answer 26.
joshua van antwerp (7 days ago)
why are we zapping all the numbers?
Randell Heyman (7 days ago)
You need to watch my video Modular arithmetic made easy.
chris lopan (9 days ago)
Wow this is a great exam question to test a student on Chinese remainder theorem, finding gcd, finding the inverse of a number AND extended euclidean algorithm
Randell Heyman (9 days ago)
I can't take credit. It's a fairly common type of problem. But you are right; it tests a lot of things.
Katie O Neill (17 days ago)
Hey what do you do if the gcd is not 1????
Randell Heyman (17 days ago)
Good question. You generally won't be given that sort of question. But if you are....Suppose you have x=1 mod 6 and x= 5 mod 8. Since gcd (6,8)=2 you can't apply the theorem. So break the 6 and 8 down. x=1 mod 6 means x=1 mod 2 and x=1 mod 3. Next, x=5 mod 8 implies x=1 mod 2 so there is no need to use x=1 mod 2 anymore. So now use the theorem for x=1 mod 3 and x=5 mod 8.
Nitesh Meena (26 days ago)
Simply Great !!!
Randell Heyman (26 days ago)
Thanks Nitesh.
Aditya Rastogi (26 days ago)
amazing explanation!
Randell Heyman (26 days ago)
Thanks for the feedback.
Dhruv Aggarwal (29 days ago)
Thank you for the amazing video
John Chang (2 months ago)
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.
Randell Heyman (2 months ago)
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.
TeamStrongSquad (4 months ago)
How can I solve this with 2 equations?
TeamStrongSquad (4 months ago)
I exactly tried that but didn't work out. What are the chances of you quickly making one as the current ones out there have a lot of dislikes due to how fast they teach it. For example: https://www.youtube.com/watch?v=kXnxYHh1XNw&t=39s
Randell Heyman (4 months ago)
The Chinese remainder theorem can be used for 2 equations. Just follow what I did in the video.
Ionut.E (5 months ago)
What is x = 0 for one of the pair's ?
Randell Heyman (5 months ago)
Sorry I can't quite understand what you are trying to do. But I gather you have made some progress. Comment again if you are still stuck.
Ionut.E (5 months ago)
Actually I've noticed I had made one mistake in my exercise .-. Still thank you! ( So I had a number 140 as the x for 4 mod 7 and and 140 = 0 mod 7 and we have to get it to 1 mod 7 so then we can multiply it with 7 .. It is even possible to get to something like that ? i got 140 because i multiplied the wrong numbers .-. )
Randell Heyman (5 months ago)
Ionut.E Do you mean you are given only 2 equations to solve. E.g. x=0 mod 3 and x=0 mod 4. Then the answer is divisible by 3 and 4. So divisible by 12. So x=0 mod 12.
Md kaif Khan (6 months ago)
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.
Randell Heyman (5 months ago)
Md kaif Khan Thanks for the comment. There is a video of mine on modular inverse if you ever need it.
Primaski (7 months ago)
Thank you so much ♥
Andrew Mcfarland (7 months ago)
Can someone please help me out? At time 3:44, 2*3 = 6, which he says is equal to 1(mod5) However, 1(mod5) is equivalent to 1. 6=1? I'm thoroughly confused.
Larry Ruane (4 months ago)
With mod 5, any number that is greater than or equal to 5, such as 6 in this case, you just subtract 5 (and repeat if still not less than 5). In this case, 6 - 5 is 1, and since that's less than 5, we can stop. In other words, N mod 5 is the remainder after dividing N by 5.
水球潘 (8 months ago)
oh my goddess , you save my time as fuck..
pcakes (8 months ago)
out of every video I've had to watch to understand my math classes so far, this was one of the most helpful
pcakes (8 months ago)
Randell Heyman next time I'm trying to find help I'll look through your channel first :)
Randell Heyman (8 months ago)
Thanks. I appreciate you letting me know. Lots of other math videos at www.youtube.com/randellheyman
Giulio Jiang (8 months ago)
I finally understand it. Thanks!
Randell Heyman (8 months ago)
As I show towards the end of the video there are an infinite number of solutions. The question will generally ask for any solution or sometimes the lowest positive solution or sometimes all solutions.
BreakfastGun (3 months ago)
How would you solve this if the numbers don't have a GCD of 1
PinHead Larry (8 months ago)
the idea is to get the lowest possible number that solves it right? because larger numbers can sometimes solve the problem
范修銘 (8 months ago)
very clear explanation, thank you
Shrimat Kapoor (9 months ago)
Very poorly explained ngl
Randell Heyman (9 months ago)
Shrimat Kapoor Thanks for the feedback. You could have a look at my video 'modular arithmetic made easy' if you are weak on modular arithmetic but probably bettet to look at other people's videos on CRT. Don't give up; you'll get it eventually.
Jackson Blankenship (9 months ago)
You’re a good person, you
i love you
Joseph Noonan (9 months ago)
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.
Joseph Noonan (9 months ago)
Randell Heyman okay, that makes more sense now
Randell Heyman (9 months ago)
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.
Yannick Molinghen (10 months ago)
Very well explained, thank you !
TECH MFK (11 months ago)
How to find y1 if 12.y1 congruent to 1 (mod 5)
TECH MFK (11 months ago)
Randell Heyman . Thanks for your reply
Randell Heyman (11 months ago)
12 is the same as 2 in mod 5. So the problem is 2.y1=1 (mod5). You only need to try 1,2,3 and 4. Note that 2.3=6=1 (mod 5). So if y1=3 (mod 5) then 2.y1=1 (mod 5). Hope that helps.
TECH MFK (11 months ago)
Sir, I watched it. When I try to simplify the above one .I get 2.y2 congruent to 2(mod 4). I don't know how to proceed to find y2
Randell Heyman (11 months ago)
TECH MFK have a look at my video modular inverse made easy.
Marah Faron (11 months ago)
purely amazing!!!!!
shubham singh (11 months ago)
Sir your video was super super easy to understand.its neat and clean.keep up the good work.
Randell Heyman (11 months ago)
shubham singh thanks.
Leala Othman (1 year ago)
@ 3:07 why is 20(mod3) the same as 2(mod3)
Randell Heyman (1 year ago)
Leala Othman 20 mod 3 is the remainder when 20 is divided by 3. Since 20=(6x3)+2 it follows that 20 mod 3 = 2 mod 3. See my video modular arithmetic made easy for more.
Jordan Shepardson (1 year ago)
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
Randell Heyman (1 year ago)
Jordan Shepardson I'm glad it helped so much.
Adarsh Trivedi (1 year ago)
Didn't understand 😮
Randell Heyman (1 year ago)
Hi Adarsh, If you are a little unsure about modular arithmetic then have a look at my video modular arithmetic made easy https://www.youtube.com/watch?v=2zEXtoQDpXY&t=2s . Otherwise try solving just two equations instead of three. I would suggest the first and third equation (i.e. x=2(mod 3) and x=1 (mod 5)). The answer is x=11 (mod 15). Hope that helps.
Gregory C (1 year ago)
Randell Heyman (1 year ago)
Glad it helped. Lots of videos on other subjects in the made easy playlist at www.youtube.com/randellheyman
mathIsART (1 year ago)
I followed the video, but i still feel like I don't understand the Chinese remainder theorem =(
Randell Heyman (1 year ago)
mathIsART Don't be too hard on yourself. I didn't understand it the first time I saw it.
Rhez Visionz (1 year ago)
Got confused after the first step😂
Randell Heyman (1 year ago)
If you tell me exactly where you got confused I am happy to try to help.
Yanru Chen (1 year ago)
This video is so helpful!! thank you!! could you do a video on using back substitution to solve system of linear congruences?
Randell Heyman (1 year ago)
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.
Yanru Chen (1 year ago)
sorry, I googled it and its official name is called successive substitution, back substitution is an unofficial name
Yanru Chen (1 year ago)
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.
Randell Heyman (1 year ago)
Yanru Chen do you mean using matrices? Or without matrices.
Ruben (1 year ago)
Great video, but the audio is horrendous
Sami Siddiqi (4 months ago)
The audio terrifies me.
Ruben (1 year ago)
awesome content, keep it up! lots of students really appreciate you
Randell Heyman (1 year ago)
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.
王Ced (1 year ago)
Payas Parab (1 year ago)
Amazing explanation
Randell Heyman (1 year ago)
Payas Parab I'm glad it helped.
ryancmf1 (1 year ago)
Chris Swan (1 year ago)
love your work mate: bloody brilliant
Randell Heyman (1 year ago)
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.
Chris Swan (1 year ago)
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.
Randell Heyman (1 year ago)
Chris Swan Thanks for the feedback. Australian?
gr4w (1 year ago)
You are a life saver ! Thank you so much! :)
Randell Heyman (1 year ago)
Thanks for the very positive feedback.
Infinity (1 year ago)
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 ....
very well
Nikhil R (1 year ago)
Gaurav Chawla (1 year ago)
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.
Randell Heyman (1 year ago)
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
Aniruddh Vasishta (1 year ago)
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.
Randell Heyman (1 year ago)
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.
littlebigphil (1 year ago)
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.
patricio26262626 (1 year ago)
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.
ziiip (1 year ago)
At the end, didnt you mean to say that 26 is 146 (mod 60) ?
hawa saylac (1 year ago)
Thanks sooo much.... good technique easy to remember :)
TheREBBU (1 year ago)
Thank you! Very clear and simple :)
box5evey (1 year ago)
i know this is an older video, but it was super helpful. thanks for the great explanation!
Carolyn Righeimer (1 year ago)
Many thanks. This was very clear.
Dilip Kumar (1 year ago)
The soln could have been easily understandable and in a well organised format!
Dilip Kumar (1 year ago)
Lengthier, but well explained.
RamanConjecture (1 year ago)
Great video! Thank you!
David Fair (1 year ago)
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!
Randell Heyman (1 year ago)
Glad you liked it. I have a few other discrete mathematics videos you might find useful (www.youtube.com/randellheyman). Good luck at Berkeley.
Anu Purohit (1 year ago)
Nice explanation. I finally understood the logic. Thanks :)
Borat Sagdiyev (1 year ago)
Thanks m8! It took my professor around 10 minutes to do a CRT question in class. I can do it in 1 minute now!
Randell Heyman (1 year ago)
+Borat Sagdiyev Glad it helped.
Shawn Pavlik (1 year ago)
What do you do if the numbers do NOT have a GCD of 1? Example: x ≡ 1 (mod 8) and x ≡ 5 (mod 10)
Randell Heyman (17 days ago)
Sorry. Didn't notice this question when it was put up. See my reply to Katie in Nov 2018.
BreakfastGun (3 months ago)
So how would you do it if this was the case
TheChosenOne (1 year ago)
You don't use this theorem because it won't work lol
Ronalds Upenieks (1 year ago)
where did you get 29 and 48 at the end? the 3 numbers were 20, 36 and 90?
Randell Heyman (1 year ago)
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.
ertosns (1 year ago)
nice explanation, happy subscriber!
Randell Heyman (1 year ago)
Thanks and welcome!
Bill Shillito (1 year ago)
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!
andrewxc1335 (1 year ago)
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.
Naixin Zong (1 year ago)
i still dont understand
Randell Heyman (1 year ago)
It's great to hear when one of my videos makes it all ``click''. Thanks for letting me know.
Kian Popat (1 year ago)
What if it was nx is equivalent to 2(mod3) where n>1?
Randell Heyman (1 year ago)
Hi. We can replace n by n mod 3. If n mod 3 = 0 then we have 0x=2 (mod 3) and there is no solution. If n mod 3 =1 then we have x = 2 (mod 3). If n mod 3 =2 then we have 2x=2 (mod 3). The inverse of 2 mod 3 is 2 (since 2x2=4=1 (mod3). So multiplying both sides by 2 we have x=1 (mod 3). Note that this sort of approach won't work if you have, say, 112x=5566779(mod 2244667). Then the only way to proceed is to use the Euclidean algorithm to find, and then multiply both sides by, the inverse of 112 modulo 2244667. Hope that helps.
Hajdú-Moharos Áron (1 year ago)
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
iisgray (7 months ago)
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])
F A R A H . (8 months ago)
what falls into the category of "big" numbers? when do i know that i need to first go to the 1st remainder?
Randell Heyman (1 year ago)
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.
vidhi sharma (2 years ago)
Best explanation!
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 :)
Randell Heyman (2 years ago)
+Mate Profe Luis Felipe Thanks, I am better at mathematics than Spanish!
Sanjay Kumar (2 years ago)
is x=86 correct ?!
Sanjay Kumar (2 years ago)
Randell Heyman thnks :)) had my xam today luckily CRT came .. Answerd it perfectly ! 💪🏻
Randell Heyman (2 years ago)
+Sanjay Kumar The best way to answer is x is equivalent to 26 mod 60. But 86 mod 60 should also get you full marks.
ZongYe Wang (2 years ago)
It is a very good explanation.
Justin Mogannam (2 years ago)
Very helpful and easy to understand. Thanks!
Ronalds Upenieks (2 years ago)
thanks a bunch bro :*
John Nilsson (2 years ago)
This makes perfect sense. Excellent repetition before exam compared to just staring at the formulas.
Randell Heyman (2 years ago)
Thanks for the thoughtful feedback.
shariq ahmed (2 years ago)
thnx a lot sir
The best explanation! I finally get it :)
Hasan Abdalla (2 years ago)
Thank you sir, the explanation made complete sense, kinda surprising how this theorem is found like hundreds of years ago :O
andrewxc1335 (1 year ago)
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.
Randell Heyman (2 years ago)
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.
Benjamin Hanson (2 years ago)
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.
Randell Heyman (2 years ago)
Yes. About 2,000 years old and it's still true!
HARERIMANA Radjab (2 years ago)
Thank you for making the Chinese Remainder Theorem easy. you are awesome!
Kanishq Kancharla (2 years ago)
2:28 are these multiplying signs or decimals?
Kanishq Kancharla (2 years ago)
ok thank you
Randell Heyman (2 years ago)
Joseph Walker (2 years ago)
great video, thankyou
Khajag Petros (2 years ago)
Very good explanation. I never bothered to know the intuition behind crt but this video explains it perfectly.
Harrson James (2 years ago)
So what happens if the GCD of dividers are not 1?
Randell Heyman (2 years ago)
See my reply to Anzal Khan about a month ago below.
Anzal Khan (2 years ago)
Why can't we find X if GCD(x,y) > 1 ?
Harrson James (2 years ago)
+Randell Heyman nice work :)
Anzal Khan (2 years ago)
Got it , Thanks
Randell Heyman (2 years ago)
OK. Here is one way to proceed. If x = 2 mod 6 then x = 0 mod 2 and x = 2 mod 3. Similarly if x = 3 mod 8 then x = 1 mod 2. So we have x = 0 mod 2 and x = 1 mod 2 which is impossible. So there is no possible solution. When I said a `common sense' solution I meant that you also just say that from x=2 mod 6 we have x is even and from x=3 mod 8 we have x is odd. So no solution is possible. If you don't get a contradiction then you have a number of equations that do satisfy the chinese remainder theorem and you can solve it as I do in the video.
Anzal Khan (2 years ago)
let's say that x = 2 (modulo 6) x = 3(modulo 8) x = 1 (modulo 5) What will be the issue here ?
Randell Heyman (2 years ago)
Good question. If the gcd is greater than one then the chinese remainder theorem doesn't apply. You need to use other methods. For small numbers I just use some `common sense'. If you have an example I can show you what I mean.
Saad Taame (2 years ago)
Very nice explanation, thank you for sharing this !
Joshua Tony-Enwin (2 years ago)
why did couldnt you just go from 3mod4 to 2mod4??
Randell Heyman (2 years ago)
+Joshua Tony 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.
Joshua Tony-Enwin (2 years ago)
instead you went from 3mod4 to 1mod4 then to 2mod4. i'm quite confused
ZyloxZukaki (2 years ago)
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?
Randell Heyman (2 years ago)
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.
Just Me (2 years ago)
why did this receive down votes. It's so clear. His example goes through every possible typical scenario.
djd829 (21 days ago)
Probably people who didn't want to learn math from satan
Baobab Koodaa (2 months ago)
Starting from 1:45 this doesn't make sense to me.
N1v3x (2 months ago)
Textbook advocates
Nash Rah (2 years ago)
X= 86 works too
Randell Heyman (2 years ago)
+Nash Rah Agreed. See around 5'38".
Umar Akhtar (2 years ago)
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.
Randell Heyman (2 years ago)
+Umar Akhtar Thanks. It is nice to hear from people I have helped. Good luck with the exam.
GURVIRRR (2 years ago)
My discrete math class makes me want to drop out of college :(
GURVIRRR (2 years ago)
+Randell Heyman Thanks for the tips. And you videos do help out a lot.
Randell Heyman (2 years ago)
+GRiZZLY G Sorry to hear that. My only suggestion would be to focus on what you know rather than getting overwhelmed by what you don't know. Suppose for your course there are 50 typical questions that exams are constructed from. If you can do 15 that is fine. Then just start looking for the easiest questions you can work on and then add to the list of 15 once you understand them. If you can get your list up to around 50% you have a (good) chance of passing.
Subham Chakravarti (2 years ago)
Ohh thanks.... It was really useful for revising my ISI exam tomorrow.... :)
Randell Heyman (2 years ago)
+Subham Chakravarti good luck !
Mystical Miner (2 years ago)
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!
Hanna Torres (1 month ago)
I was getting crazy trying to figure out where did 142 came from.
Randell Heyman (2 years ago)
+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.
Mystical Miner (2 years ago)
The Varzoth (2 years ago)
Very well explained thank you. For the life of me I don't get why textbooks can't put things as simply.
Hong W (2 years ago)
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.
Randell Heyman (2 years ago)
+Hong W Glad it helped!
GeronimoStilton (2 years ago)
In the middle section howcome we have to go from 3 mod 4 to 1 mod 4 to 2 mod 4?
GeronimoStilton (2 years ago)
+Randell Heyman Thank you!
Randell Heyman (2 years ago)
+stelton25 If the numbers are small trial and error, going directly from 3 mod 4 to 2 mod 4 is fine. If the numbers are large you need to use the Extended Euclidean Algorithm to find how to get to 1 in the modulo you are working in. Then you multiply by what you need to get to the right answer. See what I say from 6 minutes on the video. Hope that helps.
Redda (2 years ago)
Truly amazing! Thank you.
Deividas Pekunas (2 years ago)
Oh god it's so simple now, thank you very much !!!
Gyanendro Loitongbam (3 years ago)
Superb Lecture..:) BTW how to find for large no. eg x = 3346 (mod 7919) x = 2096 (mod 12553) x = 730 (mod 17389)
John Chang (2 months ago)
x = 1710316275532 Solve the 3 subproblems from CRT: 1. 12553*17389x ≡ 3346 (mod 7919). Multiplying the 2 5-digit numbers and taking mod 7919, then subtracting 7919, gives -3118x ≡ 3346 (mod 7919). Divide by 2 to get -1559x ≡ 1673 mod 7919. Add on lhs and subtract on rhs 7919 to get 6360x = -6246 mod 7919. Divide by 6: 1060x≡ -1041 ≡ 6878 mod 7919. Divide by 2. 530x ≡ 3439 ≡ -4480 (mod 7919). Divide by 10: 53x ≡ -448 (mod 7919). To solve for x, add some multiple of 7919 to -448 that makes it divisible by 53. -448 ≡ 29 and 7919 ≡ 22 (mod 53), so this is like asking how many 22s need to be added to 29 to be divisible by 53? That is, what is n if 29 + 22n ≡ 0 (mod 53)? So 22n ≡ -29 ≡ 24 (mod 53). Divide by 2: 11n ≡ 12 (mod 53). Multiply by 5: 55n ≡ 2n ≡ 60 (mod 53). Divide by 2: n ≡ 30 (mod 53). Then x ≡ (7919*30 - 448)/53 ≡ 4474 (mod 7919). 2. 7919*17389x ≡ 2096 (mod 12553). -4634 * 4836 ≡ 2096 (mod 12553). Divide by 8: -2317*1209x ≡ 262 (mod 12553). -1934x ≡ 262. Divide by 2: 967x = -131 (mod 12553). 12553 ≡ -18 mod 967. Find n such that -131 - 18n ≡ 0 mod 967. 18n ≡ 836 (mod 967). Divide by 2: 9n ≡ 418 ≡ -549 (mod 967). Divide by 9: n≡ -61 (mod 967). x ≡ (-131-12553*61)/967 ≡ -792. 3. 12553*7919x = 730 (mod 17389). -5706 ≡ 730 Divide by 2: -2853 ≡ 365. Add 17389 to lhs and subtract from rhs: 14356x ≡ -17024. Divide by 8 => 1817x ≡ -2128 (mod 17389). Look for n such that -2128 + 17389n ≡ 0 mod 1817. -2128 ≡ 1506 (mod 1817), and 17389 ≡ 1036 (mod 1817). 1036n ≡ -1506 (mod 1817). Divide by 2: 518n ≡ -753 (mod 1817). Subtract 1817 from rhs: 518n ≡ -2570 (mod 1817). Divide by 2: 259n ≡ -1285 (mod 1817). Subtract 1817 from lhs, and add to rhs: -558n ≡ 532 (mod 1817). Divide by -38: 41n ≡ -14 (mod 1817). 1817 ≡ 13 (mod 41). Choose m such that -14 + 1817m ≡ 0 (mod 41) . 13m ≡ 14 (mod 41). Multiply by 3: 39m ≡ -2m ≡ 42 (mod 41). Divide by -2: m ≡ -21 ≡ 20 (mod 41). Back substitute to get n ≡ (-14+1817*20)/41 ≡ 886 (mod 1817). Then x ≡ (-2128 + 17389*886)/1817 ≡ 8478 (mod 17389). Putting it all together, a particular solution is 12553*17389*4474 + 7919*17389*(-792) + 12553*7919*8478 = 1710316275532.
Randell Heyman (2 years ago)
+cirethesquire If you multiply 17389 by 12553 and work out the reminder when you divide by 7919 you will get 4801. Then I multiply by the inverse of 4801. This will give me 1 when I apply modulo 7919. Then I multiply by what I am given in the question for x modulo 7919.
cirethesquire (2 years ago)
+Randell Heyman how did you get x= 4801 mod 7919? and why multiply by the inverse of 4801?
Gyanendro Loitongbam (3 years ago)
thank you so much I got it... Thumbs up!!!
Randell Heyman (3 years ago)
+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).
Ramtin Javanmardi (3 years ago)
This is great and all but my problem is how to efficiently show on an exam how I have solved the problem without writing a lot of text and wasting everyone's time :/
Ramtin Javanmardi (3 years ago)
+Randell Heyman Will do, thank you very much! :)
Randell Heyman (3 years ago)
Good question. Try having a look at the first formula under general case on the chinese remainder theorem page of wikipedia. If you understand my video you should be able to use that.
Mr. JC (3 years ago)
Very nice... Thank you very much.
CarpeDiem3525 (3 years ago)
What if the GCD doesn't equal 1? I have a question and the GCD = 1,13 and 10: x = 9 mod 13 x = 7 mod 10 find x mod 130. Any help would be appreaciated.,
CarpeDiem3525 (3 years ago)
+Randell Heyman awesome thank you i appreciate your help
Randell Heyman (3 years ago)
+CarpeDiem3525 Yes. Follow the video and it should work out fine. Check you answer when you finish to make sure that x=9 mod 13 and x=7 mod 10.
CarpeDiem3525 (3 years ago)
+Randell Heyman if i follow the method in your video will it apply the same way to the question i posted then? btw thanks for the reply.
Randell Heyman (3 years ago)
+CarpeDiem3525 Sorry, I don't see the problem. The GCD of 13 and 10 is 1. So there should be no problem solving as in the video. You can, of course, get a situation where the GCD is not 1. For example, x = 2 mod 20 and x = 3 mod 35. These can be solved using other methods. Hope that helps.

Would you like to comment?

Join YouTube for a free account, or sign in if you are already a member.