Thank you for the video. Another video mentioned that (bi and ni) must be relatively prime and I didn't understand why. Your video confirms that they don't have to be. One minor correction though. The sum is 274. Probably the 7 looked like a 1 and you wrote is as 214.
The proof video says all the ni should be relatively prime to one another, which is important for the constructive proof of existence. If the ni are relatively prime then each Ni is guaranteed to be relatively prime to its associated ni, ensuring the existence of its multiplicative inverse mod N. There are no requirements on the bi. If the ni are not relatively prime then the problem could just be reduced to one where they are relatively prime. Then you'll find that either (1) some of the requirements (x = bi mod ni) are redundant, or (2) some of the requirements contradict each other and a solution won't exist. A requirement like x = 7 (mod 15) is really two requirements on 15's prime factors: x = 7 (mod 3) = 1 (mod 3) and x = 7 (mod 5) = 2 (mod 5). If there was another separate requirement like x = 1 (mod 3) then it would be redundant with x = 7 (mod 15) and could be ignored. But if there was one that said x = 2 (mod 3) then there would be no solution, because there is no x such that x = 1 (mod 3) AND x = 2 (mod 3). And some other requirement mod 21 would have another mod 3 requirement that was redundant or conflicting. In this way any problem statement with non-coprime ni could be massaged so they would be coprime.
We can't find a unique x *among all the integers*. The best we can do is find a unique x (mod N). In this case (if he had written it correctly) x = 274 (mod 60). But that means any x = 274 + 60k will work, for all integers k, including 274-60=214 and 274-4*60=34. Usually when we want to find a solution mod N we give the value between 0 and N-1 because it's the most "fundamental" solution. But sometimes it's important to remember that we're really talking about an infinite number of solutions, moving up and down the number line by multiples of N. If you ever study groups in abstract algebra they're called equivalence classes mod N.
274 is the real sum in the last step, which is confusing because 214 is also a solution. But 34 = 274 (mod 60). Maybe my reply to Shravan Balaji gives more detail.
X must be equal to 20a+15b+12c(mod 60). As x=1(mod 3), a must be equal to 2.As x=2(mod 4), b must be equal to 2. As x=4(mod 5), c must be equal to 2. Hence, x=20×2 +15×2+ 12×2 (mod 60) =94(mod 60) =34(mod 60).
I'll assume you meant x3, not y3. If that's the case, he's looking for the *multiplicative inverse* of 12 (mod 5). That is, he's looking for x3 such that 12 * x3 = 1 (mod 5). To simplify that calculation, though it's not strictly necessary, we can reduce 12 (mod 5) to 2 (mod 5). So we are looking for x3 such that 2 * x3 = 1 (mod 5). From there it's easy to see that x3 = 3 will work. In his video on the proof of the CRT he explains why we need the multiplicative inverse. Also, if you check your solution of 46 against the original question you can see it doesn't work; it's not equivalent to 4 (mod 5). I like Michael's videos but I wish he would check his solutions in the videos. I think it's an invaluable habit to develop and I think he could lead by example.
Love your style. All content, no nonsense.
Professor Penn, thank you for showing a solid example of the Chinese Remainder Theorem.
Am amazed at how much solving consists of a complementary (in this case congruent to 1) and a particular solution to produce the general answer.
Thank you for the video. Another video mentioned that (bi and ni) must be relatively prime and I didn't understand why. Your video confirms that they don't have to be. One minor correction though. The sum is 274. Probably the 7 looked like a 1 and you wrote is as 214.
Thanks for catching that! It is so easy to make little mistakes like that.
Don't they have to be relatively prime for the Ns to have inverses? Pretty sure that's still a stipulation.
Michael Penn are
Plus it is still a solution so a simple check will not catch the error!
The proof video says all the ni should be relatively prime to one another, which is important for the constructive proof of existence. If the ni are relatively prime then each Ni is guaranteed to be relatively prime to its associated ni, ensuring the existence of its multiplicative inverse mod N. There are no requirements on the bi.
If the ni are not relatively prime then the problem could just be reduced to one where they are relatively prime. Then you'll find that either (1) some of the requirements (x = bi mod ni) are redundant, or (2) some of the requirements contradict each other and a solution won't exist.
A requirement like x = 7 (mod 15) is really two requirements on 15's prime factors: x = 7 (mod 3) = 1 (mod 3) and x = 7 (mod 5) = 2 (mod 5). If there was another separate requirement like x = 1 (mod 3) then it would be redundant with x = 7 (mod 15) and could be ignored. But if there was one that said x = 2 (mod 3) then there would be no solution, because there is no x such that x = 1 (mod 3) AND x = 2 (mod 3). And some other requirement mod 21 would have another mod 3 requirement that was redundant or conflicting.
In this way any problem statement with non-coprime ni could be massaged so they would be coprime.
How did he get from 20X1 to 2X1, 15X2 to 3X2 and 12X3 to 2X3?
Thanks for another wonderful demonstration! Hopefully, after watching enough of your videos, less of my number theory ignorance will remain...
Just wow ...fan of your explanation ❤
wait but when I checked the value 214, it worked. Does that mean you subtract N from the whole thing?
It is a fortunate coincidence that his mistake was off by 60 which means both 274 (actual sum) and 214 (typo) are congruent modulo 60
We can't find a unique x *among all the integers*. The best we can do is find a unique x (mod N). In this case (if he had written it correctly) x = 274 (mod 60). But that means any x = 274 + 60k will work, for all integers k, including 274-60=214 and 274-4*60=34.
Usually when we want to find a solution mod N we give the value between 0 and N-1 because it's the most "fundamental" solution. But sometimes it's important to remember that we're really talking about an infinite number of solutions, moving up and down the number line by multiples of N. If you ever study groups in abstract algebra they're called equivalence classes mod N.
Where did the 1 come from in N1X1 = 1(mod 3)?
Is it always 1? Or is it always smallest b?
Where does the 34 come from?
274 is the real sum in the last step, which is confusing because 214 is also a solution. But 34 = 274 (mod 60). Maybe my reply to Shravan Balaji gives more detail.
X=1 mod3
X=2 mod4
X=4 mod5
---------------------------------
20X=20 mod60 -------(1)
15X=30 mod60 -------(2)
12X=48 mod60 -------(3)
(2) - (3)
3X= - 18 ------------------(4)
(4) X7 - (1)
X=-146 = 34 mod60
Ans. 34
You can multiply both sides of equation only if the multiplier is coprime with the mod number
@@MilanStojanovic9 You can't divide , but you can multiply.
@@azumamurakami7842 my bad
X must be equal to 20a+15b+12c(mod 60). As x=1(mod 3), a must be equal to 2.As x=2(mod 4), b must be equal to 2.
As x=4(mod 5), c must be equal to 2.
Hence, x=20×2 +15×2+ 12×2 (mod 60)
=94(mod 60)
=34(mod 60).
Yes that's a slight mistake
Does y3 is equal to 2 not 3? because 12 (mod 5) is equal to 2 (mod 5). please im very confuse now. final answer must be 46 (mod 60). 😵
I'll assume you meant x3, not y3. If that's the case, he's looking for the *multiplicative inverse* of 12 (mod 5). That is, he's looking for x3 such that 12 * x3 = 1 (mod 5). To simplify that calculation, though it's not strictly necessary, we can reduce 12 (mod 5) to 2 (mod 5). So we are looking for x3 such that 2 * x3 = 1 (mod 5). From there it's easy to see that x3 = 3 will work.
In his video on the proof of the CRT he explains why we need the multiplicative inverse.
Also, if you check your solution of 46 against the original question you can see it doesn't work; it's not equivalent to 4 (mod 5). I like Michael's videos but I wish he would check his solutions in the videos. I think it's an invaluable habit to develop and I think he could lead by example.
How come that 2.20.1+3.15.2+3.12.4=214??? It should be 274 in total. Now I'm confused😅