I have "learned" this in 3 different classes, and this is by far and a way the most intuitive and well reasoned explanation I have come across for doing the calculation. I come from a pure math background so the professors have all tried to give a quotient group or ring argument then hand wave away the calculation.
Number theory is my favorite discrete math branch. Although, when I assume that I have mastered a technique, something worse is waiting for me in the corner. Thank you from the deepest of my heart. You have made this complex theorem ridiculously easy. "There are three components to success: simplify, simplify simplify."
I needed to review the CRT when one of my students presented me with this problem: "Find digits X,Y,and Z so that the number 789,XYZ is divisible by 7, 8, and 9, where X, Y, and Z are in {0,1,2,3,4,5,6}." This example has the *perfect* blend of a concrete example with just the right amount of theory/algorithm (x,b,i,N,etc), along with narration that is not unpleasant to listen to. Thank you so much!
@@MathsWithJay Thank you, for being the best explanation of CRT I could find. Everything else is written/taught in such high mathematical language it was impenetrable.
I want to cry at how much you saved me. I've been trying to understand this unit for the past 2 days. This 13 min video helped me more than everything I have trie so far. I am literally in tears while I am writing this comment. THANK YOU SO MUCH!!!!!!
The numbers are so small that I solved this problem in my head after a few minutes whilst watching the video. I just tried to find a values of x such that x = 6 + 8y, where y = 1,2,3, ... 9 (I stopped here) as 6 + 8x9 = 78, and x = 78 satisfied all three congruences.
The extended euclidean algorithm really helps instead of trial or error for finding inverse.I have had some luck writing a computer program for it and now I wanted to understand the chinese remainder theorem and incorporate the the algorithm into it,but I was having a hard time until i came upon this video which blew my mind.Thank you so much,I have been stuck for days struggling with number theory and this helps so much.Please make more videos.
That is THE best explanation I've seen for this. Thank you, this has helped me a lot and I don't think I'll ever forget this easy way of solving it. Thanks!
Thank you so much, this was really helpful! I'm a third year maths undergraduate and have always struggled with the Chinese Remainder Theorem from the moment we learned it in Abstract Algebra in first year, but will definitely be using this method from now on. I have a number theory exam in two days so fingers crossed this helps! ^.^
The math books I have are horrible at explaining it. They are all written by people who forget how hard this is to an outsider. This video was the best so far.
Even though I do have some tutorials in my native language which is Polish, this video was more helpful. Now I understand this and I'm ready for my exam
In India Artabhatta 1 invented in kuttaka ,ie pulverised system. He was born in 476 AD in India and possibly headed Belanda University.. See reminder theorem linear and Pell equation invented by brahma gupta in 628 AD. For all info see bbdatta ana ansingh book hindu mathematics. May be available in internet archive.
For finding the inverse, I personally find it easier to add ni to the right term until I get a multiple of the left term parameter. At least when the left term parameter is such that it is easy to check if a number divides it.
wonderful video, crystal clear. i was able to implement Python code for this trivially, especially since Python 3.8 provides the function for the modular inverse with a simple call to `x = pow(Ni,-1,m)`, no libraries needed
Brahma gupta formula 5x + 3 -1 is divisible by 7, 5x+2 is divisible by 7 when x =1, then number is 7 satisfying two conditions, third is now 5x7 k + 8 - 6 is divisie by 8 or 3k + 2 s divisible by 8, then k =2, , then number is 35x2+ 8 =78. It is done in 650 AD, much before Chin Sao in 1247 AD. Gauss popularised Chinese theorem.
You may read Chinese Mathematics by Ulrich liberchit and history of Hindu mathematics, BB Datta and Avadesh Narayan Singh. Issue of remainder theorem is part of Linear Indeterminate Analysis initiated by Aryabhatta 1, 476 - 550 ad. solution of equation ax - by = +- c, Uniqueness is positive integer solutions. But , Brahmagupta added algebra , add negative integer solutions also. Western people highlighted Diophantus who solved rational solution Bhaskara 1 solved ax -by =1, this could be used as modulo purpose. This crypitc two verses were elaborated by Bhaskara 1 600 ad 680 ad. Interesting feature is bhaskara 1, Brahmagupta 598 -665ad, Mahavira 850 ad , Aryabhatta ii, and Bhaskara ii, between them , many commentators there, each one modified the generic form. Besides, all of them added many inputs. Brahmagputra with 1000 verses, out of two chapters Ganitadhya (arthmatic) and Kuuttakadhya (Algebra)by T H Colebrook . U could get some of them from internet archive. Brahmaputra NX^2+c = y^2. , 67x^+1= y^2 , N is a non squared prime number , you have to solve 101x^+1 = y ^2. Procedure was improved by jaydeva of 9th century and finally 11th century by Chakravala method.. Cyclic method.but western people named Pell equation . My email kantoprasad@gmail.com, KPSinha , Delhi India.
The method is offical but seems to be a bit complicate. Just take the two largest multiple 7 and 8 we can immediate see 77 and 72 respectively. Then 77+1 and 72+6 That 78 fulfil 7 and 8. We then verify 5 remain 3. Simple
@@MathsWithJay We are starting to come out of lockdown as well starting next week, but a full lockdown was never implemented anyway just a partial curfew with schools and closure of cafes/restaurants. The weather here is starting to be very nice but unfortunately beaches remain closed :( I was moving to London by the end of July but everything is put on hold because of what's going on 🤦
Yesterday some of England's beaches were overwhelmed by visitors...we now have unusually hot weather for a few days. Restaurants and museums hope to open on 4th July, but schools are not planning for pupils to be back until September
Hello! You're one dedicated teacher, Jay.. this is one concept that looked unsurmountable, and you've helped me become competent in a matter of 13 minutes.. thank you so much.
If u want to work out the sum, whose principle was invented by ArgBhatt 1 and fine-tune by Brahmsvupts., 5x +3-1=5x+2 is divine by 7 , then x =1,,Number satisfying both is 8, Next number is 5x7k+ 8, 35k +8 -6=35k+2 is divisible by 8,is, 3k+2 =6,, minimum value of k is 2, then ,number is 35x2+8=78. Chinese Remain set theorem was invented by Chin Chia Shao in 1247 ad, Brahmaputra gave this easy or OK cess in 625 AD, Aryabhatta 1 theeorised it in cryptic Sanskrit in 499 ad. Chinese Remainder theorem was popularised. By Gauss.
Nice video @maths with Jay , could you please help me with this: By raising 7 ≡ 5^x(mod 18) to the powers 2 and 3, we get: 13 ≡ 7^x(mod 18) and 1 ≡ 17^x(mod 18), respectively. Solving DLP in the first subgroup gives us x ≡ 2 (mod 3). What is x in the second subgroup? How to use the Chinese Remainder Theorem (using PARI) to find x in the original DLP instance.
@@MathsWithJay x=2 mod 5 2x= 1 mod 7 => 2x=1+7 mod 7 => 2x=8 mod 7 => 2x/2=8/2 mod 7 => x=4 mod 7 3x=4 mod 11=> 3x=4+11 mod 11 => 3x=15 mod 11 => 3x/3=15/3 mod 7 => x=5 mod 11 ======== x=2 mod 5 x=4 mod 7 x=5 mod 11
I have "learned" this in 3 different classes, and this is by far and a way the most intuitive and well reasoned explanation I have come across for doing the calculation. I come from a pure math background so the professors have all tried to give a quotient group or ring argument then hand wave away the calculation.
You're very welcome! Thank you so much for this superb feedback.
Lol yes those quotient groups are irritating 😂
I couldn’t agree more. I’m actually upset that it wasn’t taught this way
How 78 came?
@@shreeshsingh1121 918 divided by 280, and you get the remainder of 78
These comments thanking you are NOT overstatements. This was a wonderful explanation, sending my thanks from college
@Marlon: Thank you so much! Where is your college?
Queens college
Number theory is my favorite discrete math branch.
Although, when I assume that I have mastered a technique, something worse is waiting for me in the corner.
Thank you from the deepest of my heart.
You have made this complex theorem ridiculously easy.
"There are three components to success: simplify, simplify simplify."
I am so glad that you found this helpful. All the best!
I can't help but cry after understanding this. You are a life saver and relieves me from false assumptions that my brain ain't working anymore.
That's great!
@@MathsWithJay OMG This video was uploaded over a year ago and you are still replying to the comments That's Really Great !!!
Good
This is so simple, and every resource I've come across makes it look so difficult.... "Simplicity is the Ultimate Sophistication" many thanks!
@Quentin Gigon: Thank you so much!
See Brahma gupta rule , it takes one minute, I have written in comment section today on 24.1.2021
Mrs Jay I cannot express how much you have saved my life. I am now an absolute tank at these, I am moving to Beijing as we speak.
Good to know it helped!
I needed to review the CRT when one of my students presented me with this problem:
"Find digits X,Y,and Z so that the number 789,XYZ is divisible by 7, 8, and 9, where X, Y, and Z are in {0,1,2,3,4,5,6}."
This example has the *perfect* blend of a concrete example with just the right amount of theory/algorithm (x,b,i,N,etc), along with narration that is not unpleasant to listen to. Thank you so much!
It's good to know that you found this useful
RSA is the Most beautiful application of Mathematics ever devised. It is simple yet so powerful that it gives people sleepless nights.
Nah, it's rather ugly imo. We don't even know that there is no efficient factorisation algorithm.
Finally explanation that makes the concept easy rather than making it more complicated ,I seriously can't thank you enough 💜💜
You're very welcome!
Came here from Advent of Code 2020 - Day 13
That's interesting - it explains the sudden increase in views! Thank you for letting me know.
Part 2 yeah :)
@@MathsWithJay Thank you, for being the best explanation of CRT I could find. Everything else is written/taught in such high mathematical language it was impenetrable.
yup but failed to find a way to get the inverse reee
Thank you so much Anthony
Thx a lot!!!! This is the simplest way to think of CRT I have learnt so far. Really helpful for my final
@Linfei ZHANG: Glad it helped! Good luck with your final.
Never seen better presentation skills and organization. People, of course, can take a few shortcuts on an exam with time constraints. Thank you!
Wow, thank you!
This is THE best example I've seen on TH-cam. Thanks!
@Jason: Thank you!
Very well explained - thank you! It's rare to find this kind of high quality tutorials (for free).
Glad it was helpful!
I want to cry at how much you saved me. I've been trying to understand this unit for the past 2 days. This 13 min video helped me more than everything I have trie so far. I am literally in tears while I am writing this comment. THANK YOU SO MUCH!!!!!!
You're very welcome, Freddy!
Thanks a lot.I am a teacher of Further Mathematics in Cameroon and I find your tuts very helpful!!
@Oto Oto: That's great! How old are your students?
When I searched "Chinese Remainder Theorem" on TH-cam, this video is by far the easiest to understand. Thank you!
Great to know that it's so useful. Thank you for your feedback.
The numbers are so small that I solved this problem in my head after a few minutes whilst watching the video. I just tried to find a values of x such that x = 6 + 8y, where y = 1,2,3, ... 9 (I stopped here) as 6 + 8x9 = 78, and x = 78 satisfied all three congruences.
Well done!
"Beautiful, Beautiful, something close to genius." THANK YOU SO MUCH!!!!
Wow, thank you!
The extended euclidean algorithm really helps instead of trial or error for finding inverse.I have had some luck writing a computer program for it and now I wanted to understand the chinese remainder theorem and incorporate the the algorithm into it,but I was having a hard time until i came upon this video which blew my mind.Thank you so much,I have been stuck for days struggling with number theory and this helps so much.Please make more videos.
So glad to know how helpful this is. Thank you for your detailed feedback
The BEST and most clear explanation I've seen of this. I finally understand, thank you!!
You're very welcome!
Thank you for going through all the steps no matter how simple. It made it very easy to follow.
@Snow Dawner: It's great to know how much you appreciate this. Thank you!
That is THE best explanation I've seen for this. Thank you, this has helped me a lot and I don't think I'll ever forget this easy way of solving it. Thanks!
Thank you so much!
Thank you so much for this, I have been having so much trouble understanding this and this video has made it so easy to understand.
@Aeril: Thank you!!
I wish I found your channel at the start of my semester, but better late than never! 💃🏾💃🏾💃🏾 You're a wonderful teacher.
Thank you so much!
Poland here, thank you for this video. The best explained CRT on TH-cam
@Yekoss: Greetings to you in Poland from London, England. Thank you for your great feedback!
thank you so much , this method is way easier than using the euclidean algorithm which gets quite confusing when finding the inverse
You're welcome
Thank you so much, this was really helpful! I'm a third year maths undergraduate and have always struggled with the Chinese Remainder Theorem from the moment we learned it in Abstract Algebra in first year, but will definitely be using this method from now on. I have a number theory exam in two days so fingers crossed this helps! ^.^
Glad it was helpful! Good luck with your exam!
This is very helpful. I have been struggling to solve this process chinese remainder theorem. You made it easier to learn.
Glad it helped!
I hadn't get the concept so clear like this in youtube. Thank u
@Niraj Kc: Thank you!
The best CRT explanation I have seen all over the internet ...Thank you so much ❤️
Wow, thank you!
Well explained! It's videos like this that make TH-cam such a fantastic resource for learning.
Wow, thanks!
In which class are you still you don't know about Chinese Remainder Theorem i am in 10 standard
Thank you so much for this video I've been struggling like hell for the past three days trying to learn this!
Glad I could help!
The math books I have are horrible at explaining it. They are all written by people who forget how hard this is to an outsider. This video was the best so far.
Thank you!
Abhishek,
CRT you explained beautifully ; no doubt.
Thank you! Your video helped me finish my assignment.
Excellent!
Thanks! I audited a number theory course in college, but got too busy to do the homework, and absorbed very little as a result. Great refresher!
Excellent!
Now I don't have to cram the example I have on my notes, I give you 100% for the tutorial 👏👏👏
@Katlego Mojela: Thank you! Very generous marking!
Even though I do have some tutorials in my native language which is Polish, this video was more helpful. Now I understand this and I'm ready for my exam
Glad it helped! Good Luck in your exam!
Clear and precise, really loved the explanation and the checking methods
@Anonymous AnimeLover: Thank you so much!
In India Artabhatta 1 invented in kuttaka ,ie pulverised system. He was born in 476 AD in India and possibly headed Belanda University.. See reminder theorem linear and Pell equation invented by brahma gupta in 628 AD. For all info see bbdatta ana ansingh book hindu mathematics. May be available in internet archive.
Interesting...thank you for sharing
This was great for helping me implement as programming function! I stumbled upon this video and It saved me so time and much pain!
Glad it helped!
Thanks!! Just learnt something I could not learn from fancy books.
Glad I could help!
Without a doubt the best explanation I’ve seen!! You are awesome..thank you you’re a wonderful teacher!
Wow, thank you!
💯% Clear explanation.🇵🇭 Thanksss!
@ryan rock: Thank you!
I have a homework and I following your steps to solve it. Thank you so much ^^
You're welcome 😊
This was a great explanation. I keep forgetting how to do this, but your explanation is very intuitive!
Great to hear!
This video is the definition of life saving thanks alot !!
You're welcome!
Thank you so much to recall my college maths in a very clear way.
Happy to help!
Very simple and clear explanation. Much appreciated !
Glad it was helpful!
You are the best thanks so much!!!
Welcome!
Thanks, founding a good explenation of this topic was harder than way through The Misty Mountains in winter, you helped as much as eagles could help!
You're very welcome!
For finding the inverse, I personally find it easier to add ni to the right term until I get a multiple of the left term parameter. At least when the left term parameter is such that it is easy to check if a number divides it.
Thanks for sharing
You might be my hero of the day
Oooh!
wonderful video, crystal clear. i was able to implement Python code for this trivially, especially since Python 3.8 provides the function for the modular inverse with a simple call to `x = pow(Ni,-1,m)`, no libraries needed
Thank you Silviana, That's good to know
Thank you, i didn't know how to implement the inverse with trial and error.
Brahma gupta formula 5x + 3 -1 is divisible by 7, 5x+2 is divisible by 7 when x =1, then number is 7 satisfying two conditions, third is now 5x7 k + 8 - 6 is divisie by 8 or 3k + 2 s divisible by 8, then k =2, , then number is 35x2+ 8 =78. It is done in 650 AD, much before Chin Sao in 1247 AD. Gauss popularised Chinese theorem.
Do you have a link to a website or book?
You may read Chinese Mathematics by Ulrich liberchit and history of Hindu mathematics, BB Datta and Avadesh Narayan Singh. Issue of remainder theorem is part of Linear Indeterminate Analysis initiated by Aryabhatta 1, 476 - 550 ad. solution of equation ax - by = +- c, Uniqueness is positive integer solutions. But , Brahmagupta added algebra , add negative integer solutions also. Western people highlighted Diophantus who solved rational solution Bhaskara 1 solved ax -by =1, this could be used as modulo purpose. This crypitc two verses were elaborated by Bhaskara 1 600 ad 680 ad. Interesting feature is bhaskara 1, Brahmagupta 598 -665ad, Mahavira 850 ad , Aryabhatta ii, and Bhaskara ii, between them , many commentators there, each one modified the generic form. Besides, all of them added many inputs. Brahmagputra with 1000 verses, out of two chapters Ganitadhya (arthmatic) and Kuuttakadhya (Algebra)by T H Colebrook . U could get some of them from internet archive. Brahmaputra NX^2+c = y^2. , 67x^+1= y^2 , N is a non squared prime number , you have to solve 101x^+1 = y ^2. Procedure was improved by jaydeva of 9th century and finally 11th century by Chakravala method.. Cyclic method.but western people named Pell equation . My email kantoprasad@gmail.com, KPSinha , Delhi India.
Fantastic lucid explanation......
Glad you liked it
This is really helpful. Very simple to understand. Thanks
Glad to hear that!
Thank you so much! everything I looked at made it look so hard. your explanation is great and simple!
@Mostafa El Kindy: Excellent! Thank you for letting us know!
Thank you so much for the clear explanation. Your video really help me for a project in my crypto class.
Glad it helped!
Tomorrow is my final paper and it just saved me on right time thanks a lot 😍😍😍😍😍😍
Good luck!!
It's very simple.. Thanks a lot mam
Most welcome 😊
The method is offical but seems to be a bit complicate. Just take the two largest multiple 7 and 8 we can immediate see 77 and 72 respectively. Then 77+1 and 72+6 That 78 fulfil 7 and 8. We then verify 5 remain 3. Simple
Why not make your own video to show your method?
You're amazing thank you so much for sharing this video and explaining concept in a way that finally makes sense to me!!!
You're so welcome!
thank you so much for this absolutely BEAUTIFUL explanation.
Glad you enjoyed it!
This a very clear and simple explanation, Thank you so much !
@James: Thank you!
Thank you for making it easy for us to understand.
Glad it was helpful!
Tomorrow's my exam❤️ thamkss i get it now!
That's great! Good Luck!
Thank you, great and clear explanation! Cheers from Egypt! :)
@Hazem Essam: Glad it was helpful! How is life in Egypt? London is cold and we're just starting to come out of lockdown...
@@MathsWithJay We are starting to come out of lockdown as well starting next week, but a full lockdown was never implemented anyway just a partial curfew with schools and closure of cafes/restaurants. The weather here is starting to be very nice but unfortunately beaches remain closed :( I was moving to London by the end of July but everything is put on hold because of what's going on 🤦
Yesterday some of England's beaches were overwhelmed by visitors...we now have unusually hot weather for a few days. Restaurants and museums hope to open on 4th July, but schools are not planning for pupils to be back until September
Hello! You're one dedicated teacher, Jay.. this is one concept that looked unsurmountable, and you've helped me become competent in a matter of 13 minutes.. thank you so much.
Wow, thanks!
If u want to work out the sum, whose principle was invented by ArgBhatt 1 and fine-tune by Brahmsvupts., 5x +3-1=5x+2 is divine by 7 , then x =1,,Number satisfying both is 8, Next number is 5x7k+ 8, 35k +8 -6=35k+2 is divisible by 8,is, 3k+2 =6,, minimum value of k is 2, then ,number is 35x2+8=78. Chinese Remain set theorem was invented by Chin Chia Shao in 1247 ad, Brahmaputra gave this easy or OK cess in 625 AD, Aryabhatta 1 theeorised it in cryptic Sanskrit in 499 ad. Chinese Remainder theorem was popularised. By Gauss.
Wow, impressive
Good Job...keep going love from Bangla
Thank you so much 😀
Thanks a lot for the explaination
You are welcome
thank you a lot! this video helped me out quite good and i hopefully will perform as good as i can at the midterm too..
Best of luck!
@@MathsWithJay thanks!
Thanks a ton for this brilliant tutorial!
@Paras Gathani: Thank you so much!
gem of a video.
Thank you!
Amazingly clear explaination!
@Pleo Lin: Glad you think so!
Amazing explanation
Glad it was helpful!
Well presented. Requesting you to see the same 500 years ahead Btahmagupta' s theorem. Quicker and faster.
Do you have a link?
this video is extremly helpful. thanks alot!
Glad it was helpful!
The best explaination ever. thanks alot.
@Sahil Raman: Thank you!!
Great explanation thanks
Glad it was helpful!
This really helps a lot. Thank you 😊
You're welcome 😊
Thank you so much for outstanding explanation
You are most welcome!
I'm so glad I'm class of 2026 because otherwise I wouldn't have this video to watch.
2026?
loved the video even tho i dont study in english !!!!!
That's great! What's your language?
35x3 = 1(mod8) .,. is that not equal to 4x3 = 1 (mod8) ??
@Umair Tariq: At what time in the video?
@@MathsWithJay At 9:30 minute.
Thank you so much. I had headache understanding this
Glad it helped!
U r a Perfectionist 😍❤️🇮🇳
Really?
@@MathsWithJay Yes❤️❤️
Wow simple and great explanation.
@Wild Fire: Thank you so much!
you are just awsome lots of love 🥰such a patient.. delicate explanation i love it...
@TECH &TOM: Thank you!
Though it's helpful....During these quarantine period....learning from online classes is not that much easy....hoping for things to fix...In sha Allah
I hope so too
Thank you so much for making this video!
@Aiswarya Rajendran: My pleasure - thank you!
Nice video @maths with Jay , could you please help me with this:
By raising 7 ≡ 5^x(mod 18) to the powers 2 and 3, we get:
13 ≡ 7^x(mod 18) and 1 ≡ 17^x(mod 18), respectively.
Solving DLP in the first subgroup gives us x ≡ 2 (mod 3). What is x in the second subgroup?
How to use the Chinese Remainder Theorem (using PARI) to find x in the original DLP instance.
Thanks for your feedback. Sorry I'm busy marking and preparing students for exams...maybe someone else can answer your question...
Thanks for ur explanation
@SJ Franz: Thank you!
Bro ur a life saver
You're welcome!
I dont understand this video especially on the 7:18 part. please explain .
thank you very much. this is so simple
@ummi fadilah: Glad it helped!
What a great explanation!!
@Diego Bravo: Thank you!
Can anyone explain the last step. How did you get 78
At what time in the video?
Do you know how resolve this chinese remainder problem?
x=2 mod 5
2x= 1 mod 7
3x=4 mod 11
@Jose Perez: Start by solving the second 2 congruences so that all three lines start with just an x.
@@MathsWithJay
x=2 mod 5
2x= 1 mod 7 => 2x=1+7 mod 7 => 2x=8 mod 7 => 2x/2=8/2 mod 7 => x=4 mod 7
3x=4 mod 11=> 3x=4+11 mod 11 => 3x=15 mod 11 => 3x/3=15/3 mod 7 => x=5 mod 11
========
x=2 mod 5
x=4 mod 7
x=5 mod 11
The second one should be 4+11=15, not 1+11=12?
@@MathsWithJay Thank you.
Chinese Remainder Theorem in Geogebra
www.geogebra.org/m/axbnga42