Chinese Remainder Theorem -- Number Theory 11

[@williamperez-hernandez3968]

8:55 The divisions are backwards, should be n_i divides (x-y), for all n_i. Therefore x-y must have the product of all n_i, so it is a multiple of N, giving the result x == y (mod N).

[@emperornortoni2871]

I earnestly thought I was losing my mind. Thanks.

[@matematicacommarcospaulo]

How can I prove that if each n_i divides x-y, then the product of all n_i also divides x-y?

[@williamperez-hernandez3968]

@@matematicacommarcospaulo Since n_i and n_j are relative primes, the prime factorization of n_i has primes not present in n_j. Therefore, x-y has all the primes of n_i and n_j in its prime factorization. This is true for the complete set {n_k}. So N has product of all different primes forming the set, as also does x-y.

[@pandawagurning]

@@matematicacommarcospaulo GCD(n_1,n_2,n_3,....,n_i)=1

[@telnobynoyator_6183]

Got me a bit confused haha

[@miasbeck]

Always good to have the Mandalorian at your side to tackle a system of congruences.

[@randobravo4335]

This guy is so entertaining as a math teacher ..I hear he even does back flips !? 🤔☺️

[@Chris_5318]

The inverse calculations can be done more systematically by noting that b^(-1) = b^(φ(n) - 1) (mod n) e.g. 2^(-1) = 2^(4-1) = 2^3 = 8 = 3 (mod 5) Note that for the CRT we have guaranteed that gcd(b,n) = 1 and so it satisfies the conditions of Euler's theorem (FLT generalisation).

[@randomdude9135]

Wow

[@2070user]

At 16:37, before he said "and that will be our "nicest" answer", I was already doing the calculation in my head. I wasn't being careful because it is just simple arithmetic, just 689-630. Then I started to take my time and I got "69" exactly at the same timing that when he said "the "nicest" answer". And I was like "oh hahahaha I see what you did there". Then when he wrote down 59 I then quickly realized how dumb I was 😂

[@lucacastenetto1230]

Hahahahahhahah thank you for sharing

[@anonymouskumar8576]

😂

[@lorencbushi5923]

Theres a really nice generalization of the CRT for ideals of a commutative ring which lets you apply it in a wider context. It can also be used to get a simple proof of the multiplicativity of the totient function.

[@theRealdesaro]

what's the name of that theorem?

[@goodplacetostop2973]

26:34 Homework 26:57 Good Place To Stop

[@2070user]

Just a trivial thing I've noticed at the "table" at 24:38. From the congruences "3⁻¹ (mod 4) ≡ 3 (mod 4)" and "2⁻¹ (mod 3) ≡ 2 (mod 3)", I got inspired and then realized that it is always true that "(n-1)⁻¹ (mod n) ≡ (n-1) (mod n)" The proof is trivial and is left as an exercise to the reader.

[@Boringpenguin]

(n-1)(n-1) = n^2 - 2n +1 ≡ 1 (mod n), or even simpler, (n-1)(n-1) ≡ (-1)(-1) ≡ 1 (mod n), so n-1 is always its own inverse modulo n.

[@bobh6728]

Help me understand. What does the inverse mean in 3(inverse) (mod 4)? Is it 1/3? I’m missing something.

[@DilipKumar-ns2kl]

Check this.Your first example can be generalized (in fact any example to solve given the divisors) If x=a(mod 3), x=b(mod7) & x=c(mod10) then required number N is given by N=70a+120b+21c (mod 210).

[@sentipy8990]

@@bobh6728 Inverse module of number "a" mod n is such number "x " so that a * x ≡ 1 (mod n). For instance inverse module of 3 mod 5 is 2 because 3 * 2 ≡ 1 (mod 5)

[@bobh6728]

@@sentipy8990 thanks. That was the first time I heard of that and missed the fairly obvious definition.

[@schrodingerbracat2927]

output from my Python program:- To solve system of congruences:- x = 4 (mod 11) x = 3 (mod 17) Solving by sum construction ... (187 / 11)^-1 = 17^-1 = 2 mod 11 (187 / 17)^-1 = 11^-1 = -3 mod 17 sum = 4*2*17 + 3*-3*11 = 37 Conclusion: x = 37 (mod 187) To solve system of congruences:- x = 0 (mod 2) x = 0 (mod 3) x = 1 (mod 5) x = 6 (mod 7) Solving by sum construction ... (210 / 2)^-1 = 105^-1 = 1 mod 2 (210 / 3)^-1 = 70^-1 = 1 mod 3 (210 / 5)^-1 = 42^-1 = -2 mod 5 (210 / 7)^-1 = 30^-1 = -3 mod 7 sum = 0*1*105 + 0*1*70 + 1*-2*42 + 6*-3*30 = -624 Conclusion: x = 6 (mod 210) >

[@endormaster2315]

Thank you, I have corrected my solutions via yours.

[@skwbusaidi]

Example2 x =1 ( mod 4) ---eq1 x=3 (mod 10) --eq2 x= 8 (mod 15) -- eq 3 From eq 1 x= 4a +1 ---eq4 Sub eq4 in eq 2 4a+1 = 3 ( mod 10) 4a = 2 ( mod 10) We want to divide by 2 but remember that gcd (2, 10) = 2 so we need to devide the mod 10 also by 2 2a = 1 ( mod 5) a = 3 ( mod 5) a = 5b +3 ---eq5 Sub eq5 in 4 x = 4( 5b+3) + 1 x= 20b + 13 ---eq6 Sub eq6 in eq3 20b+13 = 8 ( mod 15) 20b = -5 ( mod 15) 5b = 10 ( mod 15) We need to devide by 5 but gcd ( 5, 15) is 5 so the mod 15 is also devide by gcd ( 5,15) b= 2 ( mod 3) b= 3c+2 --eq7 Sub eq7 in eq6 x= 20(3c+2) +13 x= 60c + 53 x= 53 ( mod 60)

[@exvaran]

12:33 Nice

[@thomaspickin9376]

I think people need to remember the use of 'eyeballing a solution', for the warmup part 2 it looks longer but x == 0 (mod 2) => it's even x == 0 (mod 3) => it's divisible by 3, what's the first number that's both? 6. 6 (mod 5) == 1, what we wanted. 6 (mod 7) == 6 again what we wanted. Sometimes it's good to get a good idea of what might be the right solution, before diving straight in.

[@מיכאלקונטרוביץ]

Dear Michael, I want to request something from you. Could you, please, give a series of lectures on KZbin on some more advanced topics, like you did with your research interest, the vertex algebra. I mean here particularly some analytic number theory, like maybe the Prime Number Theorem (to deal with the famous asymptotic of the number of primes up to something), or maybe some algebraic number theory, geometry of numbers, etc. That's on number theory. But not only that, if you could include some measure theory, like some ergodic properties, etc. I mean if you could do something on the undergraduate upper level or the first year of graduate level courses. I know that is much of a hassle, but please consider doing that once a while when you have some time... please....

[@agrajyadav2951]

im surprised its called chinese remainder theorem and europeans didnt "rediscover" it and publish it as eg George's theorem. Thanks Gauss!

[@ConManAU]

Doing the second homework problem, I figured that I could apply the CRT to pairs of the equations and combine them, so I started by solving the mod 2 and 5 giving x = 6 mod 10 and the mod 3 and 7 giving x = 6 mod 21, then I stared at it for a second and went “… is it just 6?”

[@schrodingerbracat2927]

Output from my Python program, but yea, I could have guessed the answer. To solve system of congruences:- x = 0 (mod 2) x = 0 (mod 3) x = 1 (mod 5) x = 6 (mod 7) Solving by the pairwise method ... Solving CRT pair x = 0 (mod 2) x = 0 (mod 3) Pair soln: x = 0 (mod 6) Solving CRT pair x = 0 (mod 6) x = 1 (mod 5) Pair soln: x = 6 (mod 30) Solving CRT pair x = 6 (mod 30) x = 6 (mod 7) Pair soln: x = 6 (mod 210) Solving by sum construction ... (210 / 2)^-1 = 105^-1 = 1 mod 2 (210 / 3)^-1 = 70^-1 = 1 mod 3 (210 / 5)^-1 = 42^-1 = -2 mod 5 (210 / 7)^-1 = 30^-1 = -3 mod 7 sum = 0*1*105 + 0*1*70 + 1*-2*42 + 6*-3*30 = -624 Conclusion: x = 6 (mod 210) >

[@randomdude9135]

@@schrodingerbracat2927 what's the python program for that??

[@GKinWor]

hha perfect because i did NOT attend my lecture and it was on this

[@briana5708]

At 25:30 Michael says we need to check this solution 53 against the original problem. Is that really necessary? Or is that just a double check for errors? I can't see any case where the solution wouldn't work if you do the previous steps correctly.

[@fierydino9402]

Thank you!

[@absolutezero9874]

Hi Why is X1 congruent to inverse of N (mod n1)?

[@maxblack493]

Excellent. Thank you.

[@r.maelstrom4810]

It's the other way round: it's x == 1(mod 4) which are special cases of x == 1(mod2)

[@jiahao2709]

by the way, are there any course note for your wonderful lecture?

[@thelilpippin]

Hi Michael, I want to get a chalkboard like this, where did you get it?

[@pdjibril]

Excellent!

[@yeech]

Sorry I would like to ask: Why 2^-1(mod7) is congruent to 4(mod7)?

[@pakornlim4343]

2inverse mod 7 means that 2 times 2inverse = 1 mod 7 but we found that 2 times 2inverse = 8 mod 7 so, 2inverse = 4 mod 7.

[@Boringpenguin]

That is because (2)(4) = 8 ≡ 1 (mod 7) We say a is the inverse of x modulo n if ax ≡ 1 (mod n), and we will usually denote a as x^-1

[@yeech]

Thank you very much!!! I understand now!!

[@absolutezero9874]

@@Boringpenguin Hi New to this CRT Why is X1 congruent to inverse of N (mod n1), for eg Thank you?

[@jimallysonnevado3973]

Second problem no need to go through the steps. 6 satisfies all.

[@efrensumortin1474]

What if one of the system is X = y mod8 ?? How can we solve that? Like X = 2mod12 X= 8mod30 X = Cmod20 How can i get C??

[@justindilabio7155]

what heppen to your arm/pinky?

[@holyshit922]

What happened with his left hand Was everything ok ?

[@holyshit922]

I had been taught differently x = 2 mod 3 x = 3 mod 7 x = 9 mod 10 x = 2 mod 3 x = 3 mod 7 1 = (-2)*3+1*7 x = ((-2)*3*3 + (1)*7*2 ) mod 21 x = 17 mod 21 x = 17 mod 21 x = 9 mod 10 1 = 1*21 + (-2)*10 x = (1*21*9 + (-2)*10*17) mod 210 x = (189 - 340) mod 210 x = (189 - 340+210)mod 210 x = 59 mod 210

[@ivayloivanov5766]

Can you help me with this, please: x ≡ 2 (mod 11) x ≡ 9 (mod 15) x ≡ 7 (mod 9) x ≡ 5 (mod 7) ?

[@tejasgambhir6457]

warm up : 1) x = 37 2) X = 126

[@iabervon]

Since 4 and 15 are relatively prime and their product is a multiple of 10, you could solve the system with just 4 and 15, and check whether the answer works for 10. Also, if there are two congruences that are easy to combine, you can do that and have fewer, larger congruences to work with. For example, if you've got several that are 0 (mod something), you can find x to be 0 mod their lcm without working out any of the details, since you're going to multiply by a_i=0. It's also worth noting that you can reuse a lot of computation if you want to do a bunch of systems if you can pick the n_i to be the same for all the systems.

[@randobravo4335]

This is a good lecture but this topic of as to be in person ..this is a Gauss lecture from Gottingen and is complex

[@WillBillDillPickle]

chad!

[@klementhajrullaj1222]

What has happened with your hand?! 😲😲😲

[@MisterPenguin42]

I'm too stupid for this, but I really enjoy the videos, so I'm catching up on the math to understand what's going on.

[@paulkohl9267]

Nice video covering CRT (not Critical Race Theory but Chinese Remainder Theorem). Does anyone think it is crazy that the chinese remainder theorem reminds me of partial derivatives and maybe the chain rule? x ≡ r (mod m) analog ∂ x / ∂ m = r ....