For those that don't skip steps: 15L = 2 (mod 7) => 15L = 7k + 2 for some k in the integers Let k = 2T where T is an integer => 15L = 14T + 2 => L = 14T - 14L + 2 => L = 7(2T - 2L) + 2 Let H = (2T - 2L), then H is an integer. => L = 7H + 2 => L = 2 (mod 7)
You can already reduce the first step. 15l =2 (mod 7) equivalent to l = 2 (mod 7) (since 15 = 2 * 7 + 1). Mod equations are linear. This means you can reduce factors and addends with the module. Not exponents, though. Also, while you can't divide (in general), you can multiply, and you can find a multiplicative inverse if the number you start with is relatively prime to the module. So if the second equation had simplified to 3k = 4 (mod 5), for such small modules, you can just try it out, and see that 2*3 = 6 = 1 (mod 5) (for larger modules you may need the extended Euclidean algorithm). So you can multiply both sides with 2 instead of dividing by 3 (which leads to k = 3).
Yes we know the rules, this was to provide a proof without skipping steps on how this is true: "15l =2 (mod 7) equivalent to l = 2 (mod 7) (since 15 = 2 * 7 + 1)."
zach p Yes I skipped many steps and didn't label any of them with Axioms. The purpose was a proof of the statement without skipping steps around the mod magic going on rather than a step by step guide through the axioms. I've taken a course which specifically required each step to be outlined and labeled like you mentioned and you quickly get used to it: 15L = 2 (mod 7) "Assumption" => 15L = 7k + 2 for any k in the integers, "by definition of mod" Choose k = 2T where T is an integer (2 and T are integers => 2T is an integer "closure") => 15L = 7(2T) + 2 "Substitution" => 15L = (7*2)T + 2 "Associative multiplication" => 15L = 14T + 2 "Multiplication" => 15L - 14L = (14T + 2) - 14L "Subtraction on both side" => L15 - 14L = (14T + 2) - 14L "Commutative multiplication" => L15 - L14 = (14T + 2) - 14L "Commutative multiplication" => L(15 - 14) = (14T + 2) - 14L "Factorize" => L*1 = (14T + 2) - 14L "Subtraction" => L = (14T + 2) - 14L "Multiplication" => L = (2 + 14T) - 14L "Commutative addition" => L = 2 + (14T - 14L) "Associative addition" => L = (14T - 14L) + 2 "Commutative addition" => L = (7*2T - 14L) + 2 "Multiplication" => L = ((7*2)T - (7*2)L) + 2 "Multiplication" => L = (7*(2T) - (7*2)L) + 2 "Commutative multiplication" => L = (7*(2T) - 7*(2L)) + 2 "Commutative multiplication" => L = 7(2T - 2L) + 2 "Factorize" Let H = (2T - 2L), then H is an integer since: 2 and T are integers => 2T is an integer "closure" 2 and L are integers => 2L is an integer "closure" 2T and 2L are integers => 2T - 2L is an integer "closure" => L = 7H + 2 "Substitution" => L = 2 (mod 7) "Definition of mod"
Honestly, I've been having to teach myself modular arithmetic and discrete mathematics for school and have been struggling for so long and this was SO freaking useful. You explain things so well, it's amazing. Thank you so much, man! Thank you for making math so easy to comprehend and so enjoyable.
Thank you SO much! THIS ACTUALLY HELPED ME!!! And the fact that I only needed to watch the video once to understand this, it shows that you're great at explaining things!
I love those. Although, when tutoring my students for university entrance exams, i used to tell them to go with trial and error (just try out all but one of the choices till one fits). But I love solving them, really enjoyed that. Thanks.
This was so informative. Thank you so much!! You made it clear on how to do it but I wish there was just a few more explanations on the modular arithmetic rules. Thank you nonetheless. Well done. Thanks so much!
If you want to learn more about the CRT, try going for the bezout's identity and the extended euclidean algorithm (which is used to find the bezout's identitiy).
Damn thanks a lot!!! This was really helpful!! Stuck in quarantine due to corona virus thing and stuck with Chinese remainder theorem too xD!! Helped a lot!!❤️
When the system contains small numbers for the mod (like 3), you can often take a short-cut. Whatever solution we have for these sort of systems, we can always generate another solution by adding or subtracting the product of the modulo bases, in this case 3 x 5 x 7 = 105. Hopefully, that is self-evident, since 105 congruent 0 (mod 3 or mod 5 or mod 7). So if a solution exists, it has to be between 0 and 105. Also note that in this problem 4 congruent -1 (mod 5) and 6 congruent -1 (mod 7). That means that -1 satisfies the second and third congruencies, as does -1 + 35n where n is an integer. Since we only need examine the range 0 to 105, we only need to look at 35 -1 and 70 -1 to see if they satisfy the first congruence. Of course, 34 does. The small amount of work necessary is because 3 is such a small number, so we only need to look a two possibilities in the range.
I had a similar solution: cong 1 mod 3 means "1 more than some multiple of 3" and cong 4 mod 5 and cong 6 mod 7 both mean "1 less than some multiple of 5, and 1 less than some mult of 7". We can merge the last 2 equations into cong 34 mod 35 (1 less than some multiple of BOTH 5 AND 7), then check if 35-2 is cong 0 mod 3, in this case we got the correct answer at 1st try! So just add 1 to 33 and x = 34
HAPPY 100K U DESERVED IT MAN! FOLLOWING U SINCE 10K for real though, i've learnt a lot of al-jabr, calculus and how to think in general with ur videos. Love the content. Keep it up. Greetings from chile. Grande chile jiji viendo esta wea cuando deberia estar estudiando historia jijiji pero grande bprp
Here's another quick method to answer this question. The first congruence 1 ( mod 3 ) can be changed to 4 (mod 3) since 1 and 4 are congruent mod 3. By the Chinese Remainder Theorem, the first congruence 4 ( mod 3 ) and second congruence 4 ( mod 5 ) can be rewritten as 4 ( mod 15 ). 4 ( mod 15 ) can be rewritten as 34 ( mod 15 ) since 4 and 34 are congruent mod 15. Then the last congruence 6 ( mod 7 ) can rewritten as 34 ( mod 7 ) since 6 and 34 are congruent mod 7. By the Chinese Remainder Theorem, 34 ( mod 15 ) and 34 ( mod 7 ) is equivalent to 34 ( mod 105 ). Any integer of the form 105m + 34 satisfies the system of congruences just like you said. Thanks for the videos!!
Better video ever covering chinese remainder system, all talk about using bézout theorem and getting inverse mod something kinda, but its hard and beyond 2 congruences it becomes a mess , thank u so much
Last 2 equation give x ≡ -1 (mod5) x ≡ -1 (mod7) and therefore x ≡ -1 (mod 35) x = 35k -1 35k -1 ≡ 1 (mod3) 35k ≡ 2 (mod3) 2k ≡ 2 (mod3) k ≡ 1 (mod3) k = 3m+1 x = 35(3m+1)-1=105m+34
Our sir gave us a similar question to this, which came in a previous RMO paper and it goes as follows : Find the smallest x for which : x is congruent to 2(mod4) x is congruent to 3(mod5) x is congruent to 1(mod7) The trick is here deriving a relation between k1, k2 and k3 by equating all of them by expressing them all in x-b=kz form. Soln : by deriving a relation between k1 and k2 we see that that k1= 5n and k2 = 4n where n is an int, using this we can also equate k1 and k2 to k3, by expressing the third expression in the form x-2 = 7k3 - 4 And then finding k3.
4 mod 5 and 6 mod 7 are both one below their mod, therefore you can multiply 5 and 7 to make 35. Plug in 35k-1 to 1 mod 3. Add the +1 on each side and you get 35k being 2 mod 3. K=1 satisfies 2 mod 3 as well, therefore x = 33+2-1 or 34.
You should prove the Chinese reminder theorem because I never understood the proof hahahahaha. Btw, congratulations for reaching 100k subs! I've been here since before you reached 10k!
I don't know which part you didn't understand but the most important part is this. We add 3 things together, ax5x7 + bx3x7 + cx3x5. Why? Because whatever values we choose for a b c, the first term is 0 mod 5 and 0 mod 7 etc. This means that looking at solving for 1 mod 3 we only have to worry about the value of a and we are not messing up the other requirements. Therefore ax5x7=1 mod 3 35a=1 mod 3 2a=1 mod 3 a=2 Let me know if you need more clarification. Once you understamd why it works it becomes easy to remember as well.
The Chinese Remainder Theorem is best proven in Abstract Algebra. It becomes equivalent to finding an explicit isomorphism between certain groups, which is surprisingly straight forward.
I am a university student in Korea. You gave me great help for my math exam. Thank you for your effort. Keep hustling!! You used a bluepen in this video lol😂
Thank you profesor for your excellent videos. What about systems of congruences with no coprime modules,? do exist equivalent theorem to chinese remainders theorem,? could you explain it please,,?
Great discussion of the Chinese Remainder Theorem, but one thing’s missing. During the two steps you did here, you were able to easily simplify the two mod equations you got; the first one easily let you divide out 3, while the second one let you easily mod away the 15 to get 1. What is the more generic way to solve these mod equations? For example, in the example you gave, imagine omitting the second one. After you plug 3k+1 into the third mod, you get 3k=5 mod 7. Is there any way simpler than trial and error to solve this equation for k=4 mod 7?
I'm super glad I figured this out on my own! This modular arithmetic stuff is super easy for me (well, at least these basics, I'm sure there is Olympiad level stuff that will screw me over :p). Does anyone have any slightly harder modular arithmetic problems or puzzles?
Well explained. Although I wonder isn't it easier to start from largest devisor (which is 7 here) and then go to smaller ones. Shouldn't we get smaller numbers cause we are casting onto smaller fields?
"Division in modular arithmetic" is known as the "Cancellation Law" in algebra where ax≡ay implies that x≡y as long as a!≡0. I endorse +VeryEvilPettingZoo for having an excellent set of propositions derived from the very foundations of ring theory.
It has to be in the forms 3n+1, 5n-1, and 7n-1. The second two mean it has to be in the form 35n-1. Since we're looking for the smallest, it shouldn't take too long to try all of them. 34, being 35(1)-1, happens to also be 3(11)+1. That was easy.
How I think it would be more simple: If x=4=-1 mod 5 and x=6=-1 mod 7, we have that 5 and 7 divides x+1. Knowing that, we also have that 35 divides x+1, so we can write x+1=35k, for some natural number k. Looking x=35k-1 modulo k, we get x=2k-1 mod 3 and we have to have x=1 mod 3, so we have 2k-1=1 mod 3, so 2k=2 mod 3. It's easy to see that for k=1 it's true, and k=1 is the smalles value for which x is positive. So x=35*1-1=34 is the solution!
I used *_try & check_* to solve this problem. This approach is heuristically faster than the analytic approach when the modulos are small and quite close to each other in value like 3,5 and 7 are. I started with the biggest modulo. I.e the last congruence equation and tried x = 6, 13, 20, 27 and then x = 34. This last value satisfies the three congruences (easily check in ones head). We can stop looking at other values of x, as the CRT guarantees there is one and only one solution to the congruence equations. So, I then multiplied 3 × 5 × 7 to get 105. This works because 3,5 and 7 are relatively prime (they don't need to be prime, but if they are, then they are also relatively prime). So if x = 34 satisfies the congruence and then so too does x = 34 + 105k, where k is an integer and as 3 × 5 × 7 = 105. So, x = 34 (mod 105) is the general solution.
...and note that after the smallest such integer, there is an infinite series of greater integers with same property....and the common difference between each is the LCM, in this case, of 3, 5, and 7.
A general equation for the minimum number which gives remainders a,b,c when divided by 3, 5,7 can be written as below. N=70a+21b+15c + or - 105n, Where n = 0,1,2,3....... 'n' can be chosen in such a way that 'N' becomes minimum. Obviously N is the required number for the given remainders a,b,c. Congrats for system of congruences and solution.
I don't know if I fell through a gap in school but modular mathematics and any math involving matrices were not presented during a relatively standard mathematics path in HS. However, students in less advanced classes, thye seemed to be a core of at least a year of their math carreer in HS. It was very strange being near top of advanced math classes and completely lost when asked for help by other students. Hopefully that picture has changed because they are very useful ideas in later mathematics.
I realized that the mod 5 would either end in 4 or 9. Then I went through multiples of 7 that would end in 5 or 0. The first such example is *34,* which fits all the criteria. Thinking about it a bit more I could have realized that the last two are both mod -1, which means I could just find the least common multiple of 5 and 7, then subtract 2 and see if that's divisible by 3. If not, then double the answer and try again, then triple, and so on.
I did it like that: x --- 1 (mod 3) x --- 4 (mod 5) x --- 6 (mod 7) from first one I see it is also --- 4, and because the first two numbers in brackets are co-prime, I combined both to x --- 4 (mod 15) I created an equation 15k + 4 = 7l + 6 and by trial and error I got k=2, l=4, so x=34
You can't always. If it says x is congruent to 1(mod 2) and also x is congruent to 2(mod 4) there can be no solution. However something like x is congruent to 1(mod 2) and x is congruent to 1(mod 4), you can just use x ict 1(mod 4).
For those that don't skip steps:
15L = 2 (mod 7)
=> 15L = 7k + 2 for some k in the integers
Let k = 2T where T is an integer
=> 15L = 14T + 2
=> L = 14T - 14L + 2
=> L = 7(2T - 2L) + 2
Let H = (2T - 2L), then H is an integer.
=> L = 7H + 2
=> L = 2 (mod 7)
You can already reduce the first step. 15l =2 (mod 7) equivalent to l = 2 (mod 7) (since 15 = 2 * 7 + 1).
Mod equations are linear. This means you can reduce factors and addends with the module. Not exponents, though.
Also, while you can't divide (in general), you can multiply, and you can find a multiplicative inverse if the number you start with is relatively prime to the module. So if the second equation had simplified to 3k = 4 (mod 5), for such small modules, you can just try it out, and see that 2*3 = 6 = 1 (mod 5) (for larger modules you may need the extended Euclidean algorithm). So you can multiply both sides with 2 instead of dividing by 3 (which leads to k = 3).
Yes we know the rules, this was to provide a proof without skipping steps on how this is true:
"15l =2 (mod 7) equivalent to l = 2 (mod 7) (since 15 = 2 * 7 + 1)."
zach p Yes I skipped many steps and didn't label any of them with Axioms. The purpose was a proof of the statement without skipping steps around the mod magic going on rather than a step by step guide through the axioms. I've taken a course which specifically required each step to be outlined and labeled like you mentioned and you quickly get used to it:
15L = 2 (mod 7) "Assumption"
=> 15L = 7k + 2 for any k in the integers, "by definition of mod"
Choose k = 2T where T is an integer
(2 and T are integers => 2T is an integer "closure")
=> 15L = 7(2T) + 2 "Substitution"
=> 15L = (7*2)T + 2 "Associative multiplication"
=> 15L = 14T + 2 "Multiplication"
=> 15L - 14L = (14T + 2) - 14L "Subtraction on both side"
=> L15 - 14L = (14T + 2) - 14L "Commutative multiplication"
=> L15 - L14 = (14T + 2) - 14L "Commutative multiplication"
=> L(15 - 14) = (14T + 2) - 14L "Factorize"
=> L*1 = (14T + 2) - 14L "Subtraction"
=> L = (14T + 2) - 14L "Multiplication"
=> L = (2 + 14T) - 14L "Commutative addition"
=> L = 2 + (14T - 14L) "Associative addition"
=> L = (14T - 14L) + 2 "Commutative addition"
=> L = (7*2T - 14L) + 2 "Multiplication"
=> L = ((7*2)T - (7*2)L) + 2 "Multiplication"
=> L = (7*(2T) - (7*2)L) + 2 "Commutative multiplication"
=> L = (7*(2T) - 7*(2L)) + 2 "Commutative multiplication"
=> L = 7(2T - 2L) + 2 "Factorize"
Let H = (2T - 2L), then H is an integer since:
2 and T are integers => 2T is an integer "closure"
2 and L are integers => 2L is an integer "closure"
2T and 2L are integers => 2T - 2L is an integer "closure"
=> L = 7H + 2 "Substitution"
=> L = 2 (mod 7) "Definition of mod"
You don’t have to do that mess, and can just use modular substitution. Since 15 ≡ 1 (mod 7), 15 can be substituted with 1.
Not Your Average Nothing
As I mentioned before, this is to show the magic behind: "Since 15 ≡ 1 (mod 7), 15 can be substituted with 1."
Honestly, I've been having to teach myself modular arithmetic and discrete mathematics for school and have been struggling for so long and this was SO freaking useful. You explain things so well, it's amazing. Thank you so much, man! Thank you for making math so easy to comprehend and so enjoyable.
Nice preview of the chinese remainder theorem.
Thank you SO much! THIS ACTUALLY HELPED ME!!! And the fact that I only needed to watch the video once to understand this, it shows that you're great at explaining things!
Small explanation on 15l congruent to 1l:
15l = 14l + 1l = 7*2l + 1l
If you take (mod 7) of 14l and 1l 14l becomes 0 and 1l stays 1l
Thanks
Thanks , i was struggling in that
what are the |'s?
@@felixfong2667 l was the letter he used in the video, it's a variable like x
Thanks alot :)
I recently purchased a subscription to Brilliant as per your advice, and I'm loving it! Thanks so much for sharing these wonderful puzzles with us :)
I love those. Although, when tutoring my students for university entrance exams, i used to tell them to go with trial and error (just try out all but one of the choices till one fits). But I love solving them, really enjoyed that. Thanks.
What I want for this channel is Sir Steve is not a boring teacher when he lectures, and always keep smiling.
From the philippines here
This makes way more sense now! I learnt this as a formula that made no sense. Thank you for this!
I can't believe how well this was explained! Thank you so much!!
YOU REACHED 100K SUBS! Congrats!
Darshan Krishnaswamy thank you!!!!
You are so good at explaining, looking forward for more videos ;D
You have no idea how much you help me out, thank you
This was so informative. Thank you so much!! You made it clear on how to do it but I wish there was just a few more explanations on the modular arithmetic rules. Thank you nonetheless. Well done. Thanks so much!
Do you have any specific problem that you would like me to work out?
If you want to learn more about the CRT, try going for the bezout's identity and the extended euclidean algorithm (which is used to find the bezout's identitiy).
OMG!! This was SOOO useful. Thank you so much!!
Nice video, you somehow make math fun enough for me to learn it. nice explanation.
You are one of the few RUclipsrs I watch whose sponsor segments are worth watching.
Excellent video!! Thank you for teaching different areas of math. Is this topic related to divisibility?
100k subs bro big family. Congrats!
Tufan thank you!!
The passion in this mans voice resparks my love for math
Thank you so much, this video helped me a lot to understand this topic.
Your vid saves my life. Thanks
Thank u man, this helps my assignment
Nice explanation, i understand chinese remainder theorem using your lemma and proof.
Damn thanks a lot!!!
This was really helpful!!
Stuck in quarantine due to corona virus thing and stuck with Chinese remainder theorem too xD!!
Helped a lot!!❤️
Thanks for helping me solve AdventOfCode day 13!
When the system contains small numbers for the mod (like 3), you can often take a short-cut.
Whatever solution we have for these sort of systems, we can always generate another solution by adding or subtracting the product of the modulo bases, in this case 3 x 5 x 7 = 105. Hopefully, that is self-evident, since 105 congruent 0 (mod 3 or mod 5 or mod 7). So if a solution exists, it has to be between 0 and 105.
Also note that in this problem 4 congruent -1 (mod 5) and 6 congruent -1 (mod 7). That means that -1 satisfies the second and third congruencies, as does -1 + 35n where n is an integer. Since we only need examine the range 0 to 105, we only need to look at 35 -1 and 70 -1 to see if they satisfy the first congruence. Of course, 34 does. The small amount of work necessary is because 3 is such a small number, so we only need to look a two possibilities in the range.
I had a similar solution: cong 1 mod 3 means "1 more than some multiple of 3" and cong 4 mod 5 and cong 6 mod 7 both mean "1 less than some multiple of 5, and 1 less than some mult of 7". We can merge the last 2 equations into cong 34 mod 35 (1 less than some multiple of BOTH 5 AND 7), then check if 35-2 is cong 0 mod 3, in this case we got the correct answer at 1st try! So just add 1 to 33 and x = 34
HAPPY 100K U DESERVED IT MAN! FOLLOWING U SINCE 10K for real though, i've learnt a lot of al-jabr, calculus and how to think in general with ur videos. Love the content. Keep it up. Greetings from chile. Grande chile jiji viendo esta wea cuando deberia estar estudiando historia jijiji pero grande bprp
Jo Hi thank you!!!!!!!!!
Congrats brother you've crossed 0.1+ million subscriber And nearly you can increase it to 1 and more...
💐💐💐💐💐💐💐👍👍💐💐💐
Amerendra Kumar thank you!!!
This has really helped me
Here's another quick method to answer this question. The first congruence 1 ( mod 3 ) can be changed to 4 (mod 3) since 1 and 4 are congruent mod 3. By the Chinese Remainder Theorem, the first congruence 4 ( mod 3 ) and second congruence 4 ( mod 5 ) can be rewritten as 4 ( mod 15 ). 4 ( mod 15 ) can be rewritten as 34 ( mod 15 ) since 4 and 34 are congruent mod 15. Then the last congruence 6 ( mod 7 ) can rewritten as 34 ( mod 7 ) since 6 and 34 are congruent mod 7. By the Chinese Remainder Theorem, 34 ( mod 15 ) and 34 ( mod 7 ) is equivalent to 34 ( mod 105 ). Any integer of the form 105m + 34 satisfies the system of congruences just like you said. Thanks for the videos!!
this was suuupppeeerrrr helpful, thank yooooouuuu 😄😄😄
in the last bit, a little explanation related to multiplicative inverse was required.. while you were deriving relation related to L
great explaining ,thx
thank you u helped me a lot
Thanks! Great video
Love this!
I've just started this topic in my Further Maths class and these videos are very useful. Thank you so much! Keep up the good work :)
Yay!!!
Hi blackpenredpen, could you make a video making a video about geometry proofs? Thank you!
Better video ever covering chinese remainder system, all talk about using bézout theorem and getting inverse mod something kinda, but its hard and beyond 2 congruences it becomes a mess , thank u so much
This is so great. thank you dude
Happy to help : )
Why's no one talking about the Doraemon theme at the start
Nice solution.
Thanks a lot dude. You are saving lives, you don't even know it
Great video thank you.
Last 2 equation give
x ≡ -1 (mod5)
x ≡ -1 (mod7)
and therefore
x ≡ -1 (mod 35)
x = 35k -1
35k -1 ≡ 1 (mod3)
35k ≡ 2 (mod3)
2k ≡ 2 (mod3)
k ≡ 1 (mod3)
k = 3m+1
x = 35(3m+1)-1=105m+34
well explained!
thank you
You're welcome!
Our sir gave us a similar question to this, which came in a previous RMO paper and it goes as follows :
Find the smallest x for which :
x is congruent to 2(mod4)
x is congruent to 3(mod5)
x is congruent to 1(mod7)
The trick is here deriving a relation between k1, k2 and k3 by equating all of them by expressing them all in x-b=kz form.
Soln : by deriving a relation between k1 and k2 we see that that k1= 5n and k2 = 4n where n is an int, using this we can also equate k1 and k2 to k3, by expressing the third expression in the form
x-2 = 7k3 - 4
And then finding k3.
Can you make videos relating to Linear Algebra topics? That'd be awesome.
Excellent 👍 thanks 😊 I can answer now❣️
OMG! thank u so much
good video, very helpful!!!
4 mod 5 and 6 mod 7 are both one below their mod, therefore you can multiply 5 and 7 to make 35. Plug in 35k-1 to 1 mod 3. Add the +1 on each side and you get 35k being 2 mod 3. K=1 satisfies 2 mod 3 as well, therefore x = 33+2-1 or 34.
Sir , please keep uploading videos on number theory concepts
Best youtuber of 2018
You should prove the Chinese reminder theorem because I never understood the proof hahahahaha. Btw, congratulations for reaching 100k subs! I've been here since before you reached 10k!
I don't know which part you didn't understand but the most important part is this. We add 3 things together, ax5x7 + bx3x7 + cx3x5. Why? Because whatever values we choose for a b c, the first term is 0 mod 5 and 0 mod 7 etc. This means that looking at solving for 1 mod 3 we only have to worry about the value of a and we are not messing up the other requirements.
Therefore ax5x7=1 mod 3
35a=1 mod 3
2a=1 mod 3
a=2
Let me know if you need more clarification. Once you understamd why it works it becomes easy to remember as well.
The Chinese Remainder Theorem is best proven in Abstract Algebra. It becomes equivalent to finding an explicit isomorphism between certain groups, which is surprisingly straight forward.
Hi. May i ask what activity with manipulatives can i use to introduce this topic? Your help will be highly appreciated. Thanks.
I am a university student in Korea. You gave me great help for my math exam. Thank you for your effort. Keep hustling!!
You used a bluepen in this video lol😂
Thank you profesor for your excellent videos. What about systems of congruences with no coprime modules,? do exist equivalent theorem to chinese remainders theorem,? could you explain it please,,?
Can you talk about modal arithmetic? I don't anything about this topic, please. Thank you for all your videos.
Congratulations! on getting 100K+ subscribers......
Soumya Chandrakar yay!!!! Thank you!!
Excellent video...do more of number theory
yay! thank you!
I absolutely love number theory!
Thank you
I like the way you teach bro
Great discussion of the Chinese Remainder Theorem, but one thing’s missing. During the two steps you did here, you were able to easily simplify the two mod equations you got; the first one easily let you divide out 3, while the second one let you easily mod away the 15 to get 1. What is the more generic way to solve these mod equations? For example, in the example you gave, imagine omitting the second one. After you plug 3k+1 into the third mod, you get 3k=5 mod 7. Is there any way simpler than trial and error to solve this equation for k=4 mod 7?
amazing bro..keep it up
Awesome work bro,but can you make more video's on gcd and (mod).?
Your lessons about operational calculus superlative in the discret and in the continous compared with analogie transformer and anti
I'm super glad I figured this out on my own! This modular arithmetic stuff is super easy for me (well, at least these basics, I'm sure there is Olympiad level stuff that will screw me over :p). Does anyone have any slightly harder modular arithmetic problems or puzzles?
Do a course on number theory.
Well explained. Although I wonder isn't it easier to start from largest devisor (which is 7 here) and then go to smaller ones. Shouldn't we get smaller numbers cause we are casting onto smaller fields?
Thank you very much 🤗
: )
Thanks
I'm taking number theory in the summer, I'd love to see the proof for division in modular arithmetic
"Division in modular arithmetic" is known as the "Cancellation Law" in algebra where ax≡ay implies that x≡y as long as a!≡0.
I endorse +VeryEvilPettingZoo for having an excellent set of propositions derived from the very foundations of ring theory.
Please make video on chinese remainder theorem
wondeful ! tanks!!!
Cool, thanks
It has to be in the forms 3n+1, 5n-1, and 7n-1. The second two mean it has to be in the form 35n-1. Since we're looking for the smallest, it shouldn't take too long to try all of them. 34, being 35(1)-1, happens to also be 3(11)+1. That was easy.
nice
nice
Congrats in 100k!
Niklas Maier thank you!!
How I think it would be more simple:
If x=4=-1 mod 5 and x=6=-1 mod 7, we have that 5 and 7 divides x+1. Knowing that, we also have that 35 divides x+1, so we can write x+1=35k, for some natural number k. Looking x=35k-1 modulo k, we get x=2k-1 mod 3 and we have to have x=1 mod 3, so we have 2k-1=1 mod 3, so 2k=2 mod 3. It's easy to see that for k=1 it's true, and k=1 is the smalles value for which x is positive. So x=35*1-1=34 is the solution!
When I was in college our teacher simply dropped the general formula without explaining how to get it. To think it was so clear
I used *_try & check_* to solve this problem.
This approach is heuristically faster than the analytic approach when the modulos are small and quite close to each other in value like 3,5 and 7 are.
I started with the biggest modulo. I.e the last congruence equation and tried x = 6, 13, 20, 27 and then x = 34. This last value satisfies the three congruences (easily check in ones head). We can stop looking at other values of x, as the CRT guarantees there is one and only one solution to the congruence equations.
So, I then multiplied 3 × 5 × 7 to get 105. This works because 3,5 and 7 are relatively prime (they don't need to be prime, but if they are, then they are also relatively prime).
So if x = 34 satisfies the congruence and then so too does x = 34 + 105k, where k is an integer and as 3 × 5 × 7 = 105.
So, x = 34 (mod 105) is the general solution.
...and note that after the smallest such integer, there is an infinite series of greater integers with same property....and the common difference between each is the LCM, in this case, of 3, 5, and 7.
You hit 100k subscribers gj !!!!
Tudi Gaming yay!! Thank yoy
My discrete math classic skipped this. We only covered finding linear inverses.
Could you please do a complete course on further curve sketching in further maths plsss
A-Level Further Maths?
Nice video 👍
A general equation for the minimum number which gives remainders a,b,c when divided by 3, 5,7 can be written as below.
N=70a+21b+15c + or - 105n, Where n = 0,1,2,3.......
'n' can be chosen in such a way that 'N' becomes minimum.
Obviously N is the required number for the given remainders a,b,c.
Congrats for system of congruences and solution.
A shortcut to CRT!
Too much sir for your time and consideration
good thx alot
I don't know if I fell through a gap in school but modular mathematics and any math involving matrices were not presented during a relatively standard mathematics path in HS. However, students in less advanced classes, thye seemed to be a core of at least a year of their math carreer in HS. It was very strange being near top of advanced math classes and completely lost when asked for help by other students. Hopefully that picture has changed because they are very useful ideas in later mathematics.
I laughed way harder than I should’ve (even saw the joke coming) at 1:24.
I realized that the mod 5 would either end in 4 or 9. Then I went through multiples of 7 that would end in 5 or 0. The first such example is *34,* which fits all the criteria.
Thinking about it a bit more I could have realized that the last two are both mod -1, which means I could just find the least common multiple of 5 and 7, then subtract 2 and see if that's divisible by 3. If not, then double the answer and try again, then triple, and so on.
Try the same with the bases 113, 181 and 197
I did it like that:
x --- 1 (mod 3)
x --- 4 (mod 5)
x --- 6 (mod 7)
from first one I see it is also --- 4, and because the first two numbers in brackets are co-prime, I combined both to
x --- 4 (mod 15)
I created an equation
15k + 4 = 7l + 6
and by trial and error I got k=2, l=4, so x=34
Great! 15k + 4 = 7l +6 gives 15k - 7l = 2 which is a Bézout identity meaning that gcd(k, l) = 2. So smallest k and l would be 2 and 4.
Liked the Video for Simply saying thank you!
200k subscribers now!
How do you handle questions where the numbers are not relatively prime ? Thanks for your efforts and hard work
You can't always. If it says x is congruent to 1(mod 2) and also x is congruent to 2(mod 4) there can be no solution.
However something like x is congruent to 1(mod 2) and x is congruent to 1(mod 4), you can just use x ict 1(mod 4).
I have a feeling that we taught the same course :D