I'm also from Morocco are you a student? high school
9 หลายเดือนก่อน
salam i m not student but an old man having a university level lover and interested in السلام ورحمة الله..لست طالبا بل رجل كبير السن ذي مستوى جامعي ومهتم ومحب للرياضياتMathematics@@theoryofbadr6507
This video has made me emotional. At my university, we are expected to solve systems of congruence equations yet we've not been lectured on how to do it. I have been trying to find out how to do it for almost 2 hours. This by far is the only TH-cam video that shows the method in an easy-to-understand way. Thank you so so so much. I'm ready for my discrete maths test next week :)
Wow @judepope6196! I'm so glad to hear this! My hope in making this video is that questions like this become just a little bit easier. Best of luck on your discrete maths test! You've got this!
Thank you for making a tutorial on a number theory related topic!! This is one of my favorite areas of mathematics and was the last course I took to wrap up my Master's last year. I remember learning this theorem but your column organization of moduli, inverses, and remainders makes it SO much easier to follow, especially when a problem like this requires a long process! I love how you took the time to explain the general case first, breaking down what each variable and subscript represented, and laying out the "flow-chart"/"game plan" for how to do this for any system of linear congruences. It flowed very smoothly into your specific example and made it very easy to follow. I also thought it was great how you plugged in the result at the end to make sure the remainders were valid - this reinforces checking our work which is something often forgotten! Thanks for this AWESOME breakdown on such a fascinating theorem/field of math! Always look forward to your weekly videos and this is one I will DEFINITELY remember!! 👍👍
Thank you so much! Number Theory was your grand finale to your Master's Degree?! Wow!! I bet that feels like such an accomplishment to have your Master's Degree done. There are some really cool applications of linear congruences and modular arithmetic such as code breaking for example. Did you do any of those as part of your Master's program?
@@CalculusbyChristee Definitely happy to be done with it - took awhile but glad I did it early on in my career! Yes, Number Theory was a fun course to end with. My professor incorporated a lot of cryptography/code-breaking applications throughout the course, as they related to the different skills we were learning. We started early on in the course with the more simple algorithms, like the Caesar and Vigenère ciphers, that relied on basic modular arithmetic. In the middle once we hit the linear congruences you mentioned above, we were able to talk about the Hill Cipher. Near the later part of the course, by the time we learned about modular inverses, Fermat's Little Theorem, and quadratic residues/primitive roots, we were able to dive into the more popular/interesting RSA public-key algorithm and ElGamal cryptosystem algorithm that use public/private secret keys between senders. This code-breaking/cryptography component was the most fascinating aspect of the course to me and my professor gave us some fun assignments where we would encrypt our own codes and it became an exercise for our classmates to decipher our codes - it was fun because we were able to make it personable/relatable to our own interests while still practicing the algorithms and the techniques in the course. One of my favorite courses I've ever taken! As a high school teacher, I feel like "The Mathematics of Cryptography/Code Breaking" could be a fun semester course for high school students to give them a little introduction to some number theory concepts with some fun applications to this very relatable and widely used field! Something I hope to maybe make happen someday - would take some planning/organization but I feel like kids would really find it interesting and it could open their eyes to a specific field of applied mathematics they haven't seen before. 😁
@@camwizemusic2802 Wow!! That is fascinating! Thank you for sharing! Great idea on the course! That would be something I imagine a lot of students would be interested in! Students love games and puzzles and I feel that would really pique their interest!
To clarify, different Sun Tzu from the art of war guy. This one's a mathematician. Also, the theorem was actually formulated by qin jiu shao, as an answer to a question formulated by math Sun Tzu in his book 孙子算经
...A very good day to you Miss Christee, I think this time you chose exactly the kind of topic (my anxiety trigger) that always gives me the shivers and so I start doubting myself if I'm actually cut out for math (lol). I thought I was starting to like you a bit by now, and then this happens (lol). Perhaps now is the time to take this topic seriously once and for all. In any case a subject where I don't lose sleep over the algebra content, but all the more because of the underlying interpretation! I'm good at mental arithmetic in general, to begin with. I will have to devide my thinking capacity between tutoring and number theory in the near future, but I promise to come back to this. Not only the procedure I want to learn, but also understand! For me this is a bit of a self-esteem issue (lol). I've written out quite a bit already and am starting to develop some understanding through structures that emerge... just be patient, okay? I hope you are doing well despite the developing pre-winter period! Thank you for your very important life lesson about Sun Tzu's Theorem, Miss Christee... Take good care, Jan-W p.s. In the past I regularly read short little books by, among others, the Chinese philosopher Confucius about ancient Chinese wisdom, and I must say that he was quite ahead of his time in terms of views on life...
Hi Jan! Never doubt yourself in math! You have a brilliant mind and are great at breaking things down so that you understand them. :) I think it's time to watch one of my developing math videos (slope-intercept form, perhaps?) to make that anxiety go away! lol I hope you are doing well! ~Christee (and Mollee too🐕)
I don't know *Chinese Remainder Theorem* so simply tried to solve the problem in the video without any significant mod arithmetic. x = 3a + 1 = 5b + 4 = 7c + 6 Therefore, (35x = 105a + 35) + (21x = 105b + 84) + (15x = 105c + 90) => (35 + 21 + 15 = 71) x = 105 (a + b + c) + (35 + 84 + 90 = 209) Therefore, 71 x = 209 mod 105 = -1 mod 105, therefore, x = (-1/71 = -1 * 71 = -71 mod 105) = 105 - 71 = 34. Hence *x = 34* without any need of Chinese Remainder Theorem.
I only started understanding it after I have coached math team for several years. Very interesting topic show up in math team like modular arithmetic, and it’s really interesting to learn about it! Lots of self teaching though! What courses do you teach at your school?
While it was easy to follow your explanation of the algorithm, there was no explanation provided to describe *why* it worked. Alternative approach that I like to use: I first solve the first two congruences. Notice that x = 1(mod 3) implies that there is a value 'a' such that x = 3*a + 1. Now, look at second equation. Notice that it says that x = 4 (mod 5). Since x = 3*a + 1, compute 3*a + 1 mod 5= 4. Hence, 3*a mod 5 = 3, or a= 1 so that x = 4. However, to be clear, this is 4 mod 15, so it is actually the case that x = 15*b + 4 for some value b. Now, we continue by computing x (i e 15*b + 4) mod 7. This tells us that 15*b +4 mod 7 = 6. This implies b = 2. Hence, x = 15*2+4 =34. Again, we must note that this is mod 105. The approach I described still needs to explain why the modulus needs to change from 3 to 15 to 105. And that indeed can be done, but the point is to show each step one at a time rather than a mysterious algorithm. For me, I know the CRT algorithm, and I know how and why it works. But I only know it because I have built up the intuition, and that seems to be missing from your presentation!
I appreciate your feedback. While I show both your method and the method I showed in this video to my students, I decided to show this particular method in this video. You are correct - this is definitely more of the algorithmic approach.
I totally agree. In my opinion, it is really pointless to have a math video that does not explain how the underlying algorithm works. This isn't chemistry.
Thank you so much! I appreciate the compliment :) My students say the same thing when I'm writing on the SMART board in class - and then when they come up to write on the board, they realize how hard it REALLY is! lol
It's important to understand the difference between a description and an explanation. The video describes the method (and works through an example) of the CRT, but certainly does not explain the CRT. The truth is that much of the time the CRT is a lot of work to achieve a simple goal. It has the advantage that following the algorithm accurately will provide a solution, but quite often, a little insight will yield a quicker solution. In particular, a solution found for two of the three congruences can quickly lead to a solution for all three. Taking the example from the video, the two larger bases are 5 and 7, and conveniently the remainders are equivalent to -1 in both cases, i.e. 4 ≡ - 1 (mod 5) and 6 ≡ -1 (mod 7). That means that x ≡ -1 (mod 35) will be a common solution for both since 5 * 7 = 35. But -1 ≡ 34 (mod 35), so x ≡ 34 is a solution to the second and third congruences. That means we are looking for a multiple of 34 that also satisfies the first congruence x ≡ 1 (mod 3) and that can only be 34 * 1 or 34 * 2 (since 3 and 35 are coprime). We can immediately see that x ≡ 34 satifsfies the first congruence as well as the second and third, so is our solution. It should be clear that if the first congruence had been x ≡ 2 (mod 3), then x ≡ 68 would be the solution. The above is a _explanation_ of a means of tackling the problem presented, and hopefully the insights may be helpful. Nevertheless, if we are dealing with large numbers and shortcuts are not obvious, then the CRT will always give solutions as long as the congruences are independent, so is worth knowing.
Thanks so much! When 35 is divided by 3 (that's what we should think about with a mod of 3), there would be a remainder of 2. That is why 35 was able to change to 2 in mod 3. 4 in mod 3 also has a remainder of 1, that is why 1 was able to be changed to 4. Since when 4 is divided by 3 there is a remainder of 1. I hope this helps!!
@@CalculusbyChristee Although this helps with finding out why 35 becomes 2, why specifically does 1 become 4? 4 mod 3 has a remainder of 1, but so does 7 mod 3, 10 mod 3, etc. Could we get clarification on that?
@@andrewscott1153 Ahhh yes, a great question! Because I changed 35 mod 3 to 2 (2 is the remainder when 35 is divided by 3), I wanted the other side to be divisible by 2. That's why I changed it to 4 so that I could then divide 4 by 2 to get the answer of 2. You make a great point - what about 7 or 10?! If I had changed it to 7, I wouldn't be able to divide 7 by 2. If I had changed it to 10, I COULD divide it by 2. Then I would get 5, which, in mod 3 is still 2! (the remainder is 2 when 5 is divided by 3) You are absolutely right - I could have kept choosing positive numbers that are all divisible by 2, but in the end they would all give an answer of 2 for the remainder in mod 3. I hope this helps!
Hello thanks for the video Just a clarification, it seems that Sun Tzu is also the name of author of the Art of War but is not the same person. Per wikipedia, the art of war author came before the writer of Sunzi Suanjing (孫子算經, Master Sun's Mathematical Manual) which contained Sun’s remainder theorem. en.wikipedia.org/wiki/Sunzi_Suanjing
Thank you for adding this in and for your clarification! When I was researching Sun Tzu, I also came across the name of the author of the Art of War. Other resources showed the remainder theorem was authored by Sun Tzu (a different Sun Tzu). However, this resource (www.britannica.com/science/Chinese-remainder-theorem) references Sun Zi's work and even Qin Jiushao, who first provided this theorem. Different resources mention different mathematicians - further emphasizing the unfortunate fact that these brilliant mathematicians were overlooked and replaced with only their nationality. Thank you for providing your clarification. I really appreciate it!
As a mathematics student and a advanced certificate holder from The Science of Strategy institute, and an English-Mandarin speaker/reader, having published fictional work bilingually and regularly do bilingual subs professionally i can also confirm through both ends (math and 孫子兵法) that they are of no relation. However, the Buddhist diety Sun Ping, who famously popularized his grandad's work in real life, is related and is ironic because sun Tzu means grand child. However his granddads formal address is also his relationship through homophones or whatever to his granddad (孫子 means grandchild, but when 孫 is a family name, then anciently 子 means master, although not in any actual sentence (師父). Its just a lot of interesting coincidences. However Master Sun's first name was Wu, ironically the same name as the kingdom he ended up taking a contract for to protect against larger hostile neighborhood. So Sun Wu had a lot of weird phonetic, and almost as often, written coincidences.
I got 34 myself, but wouldn't it actually be 34+105n, where n is any integer? The modulus values should line up again after every 105 terms. I simply did it by noticing that 1 (mod 3) and 4 (mod 5) would occur any time you get 4 plus a multiple of 15. Then I checked 19 and then 34.
The answer is actually x ≡ 34 (mod 105) so you're quite right. Although when we know we're dealing with congruences, it's common to see the equals sign used when we're talking about the member of a congruence class that lies between 0 and the modulus. Personally, I find it a bit sloppy, but I think most folk wouldn't worry about it.
Actually it is a practical method of finding the unknow figure for a group of people. We use 3, 5 and 7 as grouping and all we need is to remenber the formula I have shown out above then we can figure out the number of the group
Hi there! In order to use this theorem, the moduloes need to be co-prime. For special cases with non co-prime moduloes, you would need to first reduce the system to moduloes that are only co-prime. I didn't cover this in this video, but this is a great suggestion for a future video. Thank you!
The list given at the start isnt to hard to find a number for. Like.... 34 works. But once you start getting to a list of 4 or 5 conditions, it's really hard. The more constraints, generally, the larger the number becomes
PLS. YOU ARE SO Fast in explaining!... I dont understand the part in 7:47 whichi is inverse congruence.. do you have a topic on this so that I could understand this?
The modular multiplicative inverse is the value you need to multiply by to produce a number that would have a remainder of 1 with the given mod. There is an algorithm that can be used to find the inverse, but oftentimes it is more efficient to use guess-and-check with reasonable values to find the inverse. I hope this helps!
this made me realize modular arithmetic is really not taught in the united states or at least in my state. before taking highschool comp sci, the last time i even saw remainders was in 4th grade. its a shame because primes and remainders are so useful and i have zero intuition in regards to either.
I completely agree with you! I find the mathematics of remainders and primes to be really fascinating, yet it’s never taught in the high school curriculum. The only time I get to teach it to my students is when I coach the Math Team. And they really love when I teach them about modular arithmetic!
Follow the method Christee described. In her example, there are three linear congruences with index ì being 1,2,3. If only two linear congruence, index ì would be 1,2. The table of columns r, m, x, rmx will have two rows (not three rows). Christee, you description was clear and methodical. Your intention was to describe the process using an example. Good presentation.
Hello, I have a question. In my task we have 3 sets, as following: 1st: 2x + 2 = 4 mod 5; 2nd: 3x + 2 = 3 mod 4; x +2 = 1 mod 3. How do I go forward to solve this? How do I get the x alone as in this example?
This is a really good question! If I'm understanding it correctly, I think you can do this: Start by subtracting the constant from both sides: 2x + 2 = 4 mod 5 becomes 2x = 2 mod 5 then divide both sides by 2, x = 1 mod 5 For the second one: 3x + 2 = 3 mod 4 becomes 3x = 1 mod 4 But because 1 can't be divided by 3 to get an integer, keep adding 4 to the right-hand side until the number on the right is divisible by 3. So, use 3x = 9 mod 4 then divide by 3 to get x = 3 mod 4 And then you can do something similar for the third linear congruence. Then, you would have three linear congruences with x alone and that can be solved using the theorem in my video. I hope this helps!! :)
@@CalculusbyChristee For completeness, the third congruence is x + 2 ≡ 1 (mod 3), so x ≡ -1 (mod 3). We see that the second congruence x ≡ 3 (mod 4) is equivalent to x ≡ -1 (mod 4), so x ≡ -1 (mod 12) must be a solution to both, or x ≡ 11 (mod 12) That also solves x ≡ 1 (mod 5), so we have our full solution, x ≡ 11 (mod 60). HTH.
The modular multiplicative inverse is the value you need to multiply by to produce a number that would have a remainder of 1 with the given mod. There is an algorithm that can be used to find the inverse, but oftentimes it is more efficient to use guess-and-check with reasonable values to find the inverse. I hope this helps!
Hello - 2:00 - you forgot to express what that chineese theorem says :) Sun Tzu wouldnt be proud of using his name without saying which theorem is it all about ;)
I have watched hours of modular arithmetic and still haven't found a good way to solve a seemingly simple problem and it is driving me nuts. How do i solve a (linear) equation like 9m+5 =4n+3, with m and n being natural numbers? I could use the CRT for x = 5 mod 9 and x = 3 mod 4, and then use x to find m and n, but there got to be a simpler way to do it. So if anybody can straighten it out for me, or direct me to the right topic, it would be highly appreciated.
I'll explain the simple, quick, easy way here (but the downside is you will miss many solutions...) The best way when you have one equation with two integer unknowns is to use Diophantine equation techniques (and you just gave me a GREAT idea for a future video! :) So, the quick, easy way (but not the best way): First, rewrite the equation to isolate m and n: 9m - 4n = -2 Now, notice that the right side of the equation is a constant (-2). To find natural number solutions for m and n, you can try different values of m and solve for n. Start with m = 1 and increase it until you find a natural number solution for n. Let's try m = 1: 9(1) - 4n = -2 9 - 4n = -2 4n = 11 n = 11/4 Since n must be a natural number, this solution doesn't work. Now, try m = 2: 9(2) - 4n = -2 18 - 4n = -2 4n = 20 n = 20/4 n = 5 This solution works because both m and n are natural numbers. A video on Diophantine Equation Techniques to come in the future! :)
@@CalculusbyChristee wow, a quick answer, and from mam herself. You just got a new subscriber. Unfortunately i can't do any guesswork, it is for a program working with extremely large numbers, which is also why i want to limit the number of computations. The missing solutions would be easy to find, but i do only care for the smallest positive solution. Anyway, thank you very much for taking your time, i guess it just is harder than i expected, and i can calm down knowing that i am not missing something obvious ;)
You usually solve linear Diophantine equations algorithmically by repeated substitution. You isolate the variable with the smaller coefficient on the LHS like this: 4n = 9m + 2 You divide through by that coefficient: n = 2m + (m+2)/4 Now, n and 2m are integers, so (m+2)/4 must also be an integer, so let's set an integer a = (m+2)/4 which gives us 4a = m + 2 (note for later that n = 2m + a). Then we get m = 4a - 2 That's enough to generate our solutions when a = { 1, 2, 3, ... } since a=0 makes m = -2 (not a natural number). If we still had the first coefficient ≠ 1, we could repeat the division and substitution, etc. getting smaller and smaller coefficients unti we reach 1. Anyway, when a=1, we get m = 2 and because n = 2m + a, we get n = 5. When a=2, we get m = 6 and because n = 2m + a, we get n = 14. When a=3, we get m = 10 and because n = 2m + a, we get n = 23. (m, n) = (4a-2, 9a-4) is the full solutions set you wanted.
Not the same Sun Tzu ("Master Sun") who wrote the Art of War, but another "Master Sun" who lived several centuries later. According to Wikipedia - not a Chinese expert here :) en.wikipedia.org/wiki/Sunzi_Suanjing
Yes! Thank you! ☺️ Whenever I would Google “Sun Tzu” to try to learn about him, the author of the Art of War was all that appeared. I had to search for “Sun Tzu Chinese Remainder Theorem” and I was able to get more information and see various spellings of his name. Thank you for providing the link!
It is somehow easier like this. Multiply the first equation by 5: 5X = 5 mod 15 Multiply the second by 3: 3X = 12 mod 15 We can now easily subtract: 2X = -7 mod 15, adding 0 == 15 mod 15 yield: 2X = 8 mod 15 (check, X = 4 solves indeed eq.1 and eq.2) X = 4 mod 15 Multiply it by 7: 7X = 28 mod 105 Multiply the original third equation by 15: 15X = 90 mod 105 Subtract: 8X = 62 mod 105 The inverse of 8 in mod 105 is 92: X = 92 x 62 mod 105 ( since 92 x 8 == 1 in mod 105, so (92 * 8) X == 1X mod 105)) = 34 mod 105 (check: ok for original eq. 1, 2 and 3) --------------------------------------------------- You can find the inverse of 8 in mod 105 using the Bezout's identity, or by using one of the many "Multiplicative Inverse Modulo Calculator" available on the web.
Note: we can go to X = 4 mod 15 from 2X = 8 mod 15 since the gcd(2, 15) = 1. And in fact, it is not required to reduce to 1 X , if we don't want to check the validity of the computation in the middle of the progression toward the final solution.
I understand there are several ways to solve this problem. And I might even make another video in the future with a different method! Some may find this method useful to help them solve the question, while others may not prefer this method. Thank you for sharing your thoughts!
I think the problem would need to have a variable? If it’s 120x2, which is 240, this would be congruent to 0 in mod 20, rather than congruent to 1 like in your problem. That’s just my thought when looking at it!
This is a common question, so thank you for bringing it up! Yes, Sun Tzu (a different Sun Tzu) wrote the Art of War. The mathematician who worked on this theorem (and unfortunately has not been credited for his work because it was coined the "Chinese Remainder Theorem" instead) is sometimes spelled Sun Tzu and sometimes Sun Zi. This theorem also was proven completely through the work of Qin Jiushao. www.britannica.com/science/Chinese-remainder-theorem proofwiki.org/wiki/Chinese_Remainder_Theorem/Historical_Note
I appreciate your insights. However, the explanation of the algorithm is not sufficient. Moreover, what we try to figure out is unanswered. Frankly, I regret to say that I didn't any of the steps. Also, I felt the algorithm makes the matter very difficult to comprehend
Thank you for your feedback. I understand that I have only shown one way you can approach a problem like this and I love how this problem can be creative because it can be solved in different ways! How would you approach a problem like this? I love hearing about other creative methods!
Using the word "Chinese" instead of the person's name reminds me of the case (ethnicity bias?) when referring to a Chinese restaurant down the street, instead of calling its name, people just say "the Chinese restaurant" 🤨
Wow, so true. Once I heard about how European mathematicians have their name as the name of the theorem, but Sun Tsu never received the recognition, it was definitely something that made me think… he deserves the credit! It was very upsetting. Please excuse me as I head to Happy Wok for some delicious food. ☺️
@@CalculusbyChristee Imagine Newton's Law's of Motion being call European Law's of Motion and Albert's Einstein Theory of Relativeity be called Jwesih Theory of Relativity lol
@@anshul6168 That's SO true! That would NEVER have been done! Wow, that really brings this into perspective. Those mathematicians/scientists will live on in infamy and Sun Tzu will never get the credit he deserved. Thanks for these great examples
Thanks for posting this really nice video! It has rekindled my interest in number theory 😃. I guess the theorem itself is that there exists exactly one solution (modulo, in this case, M = 105), and obtains only when the m_i are co-prime. People wishing to deepen their understanding might look at the article on wikipedia: "Chinese remainder theorem" en.wikipedia.org/wiki/Chinese_remainder_theorem ~~~~Arthur Ogawa
from Morocco thank you Christee for the full clear explanation 🌻🌻🌻🌻 i share your video on facebook
Hello to you in Morocco!!
Thank you!! 🌻🌻🌻🌻
And thank you for sharing on Facebook! I hope it can be helpful to a lot of people!
you are welcome...for sure such videos as yours will be helpful @@CalculusbyChristee
I'm also from Morocco are you a student? high school
salam i m not student but an old man having a university level lover and interested in السلام ورحمة الله..لست طالبا بل رجل كبير السن ذي مستوى جامعي ومهتم ومحب للرياضياتMathematics@@theoryofbadr6507
This video has made me emotional. At my university, we are expected to solve systems of congruence equations yet we've not been lectured on how to do it. I have been trying to find out how to do it for almost 2 hours. This by far is the only TH-cam video that shows the method in an easy-to-understand way. Thank you so so so much. I'm ready for my discrete maths test next week :)
Wow @judepope6196! I'm so glad to hear this! My hope in making this video is that questions like this become just a little bit easier.
Best of luck on your discrete maths test! You've got this!
How do you written 35x1 congruent to (1mod3) as 2x1 congruent to 4 (mod3).
35x1 = 33x_1 + 2x_1 and you can ignore the 33x_1 since its mod 3. And 1 and 4 are equal mod 3
That is by far the most clear and understandable math video I have ever seen. Thank you
Thank you for making a tutorial on a number theory related topic!! This is one of my favorite areas of mathematics and was the last course I took to wrap up my Master's last year. I remember learning this theorem but your column organization of moduli, inverses, and remainders makes it SO much easier to follow, especially when a problem like this requires a long process! I love how you took the time to explain the general case first, breaking down what each variable and subscript represented, and laying out the "flow-chart"/"game plan" for how to do this for any system of linear congruences. It flowed very smoothly into your specific example and made it very easy to follow. I also thought it was great how you plugged in the result at the end to make sure the remainders were valid - this reinforces checking our work which is something often forgotten! Thanks for this AWESOME breakdown on such a fascinating theorem/field of math! Always look forward to your weekly videos and this is one I will DEFINITELY remember!! 👍👍
Thank you so much!
Number Theory was your grand finale to your Master's Degree?! Wow!! I bet that feels like such an accomplishment to have your Master's Degree done.
There are some really cool applications of linear congruences and modular arithmetic such as code breaking for example. Did you do any of those as part of your Master's program?
@@CalculusbyChristee Definitely happy to be done with it - took awhile but glad I did it early on in my career! Yes, Number Theory was a fun course to end with. My professor incorporated a lot of cryptography/code-breaking applications throughout the course, as they related to the different skills we were learning. We started early on in the course with the more simple algorithms, like the Caesar and Vigenère ciphers, that relied on basic modular arithmetic. In the middle once we hit the linear congruences you mentioned above, we were able to talk about the Hill Cipher. Near the later part of the course, by the time we learned about modular inverses, Fermat's Little Theorem, and quadratic residues/primitive roots, we were able to dive into the more popular/interesting RSA public-key algorithm and ElGamal cryptosystem algorithm that use public/private secret keys between senders. This code-breaking/cryptography component was the most fascinating aspect of the course to me and my professor gave us some fun assignments where we would encrypt our own codes and it became an exercise for our classmates to decipher our codes - it was fun because we were able to make it personable/relatable to our own interests while still practicing the algorithms and the techniques in the course. One of my favorite courses I've ever taken! As a high school teacher, I feel like "The Mathematics of Cryptography/Code Breaking" could be a fun semester course for high school students to give them a little introduction to some number theory concepts with some fun applications to this very relatable and widely used field! Something I hope to maybe make happen someday - would take some planning/organization but I feel like kids would really find it interesting and it could open their eyes to a specific field of applied mathematics they haven't seen before. 😁
@@camwizemusic2802 Wow!! That is fascinating! Thank you for sharing!
Great idea on the course! That would be something I imagine a lot of students would be interested in! Students love games and puzzles and I feel that would really pique their interest!
To clarify, different Sun Tzu from the art of war guy. This one's a mathematician. Also, the theorem was actually formulated by qin jiu shao, as an answer to a question formulated by math Sun Tzu in his book 孙子算经
...A very good day to you Miss Christee, I think this time you chose exactly the kind of topic (my anxiety trigger) that always gives me the shivers and so I start doubting myself if I'm actually cut out for math (lol). I thought I was starting to like you a bit by now, and then this happens (lol). Perhaps now is the time to take this topic seriously once and for all. In any case a subject where I don't lose sleep over the algebra content, but all the more because of the underlying interpretation! I'm good at mental arithmetic in general, to begin with. I will have to devide my thinking capacity between tutoring and number theory in the near future, but I promise to come back to this. Not only the procedure I want to learn, but also understand! For me this is a bit of a self-esteem issue (lol). I've written out quite a bit already and am starting to develop some understanding through structures that emerge... just be patient, okay? I hope you are doing well despite the developing pre-winter period! Thank you for your very important life lesson about Sun Tzu's Theorem, Miss Christee... Take good care, Jan-W p.s. In the past I regularly read short little books by, among others, the Chinese philosopher Confucius about ancient Chinese wisdom, and I must say that he was quite ahead of his time in terms of views on life...
Hi Jan! Never doubt yourself in math! You have a brilliant mind and are great at breaking things down so that you understand them. :)
I think it's time to watch one of my developing math videos (slope-intercept form, perhaps?) to make that anxiety go away! lol
I hope you are doing well!
~Christee (and Mollee too🐕)
I don't know *Chinese Remainder Theorem* so simply tried to solve the problem in the video without any significant mod arithmetic.
x = 3a + 1 = 5b + 4 = 7c + 6 Therefore, (35x = 105a + 35) + (21x = 105b + 84) + (15x = 105c + 90) => (35 + 21 + 15 = 71) x = 105 (a + b + c) + (35 + 84 + 90 = 209)
Therefore, 71 x = 209 mod 105 = -1 mod 105, therefore, x = (-1/71 = -1 * 71 = -71 mod 105) = 105 - 71 = 34. Hence *x = 34* without any need of Chinese Remainder Theorem.
Wonderful! Thank you for sharing!
Thank you. The CRT. is the most beautiful theorem in Mathematics.
Finally I found a video that helps me. Thank you
I am so glad to hear this! Great! ☺️
Your way of teaching style is great
Thank you so much! I appreciate it! I'm glad you're finding it helpful.
Someday I'll be able to make more sense of this when I have a better understanding of the basic vocabulary/building blocks necessary. Thanks.
I only started understanding it after I have coached math team for several years. Very interesting topic show up in math team like modular arithmetic, and it’s really interesting to learn about it! Lots of self teaching though!
What courses do you teach at your school?
While it was easy to follow your explanation of the algorithm, there was no explanation provided to describe *why* it worked. Alternative approach that I like to use: I first solve the first two congruences. Notice that x = 1(mod 3) implies that there is a value 'a' such that x = 3*a + 1. Now, look at second equation. Notice that it says that x = 4 (mod 5). Since x = 3*a + 1, compute 3*a + 1 mod 5= 4. Hence, 3*a mod 5 = 3, or a= 1 so that x = 4. However, to be clear, this is 4 mod 15, so it is actually the case that x = 15*b + 4 for some value b. Now, we continue by computing x (i e 15*b + 4) mod 7. This tells us that 15*b +4 mod 7 = 6. This implies b = 2. Hence, x = 15*2+4 =34. Again, we must note that this is mod 105.
The approach I described still needs to explain why the modulus needs to change from 3 to 15 to 105. And that indeed can be done, but the point is to show each step one at a time rather than a mysterious algorithm. For me, I know the CRT algorithm, and I know how and why it works. But I only know it because I have built up the intuition, and that seems to be missing from your presentation!
I appreciate your feedback.
While I show both your method and the method I showed in this video to my students, I decided to show this particular method in this video.
You are correct - this is definitely more of the algorithmic approach.
I like your constructive algorithm~~~~Arthur Ogawa
I totally agree. In my opinion, it is really pointless to have a math video that does not explain how the underlying algorithm works. This isn't chemistry.
Your handwriting is really nice!
Thank you so much! I appreciate the compliment :) My students say the same thing when I'm writing on the SMART board in class - and then when they come up to write on the board, they realize how hard it REALLY is! lol
Im have an exam tomorrow u are just from saving me. Thanks a bunch😊
Thanks for this video, it's easy to understand
Thankyou mam
Your class is very helpful for all teachers exam 🙏🙏
That’s great to hear! Thank you so much!! 🥰
It's important to understand the difference between a description and an explanation. The video describes the method (and works through an example) of the CRT, but certainly does not explain the CRT. The truth is that much of the time the CRT is a lot of work to achieve a simple goal. It has the advantage that following the algorithm accurately will provide a solution, but quite often, a little insight will yield a quicker solution. In particular, a solution found for two of the three congruences can quickly lead to a solution for all three.
Taking the example from the video, the two larger bases are 5 and 7, and conveniently the remainders are equivalent to -1 in both cases, i.e. 4 ≡ - 1 (mod 5) and 6 ≡ -1 (mod 7). That means that x ≡ -1 (mod 35) will be a common solution for both since 5 * 7 = 35. But -1 ≡ 34 (mod 35), so x ≡ 34 is a solution to the second and third congruences. That means we are looking for a multiple of 34 that also satisfies the first congruence x ≡ 1 (mod 3) and that can only be 34 * 1 or 34 * 2 (since 3 and 35 are coprime). We can immediately see that x ≡ 34 satifsfies the first congruence as well as the second and third, so is our solution. It should be clear that if the first congruence had been x ≡ 2 (mod 3), then x ≡ 68 would be the solution.
The above is a _explanation_ of a means of tackling the problem presented, and hopefully the insights may be helpful.
Nevertheless, if we are dealing with large numbers and shortcuts are not obvious, then the CRT will always give solutions as long as the congruences are independent, so is worth knowing.
Thank you so much from Germany :)
I love to hear that you’re watching from Germany! Thank you! ☺️
Very high quality video.
Thank you so much! I appreciate it!
Good stuff, to the point but also well explained
Thank you so much!
Wow, very impressive theorem.
Great video! 😃
I'm just wondering though, how did you get from 35x1 ≡ 1 (mod 3) to 2x1 ≡ 4 (mod 3)?
Thanks so much!
When 35 is divided by 3 (that's what we should think about with a mod of 3), there would be a remainder of 2. That is why 35 was able to change to 2 in mod 3.
4 in mod 3 also has a remainder of 1, that is why 1 was able to be changed to 4. Since when 4 is divided by 3 there is a remainder of 1.
I hope this helps!!
glad I wasn't the only one wondering about this!
@@CalculusbyChristee Although this helps with finding out why 35 becomes 2, why specifically does 1 become 4? 4 mod 3 has a remainder of 1, but so does 7 mod 3, 10 mod 3, etc. Could we get clarification on that?
@@andrewscott1153 Yes, I'm glad someone asked! Because I'm sure that means more people have the same question :)
@@andrewscott1153 Ahhh yes, a great question! Because I changed 35 mod 3 to 2 (2 is the remainder when 35 is divided by 3), I wanted the other side to be divisible by 2. That's why I changed it to 4 so that I could then divide 4 by 2 to get the answer of 2. You make a great point - what about 7 or 10?! If I had changed it to 7, I wouldn't be able to divide 7 by 2. If I had changed it to 10, I COULD divide it by 2. Then I would get 5, which, in mod 3 is still 2! (the remainder is 2 when 5 is divided by 3) You are absolutely right - I could have kept choosing positive numbers that are all divisible by 2, but in the end they would all give an answer of 2 for the remainder in mod 3. I hope this helps!
Hello
thanks for the video
Just a clarification, it seems that Sun Tzu is also the name of author of the Art of War but is not the same person. Per wikipedia, the art of war author came before the writer of Sunzi Suanjing (孫子算經, Master Sun's Mathematical Manual) which contained Sun’s remainder theorem.
en.wikipedia.org/wiki/Sunzi_Suanjing
Thank you for adding this in and for your clarification! When I was researching Sun Tzu, I also came across the name of the author of the Art of War. Other resources showed the remainder theorem was authored by Sun Tzu (a different Sun Tzu). However, this resource (www.britannica.com/science/Chinese-remainder-theorem) references Sun Zi's work and even Qin Jiushao, who first provided this theorem. Different resources mention different mathematicians - further emphasizing the unfortunate fact that these brilliant mathematicians were overlooked and replaced with only their nationality.
Thank you for providing your clarification. I really appreciate it!
As a mathematics student and a advanced certificate holder from The Science of Strategy institute, and an English-Mandarin speaker/reader, having published fictional work bilingually and regularly do bilingual subs professionally i can also confirm through both ends (math and 孫子兵法) that they are of no relation.
However, the Buddhist diety Sun Ping, who famously popularized his grandad's work in real life, is related and is ironic because sun Tzu means grand child. However his granddads formal address is also his relationship through homophones or whatever to his granddad (孫子 means grandchild, but when 孫 is a family name, then anciently 子 means master, although not in any actual sentence (師父).
Its just a lot of interesting coincidences. However Master Sun's first name was Wu, ironically the same name as the kingdom he ended up taking a contract for to protect against larger hostile neighborhood. So Sun Wu had a lot of weird phonetic, and almost as often, written coincidences.
@@CalculusbyChristee In fairness, *many* things in math (and science generally) are *not* named after the 1st person who found them.
Your digital whiteboard handwriting is very beautiful...
Thank you so much. I really appreciate it! ☺️
I got 34 myself, but wouldn't it actually be 34+105n, where n is any integer? The modulus values should line up again after every 105 terms.
I simply did it by noticing that 1 (mod 3) and 4 (mod 5) would occur any time you get 4 plus a multiple of 15. Then I checked 19 and then 34.
The answer is actually x ≡ 34 (mod 105) so you're quite right. Although when we know we're dealing with congruences, it's common to see the equals sign used when we're talking about the member of a congruence class that lies between 0 and the modulus. Personally, I find it a bit sloppy, but I think most folk wouldn't worry about it.
Actually it is a practical method of finding the unknow figure for a group of people. We use 3, 5 and 7 as grouping and all we need is to remenber the formula I have shown out above then we can figure out the number of the group
This makes sense, even though I didn't follow some of the language about inverses.
Do you cover the case where the moduloes are not co-prime?
Hi there! In order to use this theorem, the moduloes need to be co-prime. For special cases with non co-prime moduloes, you would need to first reduce the system to moduloes that are only co-prime. I didn't cover this in this video, but this is a great suggestion for a future video. Thank you!
So helpful, thanks!
either i missed that or you did not mention that you found the smallest (positive) solution. this IS important.
You are absolutely correct. That IS important and I definitely could have missed that important point in my video. Thank you!
The list given at the start isnt to hard to find a number for. Like.... 34 works. But once you start getting to a list of 4 or 5 conditions, it's really hard. The more constraints, generally, the larger the number becomes
That’s a very good point! I agree!
Looks like it has application to cryptography. The modulo work helps understand Shors algorithm. The prime requirement is interesting.
Yes it is! I’m glad that you mentioned this. So true!
One of the numbers is x=3a+1=5b+4=7c+6
3a=5b+3,5b=7c+2
So c=4,b=6,a=11
x=3×11+1=34
General value of x=34+LCM(3,5,7)k=34+105k,k is an integer.
PLS. YOU ARE SO Fast in explaining!... I dont understand the part in 7:47 whichi is inverse congruence.. do you have a topic on this so that I could understand this?
The modular multiplicative inverse is the value you need to multiply by to produce a number that would have a remainder of 1 with the given mod. There is an algorithm that can be used to find the inverse, but oftentimes it is more efficient to use guess-and-check with reasonable values to find the inverse. I hope this helps!
thank you maam.
@@CalculusbyChristee
7:42 where that 4 came from??????????? It does not make any sense
this made me realize modular arithmetic is really not taught in the united states or at least in my state. before taking highschool comp sci, the last time i even saw remainders was in 4th grade. its a shame because primes and remainders are so useful and i have zero intuition in regards to either.
I completely agree with you! I find the mathematics of remainders and primes to be really fascinating, yet it’s never taught in the high school curriculum. The only time I get to teach it to my students is when I coach the Math Team. And they really love when I teach them about modular arithmetic!
what if there are only two linear congruences?
Follow the method Christee described. In her example, there are three linear congruences with index ì being 1,2,3.
If only two linear congruence, index ì would be 1,2. The table of columns r, m, x, rmx will have two rows (not three rows).
Christee, you description was clear and methodical. Your intention was to describe the process using an example. Good presentation.
Hello, I have a question. In my task we have 3 sets, as following: 1st: 2x + 2 = 4 mod 5; 2nd: 3x + 2 = 3 mod 4; x +2 = 1 mod 3. How do I go forward to solve this? How do I get the x alone as in this example?
This is a really good question! If I'm understanding it correctly, I think you can do this:
Start by subtracting the constant from both sides:
2x + 2 = 4 mod 5 becomes
2x = 2 mod 5
then divide both sides by 2,
x = 1 mod 5
For the second one:
3x + 2 = 3 mod 4 becomes
3x = 1 mod 4
But because 1 can't be divided by 3 to get an integer, keep adding 4 to the right-hand side until the number on the right is divisible by 3.
So, use 3x = 9 mod 4
then divide by 3 to get
x = 3 mod 4
And then you can do something similar for the third linear congruence. Then, you would have three linear congruences with x alone and that can be solved using the theorem in my video. I hope this helps!! :)
@@CalculusbyChristee For completeness, the third congruence is x + 2 ≡ 1 (mod 3), so x ≡ -1 (mod 3).
We see that the second congruence x ≡ 3 (mod 4) is equivalent to x ≡ -1 (mod 4), so x ≡ -1 (mod 12) must be a solution to both, or x ≡ 11 (mod 12)
That also solves x ≡ 1 (mod 5), so we have our full solution, x ≡ 11 (mod 60). HTH.
Remember the answer when we face 3,5 and 7 we just apply 70 x reminder of 3 + 21 x reminder of 5 + 15x reminder of 7 then subtract the 105 plus
How you find out the inverse xi. ?
The modular multiplicative inverse is the value you need to multiply by to produce a number that would have a remainder of 1 with the given mod. There is an algorithm that can be used to find the inverse, but oftentimes it is more efficient to use guess-and-check with reasonable values to find the inverse. I hope this helps!
thanks i understand now .
@@CalculusbyChristee
i have quation : x ≡ 2 mod 7, x ≡ 3 mod 8, x ≡ 1 mod 3.@@CalculusbyChristee
i find answer 25 but is not correct
Yes, I don’t believe 25 will work when substituted for x in your problem. Did you try to find the answer using the method I showed in this video?
DO YOU HAVE A TUTORIAL ON LINEAR CONGRUENCES / INVERSE MOD? IT IS SO DIFFICULT... i DONT KNOW WHAT TO DO? PLS. RESPOND...
Hello - 2:00 - you forgot to express what that chineese theorem says :) Sun Tzu wouldnt be proud of using his name without saying which theorem is it all about ;)
Valid point!
I see this from India 👍❤️
That’s great!! 👍🏼👍🏼
Good one🎉
Wonderful to hear 🥰
I still dont know how to get Xi
nice video 🙂
thank you !
thank youuu
You are very welcome! ☺️
Can you help me with this, please:
x ≡ 2 (mod 11)
x ≡ 9 (mod 15)
x ≡ 7 (mod 9)
x ≡ 5 (mod 7) ?
15 and 9 are not relatively prime. So, this theorem does not apply.
I have watched hours of modular arithmetic and still haven't found a good way to solve a seemingly simple problem and it is driving me nuts.
How do i solve a (linear) equation like 9m+5 =4n+3, with m and n being natural numbers?
I could use the CRT for x = 5 mod 9 and x = 3 mod 4, and then use x to find m and n, but there got to be a simpler way to do it.
So if anybody can straighten it out for me, or direct me to the right topic, it would be highly appreciated.
I'll explain the simple, quick, easy way here (but the downside is you will miss many solutions...) The best way when you have one equation with two integer unknowns is to use Diophantine equation techniques (and you just gave me a GREAT idea for a future video! :)
So, the quick, easy way (but not the best way):
First, rewrite the equation to isolate m and n:
9m - 4n = -2
Now, notice that the right side of the equation is a constant (-2). To find natural number solutions for m and n, you can try different values of m and solve for n. Start with m = 1 and increase it until you find a natural number solution for n.
Let's try m = 1:
9(1) - 4n = -2
9 - 4n = -2
4n = 11
n = 11/4
Since n must be a natural number, this solution doesn't work.
Now, try m = 2:
9(2) - 4n = -2
18 - 4n = -2
4n = 20
n = 20/4
n = 5
This solution works because both m and n are natural numbers.
A video on Diophantine Equation Techniques to come in the future! :)
@@CalculusbyChristee wow, a quick answer, and from mam herself. You just got a new subscriber.
Unfortunately i can't do any guesswork, it is for a program working with extremely large numbers, which is also why i want to limit the number of computations.
The missing solutions would be easy to find, but i do only care for the smallest positive solution.
Anyway, thank you very much for taking your time, i guess it just is harder than i expected, and i can calm down knowing that i am not missing something obvious ;)
You usually solve linear Diophantine equations algorithmically by repeated substitution.
You isolate the variable with the smaller coefficient on the LHS like this: 4n = 9m + 2
You divide through by that coefficient: n = 2m + (m+2)/4
Now, n and 2m are integers, so (m+2)/4 must also be an integer, so let's set an integer a = (m+2)/4 which gives us 4a = m + 2 (note for later that n = 2m + a).
Then we get m = 4a - 2
That's enough to generate our solutions when a = { 1, 2, 3, ... } since a=0 makes m = -2 (not a natural number). If we still had the first coefficient ≠ 1, we could repeat the division and substitution, etc. getting smaller and smaller coefficients unti we reach 1.
Anyway, when a=1, we get m = 2 and because n = 2m + a, we get n = 5.
When a=2, we get m = 6 and because n = 2m + a, we get n = 14.
When a=3, we get m = 10 and because n = 2m + a, we get n = 23.
(m, n) = (4a-2, 9a-4) is the full solutions set you wanted.
@@RexxSchneider Thank you.
Don't know how you took value of x1, x2, x3,
From India 🇮🇳
I've got this confusing topic
So happy to hear it ☺️☺️
Not the same Sun Tzu ("Master Sun") who wrote the Art of War, but another "Master Sun" who lived several centuries later. According to Wikipedia - not a Chinese expert here :)
en.wikipedia.org/wiki/Sunzi_Suanjing
Yes! Thank you! ☺️ Whenever I would Google “Sun Tzu” to try to learn about him, the author of the Art of War was all that appeared. I had to search for “Sun Tzu Chinese Remainder Theorem” and I was able to get more information and see various spellings of his name. Thank you for providing the link!
I thought he just developed an interest in Maths after several centuries of hearing people quote The Art of War to him and having to sign autographs.
❤❤❤❤❤ 5:54
It is somehow easier like this.
Multiply the first equation by 5: 5X = 5 mod 15
Multiply the second by 3: 3X = 12 mod 15
We can now easily subtract: 2X = -7 mod 15, adding 0 == 15 mod 15 yield:
2X = 8 mod 15 (check, X = 4 solves indeed eq.1 and eq.2)
X = 4 mod 15
Multiply it by 7: 7X = 28 mod 105
Multiply the original third equation by 15:
15X = 90 mod 105
Subtract: 8X = 62 mod 105
The inverse of 8 in mod 105 is 92:
X = 92 x 62 mod 105 ( since 92 x 8 == 1 in mod 105, so (92 * 8) X == 1X mod 105))
= 34 mod 105 (check: ok for original eq. 1, 2 and 3)
---------------------------------------------------
You can find the inverse of 8 in mod 105 using the Bezout's identity, or by using one of the many "Multiplicative Inverse Modulo Calculator" available on the web.
Note: we can go to X = 4 mod 15 from 2X = 8 mod 15 since the gcd(2, 15) = 1. And in fact, it is not required to reduce to 1 X , if we don't want to check the validity of the computation in the middle of the progression toward the final solution.
This is great! Thank you for sharing this method!
I use it in playing cards
That’s a great application!
❤❤❤❤
Most complex method to solve the question 😢
I understand there are several ways to solve this problem. And I might even make another video in the future with a different method! Some may find this method useful to help them solve the question, while others may not prefer this method. Thank you for sharing your thoughts!
@@CalculusbyChristee But need those another methods now cause tomorrow's the exam 😑
@@letsboomithow did the test go letsboomit
I haveva doubt
So in the case of 120x2 ≡ 1(20) how should we proceed since we get 0x2
Is this in relation to the problem I presented or a new problem?
@@CalculusbyChristee New problem
I think the problem would need to have a variable? If it’s 120x2, which is 240, this would be congruent to 0 in mod 20, rather than congruent to 1 like in your problem. That’s just my thought when looking at it!
7+6+3*7=34
This theorem is nothing to do with Sun Tzu, who supposedly wrote Art of War.
This is a common question, so thank you for bringing it up! Yes, Sun Tzu (a different Sun Tzu) wrote the Art of War. The mathematician who worked on this theorem (and unfortunately has not been credited for his work because it was coined the "Chinese Remainder Theorem" instead) is sometimes spelled Sun Tzu and sometimes Sun Zi. This theorem also was proven completely through the work of Qin Jiushao.
www.britannica.com/science/Chinese-remainder-theorem
proofwiki.org/wiki/Chinese_Remainder_Theorem/Historical_Note
I appreciate your insights. However, the explanation of the algorithm is not sufficient. Moreover, what we try to figure out is unanswered. Frankly, I regret to say that I didn't any of the steps. Also, I felt the algorithm makes the matter very difficult to comprehend
Thank you for your feedback. I understand that I have only shown one way you can approach a problem like this and I love how this problem can be creative because it can be solved in different ways! How would you approach a problem like this? I love hearing about other creative methods!
You failed to explain the MOST important part of finding xi.
Girls can do maths😢?
Yes we can! :)
female teachers (with a bearable voice lol) are the best!
Using the word "Chinese" instead of the person's name reminds me of the case (ethnicity bias?) when referring to a Chinese restaurant down the street, instead of calling its name, people just say "the Chinese restaurant" 🤨
Wow, so true. Once I heard about how European mathematicians have their name as the name of the theorem, but Sun Tsu never received the recognition, it was definitely something that made me think… he deserves the credit! It was very upsetting.
Please excuse me as I head to Happy Wok for some delicious food. ☺️
@@CalculusbyChristee Imagine Newton's Law's of Motion being call European Law's of Motion and Albert's Einstein Theory of Relativeity be called Jwesih Theory of Relativity lol
@@anshul6168 That's SO true! That would NEVER have been done! Wow, that really brings this into perspective. Those mathematicians/scientists will live on in infamy and Sun Tzu will never get the credit he deserved. Thanks for these great examples
Thanks for posting this really nice video! It has rekindled my interest in number theory 😃. I guess the theorem itself is that there exists exactly one solution (modulo, in this case, M = 105), and obtains only when the m_i are co-prime.
People wishing to deepen their understanding might look at the article on wikipedia: "Chinese remainder theorem" en.wikipedia.org/wiki/Chinese_remainder_theorem ~~~~Arthur Ogawa
Thank you so much! ☺️ I appreciate it!
Thank you for including the wikipedia link. That’s a great idea!